算法打卡：第十一章 图论part08

今日收获：拓扑排序，dijkstra算法

算法讲解部分均来源于代码随想录

1. 拓扑排序

基础知识：

（1）应用场景：给出有向图，将有向图转换为线性的排序就叫拓扑排序（如果图中有环则存在循环依赖，不能做线性排序，所以拓扑排序也可以用来判断有向图中是否有环）

（2）解法：卡恩算法（BFS广度优先搜索）

（3）步骤：

• 找到入度为0的点加入结果集
• 将该节点从图中移除

（4）图中有环：此时找不到入度为0的点，所以结果集的长度小于节点个数

题目链接：117. 软件构建 (kamacoder.com)

方法：

import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();// 记录节点的入度int[] inDegree=new int[N];// 记录依赖关系List<List<Integer>> edges=new ArrayList<>(N);for (int i=0;i<N;i++){edges.add(new ArrayList<>());}// 接收依赖关系for (int i=0;i<M;i++){int s=sc.nextInt();int t=sc.nextInt();edges.get(s).add(t);  // 依赖于s的边inDegree[t]++;}// 队列存储入度为0的节点Queue<Integer> queue=new LinkedList<>();for (int i=0;i<N;i++){if (inDegree[i]==0){queue.offer(i);}}// 存储结果List<Integer> result=new ArrayList<>();while (!queue.isEmpty()){int cur=queue.poll();result.add(cur);// 将相连节点的入度减一for (int edge:edges.get(cur)){inDegree[edge]--;if (inDegree[edge]==0){queue.offer(edge);}}}// 判断是否存在环if (result.size()==N){for (int i=0;i<result.size()-1;i++){System.out.print(result.get(i)+" ");}System.out.print(result.get(N-1));}else {System.out.println(-1);}}
}

2. dijkstra算法

基础知识：

（1）求最短路径问题：给出有向图，求起点到终点的最短路径。

（2）dijkstra算法：有向图中边的权值均为非负数；可以求起点到其他节点的最短路径算法

（3）dijkstra三部曲：minDist数组用来记录每一个节点距离源点的最小距离。

• 第一步，选源点到哪个节点近且该节点未被访问过
• 第二步，该最近节点被标记访问过
• 第三步，更新非访问节点到源点的距离（即更新minDist数组）

（4）如果需要打印边，和prim算法一样，在更新minDist数组时记录父节点

（5）和prim算法的区别：

• prim是求非访问节点到最小生成树的最小距离
• dijkstra是求非访问节点到源点的最小距离，源点是固定的

（6）要求非负权值是因为，此算法后续节点距离源节点的距离=前面节点到源节点的距离+本边的权值，后面的节点一定要比前面已加入路径中的节点成本大

题目链接：47. 参加科学大会（第六期模拟笔试） (kamacoder.com)

方法：

import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();boolean[] visited=new boolean[N+1]; // 记录是否访问int[][] grid=new int[N+1][N+1];  // 记录所有的边，初始化为不可达for(int i=0;i<N+1;i++){Arrays.fill(grid[i],Integer.MAX_VALUE);}for (int i=0;i<M;i++){int s=sc.nextInt();int e=sc.nextInt();int v=sc.nextInt();grid[s][e]=v;}int[] minDist=new int[N+1];  // 其他点到源点的最小距离for (int i=0;i<N+1;i++){minDist[i]=Integer.MAX_VALUE;}minDist[1]=0;// 求到原点的最小距离for (int i=1;i<N+1;i++){int cur=-1;int minD=Integer.MAX_VALUE;// 选择最小节点for (int j=1;j<N+1;j++){if (minDist[j]<minD&&!visited[j]){cur=j;minD=minDist[j];}}if (cur==-1){break;}// 标记访问visited[cur]=true;// 更新其他节点for (int j=1;j<N+1;j++){if (minDist[cur]+grid[cur][j]<minDist[j]&&!visited[j]&&grid[cur][j]!=Integer.MAX_VALUE){minDist[j]=minDist[cur]+grid[cur][j];}}}if (minDist[N]==Integer.MAX_VALUE){System.out.println(-1);}else {System.out.println(minDist[N]);}}
}