拓扑排序算法相关的知识点总结
拓扑排序算法是一种对有向无环图（DAG）进行排序的方法，它可以将图中的所有顶点排成一个线性序列，使得对于任意一对顶点u和v，如果存在一条从u到v的有向边，那么u在序列中必然出现在v之前。拓扑排序算法可以用来解决一些依赖关系的问题，例如课程安排、工程进度、编译顺序等。
拓扑排序算法的原理
拓扑排序算法的基本思想是从图中选择一个没有前驱（即入度为0）的顶点并输出，然后从图中删除该顶点和所有以它为起点的有向边，重复这一步骤直到所有顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环，因此不可能进行拓扑排序。
拓扑排序算法可以用深度优先搜索或广度优先搜索来实现，下面分别介绍这两种方法。
拓扑排序算法的实现方法
深度优先搜索
深度优先搜索的方法是对每个未访问的节点，执行以下操作：
- 标记当前节点为访问中
- 递归访问当前节点的所有邻接节点，如果发现已经访问过或者正在访问中的节点，说明存在环，返回false
- 标记当前节点为已访问，并将其加入结果栈
- 返回true
最后，如果没有发现环，将结果栈中的元素逆序输出即为拓扑排序。
以下是用Java实现的深度优先搜索拓扑排序算法的代码：
class Solution {
// 用一个枚举类型表示节点的三种状态
enum State {
UNVISITED, // 未访问
VISITING, // 访问中
VISITED // 已访问
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 邻接表
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
// 状态数组
State[] states = new State[numCourses];
Arrays.fill(states, State.UNVISITED);
// 结果栈
Stack<Integer> stack = new Stack<>();
// 遍历先决条件，构建邻接表
for (int[] p : prerequisites) {
adj.get(p[1]).add(p[0]);
}
// 对每个未访问的节点进行深度优先搜索
for (int i = 0; i < numCourses; i++) {
if (states[i] == State.UNVISITED) {
if (!dfs(i, adj, states, stack)) {
return new int[0]; // 发现环，返回空数组
}
}
}
// 将结果栈中的元素逆序输出
int[] res = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = stack.pop();
}
return res;
}
// 深度优先搜索函数，返回是否有环
private boolean dfs(int cur, List<List<Integer>> adj, State[] states, Stack<Integer> stack) {
states[cur] = State.VISITING; // 标记当前节点为访问中
for (int next : adj.get(cur)) { // 遍历当前节点的邻接节点
if (states[next] == State.VISITING) { // 如果发现正在访问中的节点，说明有环
return false;
}
if (states[next] == State.UNVISITED) { // 如果发现未访问的节点，递归访问
if (!dfs(next, adj, states, stack)) {
return false;
}
}
}
states[cur] = State.VISITED; // 标记当前节点为已访问
stack.push(cur); // 将当前节点加入结果栈
return true;
}
}
广度优先搜索
广度优先搜索的方法是维护一个队列和一个入度数组，入度数组记录每个节点的前驱节点个数。初始时，将所有入度为0的节点加入队列，并将其加入结果列表。然后执行以下操作：
- 从队列中弹出一个节点
- 遍历该节点的所有邻接节点，将其入度减一
- 如果某个邻接节点的入度变为0，将其加入队列，并将其加入结果列表
- 重复以上步骤直到队列为空
最后，如果结果列表的长度等于课程数，说明可以完成所有课程，返回结果列表，否则说明存在环，返回空数组。
以下是用Java实现的广度优先搜索拓扑排序算法的代码：
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 邻接表
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
// 入度数组
int[] indegrees = new int[numCourses];
// 结果数组
int[] res = new int[numCourses];
// 记录结果数组的索引
int index = 0;
// 队列，存放入度为0的节点
Queue<Integer> queue = new LinkedList<>();
// 遍历先决条件，构建邻接表和入度数组
for (int[] p : prerequisites) {
adj.get(p[1]).add(p[0]);
indegrees[p[0]]++;
}
// 将所有入度为0的节点入队，并加入结果数组
for (int i = 0; i < numCourses; i++) {
if (indegrees[i] == 0) {
queue.offer(i);
res[index++] = i;
}
}
// 当队列不为空时，循环以下操作
while (!queue.isEmpty()) {
// 出队一个节点
int cur = queue.poll();
// 遍历该节点的所有邻接节点，将其入度减一
for (int next : adj.get(cur)) {
indegrees[next]--;
// 如果某个邻接节点的入度变为0，将其入队，并加入结果数组
if (indegrees[next] == 0) {
queue.offer(next);
res[index++] = next;
}
}
}
// 如果结果数组的长度等于课程数，说明可以完成所有课程，返回结果数组
if (index == numCourses) {
return res;
}
// 否则，返回一个空数组
return new int[0];
}
}
拓扑排序算法的应用
拓扑排序算法可以用来解决一些依赖关系的问题，例如：
- 课程安排：如果想要学习某些课程，需要先完成一些先修课程，那么可以用拓扑排序算法来确定学习顺序。
- 工程进度：如果想要完成一个工程项目，需要先完成一些前置任务，那么可以用拓扑排序算法来安排工作计划。
- 编译顺序：如果想要编译一个程序，需要先编译一些依赖模块，那么可以用拓扑排序算法来确定编译顺序。
拓扑排序算法的总结
拓扑排序算法是一种对有向无环图进行排序的方法，它可以将图中的所有顶点排成一个线性序列，使得对于任意一对顶点u和v，如果存在一条从u到v的有向边，那么u在序列中必然出现在v之前。拓扑排序算法可以用深度优先搜索或广度优先搜索来实现，它们的时间复杂度都是O(V+E)，其中V是顶点数，E是边数。拓扑排序算法可以用来解决一些依赖关系的问题，例如课程安排、工程进度、编译顺序等。
拓扑排序算法的核心思想是不断地选择入度为0的顶点并删除，如果图中存在环，那么一定会有顶点的入度永远不为0，因此无法进行拓扑排序。拓扑排序算法的结果不一定是唯一的，因为可能有多个顶点的入度同时为0，它们的输出顺序可以任意交换。
拓扑排序算法是图论中的一个重要概念，它可以帮助我们理解和解决一些实际问题中的依赖关系。通过学习和掌握拓扑排序算法，我们可以提高我们的逻辑思维和编程能力。希望这篇博客能对你有所帮助，谢谢阅读！