第十一章：图论part08
拓扑排序精讲
拓扑排序看上去很复杂，其实了解其原理之后，代码不难
文章讲解
思路
-
拓扑排序的应用场景。
大学排课，例如 先上A课，才能上B课，上了B课才能上C课，上了A课才能上D课，等等一系列这样的依赖顺序。 问给规划出一条 完整的上课顺序。- 任务调度：在任务之间存在依赖关系的情况下，拓扑排序可以用于确定任务的执行顺序。
- 编译顺序：在编译器中，确定模块或文件的编译顺序。
- 课程安排：根据课程的先修关系确定课程的学习顺序。
概括来说，给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。
当然拓扑排序也要检测这个有向图 是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。
所以拓扑排序也是图论中判断有向无环图的常用方法。拓扑排序指的是一种 解决问题的大体思路， 而具体算法，可能是广搜也可能是深搜。
实现拓扑排序的算法有两种：卡恩算法（BFS）和DFS
BFS的实现思路
以本题为例
image.png
拓扑排序（Topological Sorting）是一种用于有向无环图（DAG, Directed Acyclic Graph）的排序算法，旨在将图的顶点排成一个线性序列，使得对于每一条从顶点
u 到顶点 v 的有向边，u 在序列中出现在 v 之前。
拓扑排序的过程总结：
-
找到入度为0的节点，加入结果集：
- 初始时，找到图中所有入度为0的节点。入度为0的节点表示没有任何其他节点指向它们，因此它们是图的起点。
- 将这些入度为0的节点加入结果集，表示它们在拓扑排序中的顺序。
-
将该节点从图中移除：
- 对于已加入结果集的节点，将它们从图中删除，具体操作是：
- 移除这些节点以及它们指向的所有边。
- 更新剩余节点的入度。受影响的节点入度减少，因为指向它们的边被删除了。
- 对于已加入结果集的节点，将它们从图中删除，具体操作是：
-
重复以上步骤：
- 继续查找当前图中入度为0的节点，并重复步骤1和2。
- 每找到一个入度为0的节点，就将其加入结果集，并从图中移除，直到所有节点都被移除。
-
结束条件：
- 如果所有节点都已被处理完毕，结果集即为拓扑排序的顺序。
- 如果在某一轮中无法找到入度为0的节点，且仍有未处理的节点，说明图中存在有向环。此时，无法进行完整的拓扑排序。
判断有向环的标准：
- 在拓扑排序过程中，如果所有节点都能加入结果集，那么图是无环的。
- 如果存在无法处理的节点（即在图中找不到入度为0的节点，但图中仍有节点），则图中存在有向环。
具体模拟过程参见代码随想录原文。
写代码
import java.util.*;
public class TopologicalSort {
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]; // 记录每个节点的入度
List<Integer> result = new ArrayList<>(); // 记录拓扑排序结果
Map<Integer, List<Integer>> graph = new HashMap<>(); // 记录节点的依赖关系（邻接表）
// 读取边的信息，并更新入度数组和图的邻接表
for (int i = 0; i < m; i++) {
int s = scanner.nextInt(); // 先有s节点
int t = scanner.nextInt(); // 后有t节点
inDegree[t]++; // t节点的入度加一
graph.computeIfAbsent(s, k -> new ArrayList<>()).add(t); // 记录s指向哪些节点
}
// 初始化队列，寻找所有入度为0的节点
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
// 入度为0的节点，可以作为起点，加入队列
if (inDegree[i] == 0) queue.add(i);
}
// 开始处理队列中的节点，执行拓扑排序
while (!queue.isEmpty()) {
int cur = queue.poll(); // 当前处理的节点
result.add(cur); // 将该节点加入结果集
// 获取当前节点cur指向的所有节点
List<Integer> files = graph.get(cur);
if (files != null) { // 如果cur有指向的节点
for (int file : files) {
inDegree[file]--; // cur指向的节点的入度减一
// 如果某个节点的入度减为0，则将其加入队列
if (inDegree[file] == 0) queue.add(file);
}
}
}
// 判断是否所有节点都已被处理完，如果是则输出拓扑排序结果，否则输出-1（图中有环）
if (result.size() == n) {
for (int i = 0; i < n - 1; i++) {
System.out.print(result.get(i) + " ");
}
System.out.print(result.get(n - 1));
} else {
System.out.println(-1); // 图中存在有向环
}
}
}
说明：
-
inDegree数组：用来记录每个节点的入度。Java中使用int[]数组来实现。 -
result列表：用来存放拓扑排序的结果。Java中使用ArrayList来实现。 -
graph哈希表：用来记录图中每个节点的依赖关系（即出边）。Java中使用HashMap和ArrayList的组合来实现，computeIfAbsent方法用于简化向图中添加边的逻辑。 -
queue队列：用来存放当前入度为0的节点。Java中使用LinkedList来实现队列操作。 - 主要逻辑：遍历队列中的入度为0的节点，将其添加到结果集中，并更新其指向的节点的入度。如果一个节点的入度减为0，则将其加入队列。最终，检查结果集的大小是否等于节点数量，以判断是否完成了拓扑排序。
dijkstra（朴素版）精讲
后面几天都是最短路系列了，对于最短路系列，我的建议是，如果第一次接触最短路算法的话，能看懂原理，能照着代码随想录把代码抄下来就可以了，二刷的时候 再尝试自己去写出来。 三刷的时候，差不多才能把最短路吃透。
对于一刷的录友们，不要强行去逼迫自己去学透，很难刚接触到最短路算法就学透。
文章讲解
思路
-
dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。
需要注意两点：- dijkstra 算法可以同时求 起点到所有节点的最短路径
- 权值不能为负数
-
dijkstra三部曲：
- 第一步，选源点到哪个节点近且该节点未被访问过
- 第二步，该最近节点被标记访问过
- 第三步，更新非访问节点到源点的距离（即更新minDist数组）
（示例中节点编号是从1开始，所以为了让大家看的不晕，minDist数组下标我也从 1 开始计数，下标0 就不使用了，这样 下标和节点标号就可以对应上了，避免大家搞混）
具体例子参见代码随想录原文章
1. 算法实现
这段代码实现了Dijkstra算法来计算从起点到所有节点的最短路径。
import java.util.*;
public class DijkstraShortestPath {
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); // 初始化邻接矩阵，使用INT_MAX表示无穷大
}
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]; // 存储从源点到每个节点的最短距离
boolean[] visited = new boolean[n + 1]; // 记录顶点是否被访问过
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0; // 起始点到自身的距离为0
// Dijkstra算法实现
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;
}
}
if (cur == -1) break; // 如果cur依然为-1，说明剩余节点不可达，直接跳出
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]); // 到达终点的最短路径
}
}
}
2. 调试代码
在这段代码中，我们添加了调试日志，以便在每一步中查看minDist数组的状态。
import java.util.*;
public class DijkstraShortestPathDebug {
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); // 初始化邻接矩阵，使用INT_MAX表示无穷大
}
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]; // 存储从源点到每个节点的最短距离
boolean[] visited = new boolean[n + 1]; // 记录顶点是否被访问过
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0; // 起始点到自身的距离为0
// Dijkstra算法实现
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;
}
}
if (cur == -1) break; // 如果cur依然为-1，说明剩余节点不可达，直接跳出
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];
}
}
// 打印调试日志：
System.out.println("Select: " + cur);
for (int v = 1; v <= n; v++) {
System.out.print(v + ": " + (minDist[v] == Integer.MAX_VALUE ? "INF" : minDist[v]) + " ");
}
System.out.println("\n");
}
// 输出结果
if (minDist[end] == Integer.MAX_VALUE) {
System.out.println(-1); // 不能到达终点
} else {
System.out.println(minDist[end]); // 到达终点的最短路径
}
}
}
3. 打印路径代码
在这段代码中，我们添加了路径打印的功能，以显示从起点到各个节点的路径。
import java.util.*;
public class DijkstraShortestPathWithPath {
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); // 初始化邻接矩阵，使用INT_MAX表示无穷大
}
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]; // 存储从源点到每个节点的最短距离
boolean[] visited = new boolean[n + 1]; // 记录顶点是否被访问过
int[] parent = new int[n + 1]; // 用于记录路径
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0; // 起始点到自身的距离为0
Arrays.fill(parent, -1); // 初始化parent数组，-1表示没有父节点
// Dijkstra算法实现
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;
}
}
if (cur == -1) break; // 如果cur依然为-1，说明剩余节点不可达，直接跳出
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];
parent[v] = cur; // 记录父节点
}
}
}
// 输出结果
if (minDist[end] == Integer.MAX_VALUE) {
System.out.println(-1); // 不能到达终点
} else {
System.out.println("Shortest distance to node " + end + ": " + minDist[end]);
}
// 输出路径信息
System.out.println("Path:");
for (int i = 1; i <= n; i++) {
if (parent[i] != -1) {
System.out.println(parent[i] + " -> " + i);
} else if (i == start) {
System.out.println("Start -> " + i);
}
}
}
}
拓展
带有负权值的最短路径问题
- 求解带有负权值的最短路问题，可以使用 Bellman-Ford 算法
dijkstra与prim算法的区别
其实代码大体不差，唯一区别在 三部曲中的 第三步： 更新minDist数组
因为prim是求 非访问节点到最小生成树的最小距离，而 dijkstra是求 非访问节点到源点的最小距离
- Prim算法更新
minDist数组的写法
for (int j = 1; j <= v; j++) {
if (!isInTree[j] && grid[cur][j] < minDist[j]) {
minDist[j] = grid[cur][j];
}
}
解释：
-
isInTree[j]：表示节点j是否已经加入到生成树中。 -
grid[cur][j]：表示当前节点cur与节点j之间的边的权重。 -
minDist[j]：表示节点j到生成树的最小距离。如果cur加入生成树后，cur到j的距离比当前j的最小距离更短，则更新minDist[j]。
- Dijkstra算法更新
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];
}
}
解释：
-
visited[v]：表示节点v是否已经被访问过。 -
grid[cur][v]：表示当前节点cur与节点v之间的边的权重。 -
minDist[cur]：表示从源点到cur的最短距离。 -
minDist[v]：表示从源点到节点v的最短距离。如果cur到v的距离加上源点到cur的距离比当前源点到v的最短距离更短，则更新minDist[v]。
