图算法之拓扑排序(Topological Sort)详细解读
拓扑排序(Topological Sort)是针对有向无环图(DAG,Directed Acyclic Graph)的一种线性排序方式,它将图中的所有顶点按顺序排列,使得对于每条有向边 (u, v)
,顶点 u
必须排在顶点 v
之前。拓扑排序广泛应用于任务调度、编译器语法分析、依赖管理等场景中。
拓扑排序的定义与特性
- 有向无环图(DAG):拓扑排序仅适用于有向无环图。DAG 是一种特殊的有向图,其中不存在从某个顶点沿边可以返回该顶点的环,即不存在循环依赖。
- 线性排序:拓扑排序为图中的顶点提供了一种线性排列方式,使得每个有向边的起点都排在终点的前面。
拓扑排序的应用
- 任务调度问题:如果某些任务必须在其他任务之前完成,拓扑排序可以用于确定任务的执行顺序。
- 编译器中的依赖管理:编译时,某些模块必须先于其他模块编译,拓扑排序可以确定模块的编译顺序。
- 课程安排问题:在有前置课程要求的学习计划中,拓扑排序能够找到一个合法的课程安排顺序。
拓扑排序的两种实现方法
- Kahn's 算法(基于入度的广度优先搜索 BFS)
- 基于深度优先搜索(DFS)
1. Kahn's 算法(基于入度的 BFS)
Kahn's 算法是一种基于节点入度的算法,通过逐步移除入度为 0 的节点来生成拓扑排序。入度为 0 的节点意味着没有其他节点依赖它,因此可以将其放入排序序列中。
算法步骤
-
计算每个顶点的入度:
- 入度是指指向该顶点的边的数量。对于每个顶点,计算它的入度。
-
初始化入度为 0 的顶点队列:
- 将所有入度为 0 的顶点加入一个队列。
-
广度优先遍历:
- 从队列中取出一个入度为 0 的顶点,将其添加到拓扑排序的结果中。
- 对于该顶点的每个邻居,将它们的入度减 1。如果某个邻居的入度减为 0,将其加入队列。
- 重复此过程直到队列为空。
-
检查是否存在环:
- 如果最终排序中的顶点数量少于图中的顶点数量,说明图中存在环,无法进行拓扑排序。
Kahn's 算法的伪代码
function KahnTopologicalSort(Graph):in_degree = [0] * V // 初始化所有顶点的入度为 0// 计算每个顶点的入度for each edge (u, v) in Graph:in_degree[v] += 1// 将所有入度为 0 的顶点加入队列queue = []for i = 0 to V-1:if in_degree[i] == 0:queue.append(i)topological_order = []// 广度优先遍历while queue is not empty:u = queue.pop(0)topological_order.append(u)// 对 u 的所有邻居进行处理for each neighbor v of u:in_degree[v] -= 1if in_degree[v] == 0:queue.append(v)// 检查是否存在环if len(topological_order) != V:return "Graph has a cycle"return topological_order
2. 基于深度优先搜索(DFS)的拓扑排序
DFS 方法通过递归访问每个顶点及其邻居,并在完成对邻居的递归访问后,将顶点加入到排序结果中。因此,深度优先搜索方法的拓扑排序是“后序遍历”的一种变形。
算法步骤
-
标记节点:
- 使用一个布尔数组
visited[]
来记录每个节点是否已经被访问。
- 使用一个布尔数组
-
DFS 遍历:
- 对每个未被访问的节点调用 DFS,递归访问其邻居。当某个顶点的所有邻居都被处理完时,将该顶点放入结果栈中。
-
栈中的节点顺序:
- 由于在处理完一个节点的所有邻居后才将其放入栈,因此栈中的顺序即为拓扑排序的顺序。
DFS 拓扑排序的伪代码
function DFSTopologicalSort(Graph):visited = [False] * V // 初始化所有顶点为未访问stack = []for each vertex v in Graph:if visited[v] == False:DFS(Graph, v, visited, stack)// 返回栈中节点的顺序即为拓扑排序的结果return stack[::-1] // 将栈逆序输出function DFS(Graph, v, visited, stack):visited[v] = True // 标记当前节点已访问// 递归访问所有邻居for each neighbor u of v:if visited[u] == False:DFS(Graph, u, visited, stack)// 当前节点处理完,放入栈中stack.append(v)
Java 实现
Kahn's 算法的 Java 实现
import java.util.*;public class TopologicalSortKahn {// Kahn 算法实现拓扑排序public static List<Integer> topologicalSort(int V, List<List<Integer>> adj) {int[] inDegree = new int[V];List<Integer> topOrder = new ArrayList<>();Queue<Integer> queue = new LinkedList<>();// 计算每个节点的入度for (int i = 0; i < V; i++) {for (int neighbor : adj.get(i)) {inDegree[neighbor]++;}}// 将所有入度为 0 的节点加入队列for (int i = 0; i < V; i++) {if (inDegree[i] == 0) {queue.add(i);}}// 执行拓扑排序while (!queue.isEmpty()) {int node = queue.poll();topOrder.add(node);// 对邻居的入度进行减 1 操作for (int neighbor : adj.get(node)) {inDegree[neighbor]--;if (inDegree[neighbor] == 0) {queue.add(neighbor);}}}// 检查是否存在环if (topOrder.size() != V) {System.out.println("Graph contains a cycle");return new ArrayList<>();}return topOrder;}public static void main(String[] args) {int V = 6;List<List<Integer>> adj = new ArrayList<>(V);// 初始化邻接表for (int i = 0; i < V; i++) {adj.add(new ArrayList<>());}// 添加有向边adj.get(5).add(2);adj.get(5).add(0);adj.get(4).add(0);adj.get(4).add(1);adj.get(2).add(3);adj.get(3).add(1);// 执行拓扑排序List<Integer> result = topologicalSort(V, adj);// 输出结果if (!result.isEmpty()) {System.out.println("拓扑排序结果: " + result);}}
}
DFS 方法的 Java 实现
import java.util.*;public class TopologicalSortDFS {// DFS 实现拓扑排序public static List<Integer> topologicalSort(int V, List<List<Integer>> adj) {boolean[] visited = new boolean[V];Stack<Integer> stack = new Stack<>();// 对每个节点执行 DFSfor (int i = 0; i < V; i++) {if (!visited[i]) {dfs(i, visited, stack, adj);}}// 输出栈中的内容即为拓扑排序结果List<Integer> topOrder = new ArrayList<>();while (!stack.isEmpty()) {topOrder.add(stack.pop());}return topOrder;}private static void dfs(int node, boolean[] visited, Stack<Integer> stack, List<List<Integer>> adj) {visited[node] = true;// 访问所有邻居for (int neighbor : adj.get(node)) {if (!visited[neighbor]) {dfs(neighbor, visited, stack, adj);}}// 将当前节点加入栈中stack.push(node);}public static void main(String[] args) {int V = 6;List<List<Integer>> adj = new ArrayList<>(V);// 初始化邻接表for (int i = 0; i < V; i++) {adj.add(new ArrayList<>());}// 添加有向边adj.get(5).add(2);adj.get(5).add(0);adj.get(4).add(0);adj.get(4).add(1);adj.get(2).add(3);adj.get(3).add(1);// 执行拓扑排序List<Integer> result = topologicalSort(V, adj);// 输出结果System.out.println("拓扑排序结果: " + result);}
}
算法比较
算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
---|---|---|---|
Kahn's 算法 (BFS) | O(V+E) | O(V) | 适用于需要显式维护入度的场景 |
DFS 方法 | O(V+E) | O(V) | 适用于需要递归深度优先搜索的场景 |
拓扑排序总结
- Kahn's 算法:使用入度来逐步选出可以放入排序中的节点,适合广度优先遍历。
- DFS 方法:递归访问图中的节点,后序遍历得到排序,适合深度优先遍历。
- 有向无环图是拓扑排序的前提,如果图中存在环,则无法生成拓扑排序。