代码随想录训练营第五十八天| 拓扑排序精讲 dijkstra（朴素版）精讲
拓扑排序精讲
其实只要能在把 有向无环图 进行线性排序 的算法 都可以叫做 拓扑排序。
实现拓扑排序的算法有两种：卡恩算法（BFS）和DFS
卡恩1962年提出这种解决拓扑排序的思路
引自代码随想录：
一般来说我们只需要掌握 BFS （广度优先搜索）就可以了，清晰易懂，如果还想多了解一些，可以再去学一下 DFS 的思路，但 DFS 不是本篇重点。
接下来我们来讲解BFS的实现思路。
以题目中示例为例如图：
做拓扑排序的话，如果肉眼去找开头的节点，一定能找到 节点0 吧，都知道要从节点0 开始。
但为什么我们能找到 节点0呢，因为我们肉眼看着 这个图就是从 节点0出发的。
作为出发节点，它有什么特征？
你看节点0 的入度 为0 出度为2， 也就是 没有边指向它，而它有两条边是指出去的。
节点的入度表示 有多少条边指向它，节点的出度表示有多少条边 从该节点出发。
所以当我们做拓扑排序的时候，应该优先找 入度为 0 的节点，只有入度为0，它才是出发节点。 理解以上内容很重要！
接下来我给出 拓扑排序的过程，其实就两步：
- 找到入度为0 的节点，加入结果集
- 将该节点从图中移除
循环以上两步，直到 所有节点都在图中被移除了。
结果集的顺序，就是我们想要的拓扑排序顺序 （结果集里顺序可能不唯一）
判断有环
如果有 有向环怎么办呢？例如这个图：
这个图，我们只能将入度为0 的节点0 接入结果集。
之后，节点1、2、3、4 形成了环，找不到入度为0 的节点了，所以此时结果集里只有一个元素。
那么如果我们发现结果集元素个数 不等于 图中节点个数，我们就可以认定图中一定有 有向环！
这也是拓扑排序判断有向环的方法。
模版如下
import java.util.*;
public class Carlcodetpsort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
List<List<Integer>> list = new ArrayList<>();//记录文件依赖关系
int[] inDegree = new int[n];//记录每个文件的入度
for(int i = 0; i < n; i++){
list.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int s = scanner.nextInt();
int t = scanner.nextInt();
list.get(s).add(t);//记录s指向哪些文件
inDegree[t]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if(inDegree[i] == 0){
//入度为0的文件 可以作为开头 先加入队列
queue.add(i);
}
}
List<Integer> ans = new ArrayList<>();
//拓扑排序
while(!queue.isEmpty()){
int cur = queue.poll();
ans.add(cur);
for(int file : list.get(cur)){
if(inDegree[file] == 0){
queue.add(file);
}
}
}
if(ans.size() == n){
for (int i = 0; i < ans.size(); i++) {
System.out.println(ans.get(i));
if(i < ans.size() - 1){
System.out.println(" ");
}else{
System.out.println(-1);
}
}
}
}
}
dijkstra（朴素版）精讲
以下内容引自代码随想录：
dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。
需要注意两点：
- dijkstra 算法可以同时求 起点到所有节点的最短路径
- 权值不能为负数
dijkstra 算法 同样是贪心的思路，不断寻找距离 源点最近的没有访问过的节点。
这里我也给出 dijkstra三部曲：
- 第一步，选源点到哪个节点近且该节点未被访问过
- 第二步，该最近节点被标记访问过
- 第三步，更新非访问节点到源点的距离（即更新minDist数组）
模拟过程
0、初始化
minDist数组数值初始化为int最大值。
这里在强点一下 minDist数组的含义：记录所有节点到源点的最短路径，那么初始化的时候就应该初始为最大值，这样才能在后续出现最短路径的时候及时更新。
（图中，max 表示默认值，节点0 不做处理，统一从下标1 开始计算，这样下标和节点数值统一， 方便大家理解，避免搞混）
源点（节点1） 到自己的距离为0，所以 minDist[1] = 0
此时所有节点都没有被访问过，所以 visited数组都为0
以下为dijkstra 三部曲
1、选源点到哪个节点近且该节点未被访问过
源点距离源点最近，距离为0，且未被访问。
2、该最近节点被标记访问过
标记源点访问过
3、更新非访问节点到源点的距离（即更新minDist数组） ，如图：
更新 minDist数组，即：源点（节点1） 到 节点2 和 节点3的距离。
- 源点到节点2的最短距离为1，小于原minDist[2]的数值max，更新minDist[2] = 1
- 源点到节点3的最短距离为4，小于原minDist[3]的数值max，更新minDist[3] = 4
和prim算法近似
import java.util.Arrays;
import java.util.Scanner;
public class Carlcode_dijkstra {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(grid[i], Integer.MAX_VALUE);
}
for (int i = 0; i < m; i++) {
int p1 = scanner.nextInt();
int p2 = scanner.nextInt();
int val = scanner.nextInt();
grid[p1][p2] = val;
}
int start = 1;
int end = n;
// 存储从源点到每个节点的最短距离
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
// 记录顶点是否被访问过
boolean[] visited = new boolean[n + 1];
minDist[start] = 0; // 起始点到自身的距离为0
for (int i = 1; i <= n; i++) { // 遍历所有节点
int minVal = Integer.MAX_VALUE;
int cur = 1;
// 1、选距离源点最近且未访问过的节点
for (int v = 1; v <= n; ++v) {
if (!visited[v] && minDist[v] < minVal) {
minVal = minDist[v];
cur = v;
}
}
visited[cur] = true; // 2、标记该节点已被访问
// 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
for (int v = 1; v <= n; v++) {
if (!visited[v] && grid[cur][v] != Integer.MAX_VALUE && minDist[cur] + grid[cur][v] < minDist[v]) {
minDist[v] = minDist[cur] + grid[cur][v];
}
}
}
if (minDist[end] == Integer.MAX_VALUE) {
System.out.println(-1); // 不能到达终点
} else {
System.out.println(minDist[end]); // 到达终点最短路径
}
}
}