图的拓扑排序

图的拓扑排序（Topological Sorting）是一种线性排序，用于有向无环图（Directed Acyclic Graph，DAG）。拓扑排序将图中的顶点排成一个线性序列，使得对于每一条有向边 (u, v)，顶点 u 都排在顶点 v 之前。常见的拓扑排序算法有 Kahn 算法和基于深度优先搜索（DFS）的算法。

1. Kahn 算法

Kahn 算法是一种基于入度的贪心算法，逐步选择入度为 0 的顶点并移除其出边。

步骤：

1. 计算每个顶点的入度。
2. 初始化一个队列，将所有入度为 0 的顶点入队。
3. 重复以下步骤，直到队列为空：
   • 从队列中取出一个顶点，将其添加到拓扑排序结果中。
   • 对该顶点的每条出边，将目标顶点的入度减 1。如果目标顶点的入度变为 0，则将其入队。
4. 如果结果中的顶点数与图中的顶点数相等，则拓扑排序成功，否则图中存在环。

Java实现：

import java.util.*;public class KahnTopologicalSort {static class Graph {int V;List<Integer>[] adjacencyList;Graph(int V) {this.V = V;adjacencyList = new LinkedList[V];for (int i = 0; i < V; i++) {adjacencyList[i] = new LinkedList<>();}}void addEdge(int src, int dest) {adjacencyList[src].add(dest);}List<Integer> topologicalSort() {int[] inDegree = new int[V];for (int i = 0; i < V; i++) {for (int neighbor : adjacencyList[i]) {inDegree[neighbor]++;}}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < V; i++) {if (inDegree[i] == 0) {queue.add(i);}}List<Integer> topoOrder = new ArrayList<>();while (!queue.isEmpty()) {int u = queue.poll();topoOrder.add(u);for (int neighbor : adjacencyList[u]) {inDegree[neighbor]--;if (inDegree[neighbor] == 0) {queue.add(neighbor);}}}if (topoOrder.size() != V) {throw new RuntimeException("The graph has at least one cycle");}return topoOrder;}}public static void main(String[] args) {Graph graph = new Graph(6);graph.addEdge(5, 2);graph.addEdge(5, 0);graph.addEdge(4, 0);graph.addEdge(4, 1);graph.addEdge(2, 3);graph.addEdge(3, 1);List<Integer> topoOrder = graph.topologicalSort();System.out.println("Topological Sort: " + topoOrder);}
}

2. 基于深度优先搜索的拓扑排序

DFS 算法通过递归访问顶点，确保每个顶点在所有邻居顶点之后加入结果列表。

步骤：

1. 初始化一个布尔数组，标记每个顶点是否被访问。
2. 初始化一个栈，用于存储拓扑排序结果。
3. 对每个顶点执行以下步骤（如果尚未被访问）：
   • 从该顶点开始进行 DFS。
   • 在 DFS 过程中，将当前顶点标记为已访问，并递归访问所有未被访问的邻居顶点。
   • DFS 完成后，将当前顶点压入栈。
4. 从栈顶依次弹出顶点，形成拓扑排序结果。

Java实现：

import java.util.*;public class DFSTopologicalSort {static class Graph {int V;List<Integer>[] adjacencyList;Graph(int V) {this.V = V;adjacencyList = new LinkedList[V];for (int i = 0; i < V; i++) {adjacencyList[i] = new LinkedList<>();}}void addEdge(int src, int dest) {adjacencyList[src].add(dest);}void topologicalSortUtil(int v, boolean[] visited, Stack<Integer> stack) {visited[v] = true;for (int neighbor : adjacencyList[v]) {if (!visited[neighbor]) {topologicalSortUtil(neighbor, visited, stack);}}stack.push(v);}List<Integer> topologicalSort() {Stack<Integer> stack = new Stack<>();boolean[] visited = new boolean[V];for (int i = 0; i < V; i++) {if (!visited[i]) {topologicalSortUtil(i, visited, stack);}}List<Integer> topoOrder = new ArrayList<>();while (!stack.isEmpty()) {topoOrder.add(stack.pop());}return topoOrder;}}public static void main(String[] args) {Graph graph = new Graph(6);graph.addEdge(5, 2);graph.addEdge(5, 0);graph.addEdge(4, 0);graph.addEdge(4, 1);graph.addEdge(2, 3);graph.addEdge(3, 1);List<Integer> topoOrder = graph.topologicalSort();System.out.println("Topological Sort: " + topoOrder);}
}

结论

• Kahn算法：通过计算入度并逐步移除入度为 0 的顶点来实现拓扑排序。适用于在线性时间内完成排序，但需要额外的空间来存储入度。
• DFS算法：通过递归访问顶点来实现拓扑排序。适用于递归解决问题的场景，但需要维护递归栈和结果栈。