Day64_20250212_图论part8_拓扑排序|dijkstrs(朴素版)
Day64_20250212_图论part8_拓扑排序|dijkstrs(朴素版)
拓扑排序
题目
题目描述：
某个大型软件项目的构建系统拥有 N 个文件，文件编号从 0 到 N - 1，在这些文件中，某些文件依赖于其他文件的内容，这意味着如果文件 A 依赖于文件 B，则必须在处理文件 A 之前处理文件 B （0 <= A, B <= N - 1）。请编写一个算法，用于确定文件处理的顺序。
输入描述：
第一行输入两个正整数 N, M。表示 N 个文件之间拥有 M 条依赖关系。
后续 M 行，每行两个正整数 S 和 T，表示 T 文件依赖于 S 文件。
输出描述：
输出共一行，如果能处理成功，则输出文件顺序，用空格隔开。
如果不能成功处理（相互依赖），则输出 -1。
输入示例：
5 4
0 1
0 2
1 3
2 4
输出示例：
0 1 2 3 4
提示信息：
文件依赖关系如下：
所以，文件处理的顺序除了示例中的顺序，还存在
0 2 4 1 3
0 2 1 3 4
等等合法的顺序。
数据范围：
- 0 <= N <= 10 ^ 5
- 1 <= M <= 10 ^ 9
思路
- 思路
-
依赖顺序
- 线性的依赖顺序，很容易排序。
- 有很多依赖关系，依赖关系中可能还有循环依赖。
- 怎么发现循环依赖？怎么排出线性顺序？
-
拓扑排序：给出一个有向图，把这个有向图转换成线性的顺序(把有向无环图进行线性排序的算法)
- 细节
- 同时，检测有向图是否有环，存在循环依赖的情况。(不能做线性排序)
- 图论中判断有向无环图的常用方法。
- 在图论中判断有向无环图的常用方法。
- 种类
- 卡恩算法(BFS) 先掌握这个
- DFS
- 细节
-
- 代码思路
- 1.找到入度为0的节点，加入结果集
- 找入度为0的节点
- 2.将该节点从图中移除
- 循环以上两步骤，直到所有节点都在图中被移除了。结果集的顺序就是拓扑排序顺序(顺序可能不唯一)
- 特殊情况：
-
判断有有向环
- 结果集元素个数!=图中节点个数
-
- 1.找到入度为0的节点，加入结果集
- 伪代码
- 0.统计每个节点的入度和依赖关系
- 1.将入度为0的节点存放在队列中(不是只有1个入度为0的节点) 【！！！注意】
- 2.从队列里遍历入度为0的节点，将其放入结果集。
- 同时将此节点从图中移除(为了将该节点作为出发点所连接的边删掉)。
- 将该节点作为出发点所连接的节点的入度减1，以便选取下一个节点。
- 3.特殊情况：判断是否有有向环
- 代码
import java.util.*; public class Main{ public static void main(String[] args){ //输入 Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m=scanner.nextInt(); //记录每个文件的入度 int[] inDegree=new int[n]; 0.记录文件依赖关系 二维 List<List<Integer>> umap=new ArrayList<>(); for(int i=0;i<n;i++){ umap.add(new ArrayList());//为每个s创造list } for(int i=0;i<m;i++){ int s=scanner.nextInt(); int t=scanner.nextInt(); umap.get(s).add(t);//获取s的依赖list，将t加进去 inDegree[t]++;//每个节点的入度 } 1.将入度为0的节点存放在队列中 Queue<Integer> queue=new LinkedList<>(); for(int i=0;i<n;i++){ if(inDegree[i]==0){ //入度为0的文件，可以作为开头，先加入队列 queue.add(i); } } 2.将队列里遍历入度为0的节点,将其放入结果集 List<Integer> result=new ArrayList<>(); //拓扑排序 while(!queue.isEmpty()){ int cur=queue.poll();//当前选中的文件 result.add(cur);//将队列依次放入结果集 //遍历每个cur的依赖关系 for(int file:umap.get(cur)){ inDegree[file]--;//cur的指向的文件入度-1，删除边 //if度=0,再次加入度为0的文件，循环 if(inDegree[file]==0){ queue.add(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); } } }
总结
- 思路简单，代码细节需要注意。
- 除了最后一个地方不需要加空格，其他地方都需要
- 要有一个过渡到result的队列queue，因为每次检查度为0的节点可能有很多个
dijkstrs(朴素版) 【最短路算法】
题目
题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。
小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。
小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。
输入描述
第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。
接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。
输出描述
输出一个整数，代表小明从起点到终点所花费的最小时间。
输入示例
7 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 2
4 5 3
2 6 4
5 7 4
6 7 9
输出示例
12
提示信息
能够到达的情况：
如下图所示，起始车站为 1 号车站，终点车站为 7 号车站，绿色路线为最短的路线，路线总长度为 12，则输出 12。
不能到达的情况：
如下图所示，当从起始车站不能到达终点车站时，则输出 -1。
数据范围：
1 <= N <= 500;
1 <= M <= 5000;
思路
- 思路
- 【花费时间最少】
- 【最短路问题】给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。
- dijkstra算法：在有权图(权值非负数)中求从起点到其他节点的最短路径算法。
-
特点：
- dijkstra算法可以同时求起点到所有节点的最短路径。
- 权值不能为负数。
-
思路：(贪心)，不断寻找距离源点最近的没有访问过的节点。
-
dijkstra三部曲
- 1.选源点到哪个节点近且该节点未被访问过
- 2.该最近节点被标记访问过
- 3.更新非访问节点到源点的距离(更新minDist数组)
-
细节
- minDist数组: 用来记录每一个节点距离【源点】的最小距离。
- 从下标1开始标记
- 怎么把路径print出来，用日志
- 出现负数也能正常运行吗？
- 不正常运行，但是没有走有负权值的最短路径，是因为在访问节点2的时候，节点3已经访问过了，就不会再更新了。
- 不能改逻辑(访问过的节点，也让它继续访问。)
- 访问过的节点还能继续访问会不会有死循环的出现呢。
- 因为访问过的节点不能再访问，导致错过真正的最短路。
-
- dijkstra与prim算法的区别
- 区别在于更新minDist数组。
- 因为prim是求非访问节点到最小生成树的最小距离，而dijkstra是求非访问节点到源点的最小距离。
- 区别在于更新minDist数组。
- 伪代码
- 0.初始化
- imnDist数组初始化为int最大值。 【记录所有节点到源点的最短路径】
- visited数组，默认为0，表示有没有访问过
-
- 选源点到哪个节点近且该节点未被访问过。源点距离源点最近，距离为0，且未被访问。
-
- 该最近节点被标记访问过
-
- 更新非访问节点到源点的距离(更新minDist数组)
- 打印日志
- 0.初始化
- 代码
import java.util.*; public class Main{ 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]; //起始点到自身的距离为0，必须加上，以便推理 minDist[start]=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; } } //2.标记该节点已被访问 visited[cur]=true; //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]){ //更新源点到此节点v的最短路径 minDist[v]=minDist[cur]+grid[cur][v]; } } } //打印 if(minDist[end]==Integer.MAX_VALUE){ System.out.println(-1);//不能到达终点 }else{ System.out.println(minDist[end]);//到达终点最终路径 } } }
总结
- 打印+终止条件
- if(minDist[end]==Integer.MAX_VALUE)
- 一定要初始化，//起始点到自身的距离为0，必须加上，以便推理
minDist[start]=0; - M公路，为了遍历M而得到边的权重(2点之间的路径)