牛二网站建设,中国商标网商标查询官方网站,自适应网站开发工具,手机微信如何制作小程序今日收获#xff1a;拓扑排序#xff0c;dijkstra算法
算法讲解部分均来源于代码随想录
1. 拓扑排序
基础知识#xff1a;
#xff08;1#xff09;应用场景#xff1a;给出有向图#xff0c;将有向图转换为线性的排序就叫拓扑排序#xff08;如果图中有环则存在循…今日收获拓扑排序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 scnew Scanner(System.in);int Nsc.nextInt();int Msc.nextInt();// 记录节点的入度int[] inDegreenew int[N];// 记录依赖关系ListListInteger edgesnew ArrayList(N);for (int i0;iN;i){edges.add(new ArrayList());}// 接收依赖关系for (int i0;iM;i){int ssc.nextInt();int tsc.nextInt();edges.get(s).add(t); // 依赖于s的边inDegree[t];}// 队列存储入度为0的节点QueueInteger queuenew LinkedList();for (int i0;iN;i){if (inDegree[i]0){queue.offer(i);}}// 存储结果ListInteger resultnew ArrayList();while (!queue.isEmpty()){int curqueue.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 i0;iresult.size()-1;i){System.out.print(result.get(i) );}System.out.print(result.get(N-1));}else {System.out.println(-1);}}
}
2. dijkstra算法
基础知识
1求最短路径问题给出有向图求起点到终点的最短路径。
2dijkstra算法有向图中边的权值均为非负数可以求起点到其他节点的最短路径算法
3dijkstra三部曲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 scnew Scanner(System.in);int Nsc.nextInt();int Msc.nextInt();boolean[] visitednew boolean[N1]; // 记录是否访问int[][] gridnew int[N1][N1]; // 记录所有的边初始化为不可达for(int i0;iN1;i){Arrays.fill(grid[i],Integer.MAX_VALUE);}for (int i0;iM;i){int ssc.nextInt();int esc.nextInt();int vsc.nextInt();grid[s][e]v;}int[] minDistnew int[N1]; // 其他点到源点的最小距离for (int i0;iN1;i){minDist[i]Integer.MAX_VALUE;}minDist[1]0;// 求到原点的最小距离for (int i1;iN1;i){int cur-1;int minDInteger.MAX_VALUE;// 选择最小节点for (int j1;jN1;j){if (minDist[j]minD!visited[j]){curj;minDminDist[j];}}if (cur-1){break;}// 标记访问visited[cur]true;// 更新其他节点for (int j1;jN1;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]);}}
}
