day57 图论章节刷题Part08（拓扑排序、dijkstra（朴素版））

拓扑排序-117. 软件构建

思路：拓扑排序是经典的图论问题。给出一个有向图，把有向图转成线性的排序就叫拓扑排序，拓扑排序也要检测有向图是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的，所以拓扑排序也是图论中判断有向无环图的常用方法。

实现拓扑排序的算法有两种：卡恩算法（BFS）和DFS。一般来说只需要掌握 BFS （广度优先搜索）就可以了。

应用场景：大学排课，先上A课才能上B课，上了B课才能上C课，上了A课才能上D课等等，要求规划出一条完整的上课顺序。

核心思想

拓扑排序时应该优先找 入度为 0 的节点，只有入度为0才是出发节点。
拓扑排序的过程：

• 找到入度为0 的节点，加入结果集；
• 将该节点从图中移除；
  循环以上两步，直到 所有节点都在图中被移除了。如果我们发现结果集元素个数 不等于 图中节点个数，我们就可以认定图中一定有 有向环！

代码实现

import java.util.*;
public class Main{public static void main (String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();//存放文件之间的映射关系List<List<Integer>> umap=new ArrayList<>();for(int i=0;i<n;i++) umap.add(new ArrayList<>());//文件的入度int[] inDegree=new int[n];for(int i=0;i<m;i++){int s=scan.nextInt();int t=scan.nextInt();umap.get(s).add(t);inDegree[t]++;}Queue<Integer> queue=new LinkedList<>();//找到入度为零的节点加入队列for(int i=0;i<n;i++){if(inDegree[i]==0){queue.add(i);}}List<Integer> result=new ArrayList<>();while(!queue.isEmpty()){int cur=queue.poll();result.add(cur);for(int file:umap.get(cur)){inDegree[file]--;if(inDegree[file]==0) queue.offer(file);}}if(result.size()==n){for(int i=0;i<result.size();i++){System.out.print(result.get(i));if(i<result.size()-1) System.out.print(" ");}}else{System.out.println(-1);}}
}

dijkstra（朴素版）-47. 参加科学大会

最短路是图论中的经典问题即：给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。

dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。

• dijkstra 算法可以同时求 起点到所有节点的最短路径
• 权值不能为负数

与prim算法类似，dijkstra 算法同样是贪心的思路，不断寻找距离源点最近的没有访问过的节点。

dijkstra三部曲：
第一步，选择距离源点最近且未被访问过的节点
第二步，被标记改节点已被访问
第三步，更新未访问节点到源点的距离（即更新minDist数组）

代码实现

初始化-minDist数组数值初始化为int最大值。源点（节点1） 到自己的距离为0，所以 minDist[1] = 0；此时所有节点都没有被访问过，所以 visited数组都为0。

import java.util.*;
public class Main{public static void main (String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.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 s=scan.nextInt();int t=scan.nextInt();int k=scan.nextInt();grid[s][t]=k;}int[] minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);boolean[] visited=new boolean[n+1];//源点到源点的距离为0minDist[1]=0;for(int i=1;i<=n;i++){int cur=1;int minVal=Integer.MAX_VALUE;for(int j=1;j<=n;j++){if(!visited[j] && minDist[j]<minVal){cur=j;minVal=minDist[j];}}//标记改节点已经被访问visited[cur]=true;for(int j=1;j<=n;j++){if(!visited[j] && grid[cur][j]!=Integer.MAX_VALUE && grid[cur][j]+minDist[cur]<minDist[j])minDist[j]=grid[cur][j]+minDist[cur];}}if(minDist[n]!=Integer.MAX_VALUE) System.out.println(minDist[n]);else System.out.println(-1);}
}

注意：设置初始值的时候也要定义cur=1，这样当节点全都被访问过时，cur为合法值。