拓扑排序：Kahn算法与DFS算法

引言

拓扑排序是有向无环图（DAG）中的一种线性排序，使得对于图中的每一条有向边 ( u \rightarrow v )，顶点 ( u ) 在排序中出现在顶点 ( v ) 之前。本文将详细介绍两种实现拓扑排序的算法：Kahn算法和基于深度优先搜索（DFS）的算法。

目录

1. Kahn算法
2. 基于DFS的算法

Kahn算法

定义

Kahn算法是一种基于入度的拓扑排序算法。该算法通过不断移除入度为0的顶点及其边来构建拓扑排序。

算法步骤

1. 初始化：计算图中所有顶点的入度，并将所有入度为0的顶点添加到一个队列中。
2. 构建排序：从队列中取出一个顶点，将其添加到拓扑排序的结果中，并移除该顶点及其所有出边。对于每个被移除的出边，如果目标顶点的入度减为0，则将该顶点添加到队列中。
3. 检测环：重复步骤2，直到队列为空。如果排序结果中的顶点数量小于图中的顶点数量，则说明图中存在环，无法进行拓扑排序。

示例

假设我们有一个有向无环图，顶点集合为 ({A, B, C, D, E, F})，边集合为 ({(A, C), (B, C), (B, D), (C, E), (D, F), (E, F)})。

Kahn算法实现

下面是用Java实现Kahn算法的代码示例：

import java.util.*;public class KahnAlgorithm {private int vertices; // 顶点数量private List<Integer>[] adjList; // 邻接表public KahnAlgorithm(int vertices) {this.vertices = vertices;adjList = new List[vertices];for (int i = 0; i < vertices; i++) {adjList[i] = new ArrayList<>();}}// 添加边public void addEdge(int src, int dest) {adjList[src].add(dest);}// Kahn算法实现的拓扑排序public void topologicalSort() {int[] inDegree = new int[vertices];for (int i = 0; i < vertices; i++) {for (int dest : adjList[i]) {inDegree[dest]++;}}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < vertices; i++) {if (inDegree[i] == 0) {queue.add(i);}}List<Integer> topOrder = new ArrayList<>();while (!queue.isEmpty()) {int u = queue.poll();topOrder.add(u);for (int neighbor : adjList[u]) {if (--inDegree[neighbor] == 0) {queue.add(neighbor);}}}if (topOrder.size() != vertices) {System.out.println("图中存在环，无法进行拓扑排序");return;}System.out.println("拓扑排序结果：");for (int node : topOrder) {System.out.print(node + " ");}}public static void main(String[] args) {KahnAlgorithm graph = new KahnAlgorithm(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort();}
}

代码注释

1. 类和构造函数：

   public class KahnAlgorithm {private int vertices; // 顶点数量private List<Integer>[] adjList; // 邻接表public KahnAlgorithm(int vertices) {this.vertices = vertices;adjList = new List[vertices];for (int i = 0; i < vertices; i++) {adjList[i] = new ArrayList<>();}}
   

   KahnAlgorithm 类包含图的顶点数量和邻接表，并有一个构造函数来初始化这些变量。

2. 添加边：

   public void addEdge(int src, int dest) {adjList[src].add(dest);
   }
   

   addEdge 方法用于向图中添加边。

3. Kahn算法的拓扑排序：

   public void topologicalSort() {int[] inDegree = new int[vertices];for (int i = 0; i < vertices; i++) {for (int dest : adjList[i]) {inDegree[dest]++;}}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < vertices; i++) {if (inDegree[i] == 0) {queue.add(i);}}List<Integer> topOrder = new ArrayList<>();while (!queue.isEmpty()) {int u = queue.poll();topOrder.add(u);for (int neighbor : adjList[u]) {if (--inDegree[neighbor] == 0) {queue.add(neighbor);}}}if (topOrder.size() != vertices) {System.out.println("图中存在环，无法进行拓扑排序");return;}System.out.println("拓扑排序结果：");for (int node : topOrder) {System.out.print(node + " ");}
   }
   

   topologicalSort 方法实现了Kahn算法，进行拓扑排序。

4. 主函数：

   public static void main(String[] args) {KahnAlgorithm graph = new KahnAlgorithm(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort();
   }
   

   main 方法创建一个图并进行拓扑排序。

Kahn算法的执行过程图解

基于DFS的算法

定义

基于DFS的拓扑排序算法通过递归的方式遍历图的每个顶点，并在访问完所有邻接顶点后将顶点压入栈中，最终从栈顶依次弹出顶点即为拓扑排序结果。

算法步骤

1. 初始化：创建一个栈用于存储排序结果，标记所有顶点为未访问。
2. DFS遍历：对于每个未访问的顶点，进行DFS遍历。递归访问该顶点的所有邻接顶点，访问完毕后将该顶点压入栈中。
3. 构建排序：重复步骤2，直到所有顶点都被访问。最后从栈顶

依次弹出顶点即为拓扑排序结果。

示例

假设我们有一个有向无环图，顶点集合为 ({A, B, C, D, E, F})，边集合为 ({(A, C), (B, C), (B, D), (C, E), (D, F), (E, F)})。

基于DFS的算法实现

下面是用Java实现基于DFS的拓扑排序算法的代码示例：

import java.util.*;public class DFSTopologicalSort {private int vertices; // 顶点数量private List<Integer>[] adjList; // 邻接表public DFSTopologicalSort(int vertices) {this.vertices = vertices;adjList = new List[vertices];for (int i = 0; i < vertices; i++) {adjList[i] = new ArrayList<>();}}// 添加边public void addEdge(int src, int dest) {adjList[src].add(dest);}// 递归实现DFSprivate void DFS(int vertex, boolean[] visited, Stack<Integer> stack) {visited[vertex] = true;for (int neighbor : adjList[vertex]) {if (!visited[neighbor]) {DFS(neighbor, visited, stack);}}stack.push(vertex);}// 基于DFS的拓扑排序public void topologicalSort() {Stack<Integer> stack = new Stack<>();boolean[] visited = new boolean[vertices];for (int i = 0; i < vertices; i++) {if (!visited[i]) {DFS(i, visited, stack);}}System.out.println("拓扑排序结果：");while (!stack.isEmpty()) {System.out.print(stack.pop() + " ");}}public static void main(String[] args) {DFSTopologicalSort graph = new DFSTopologicalSort(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort();}
}

代码注释

1. 类和构造函数：

   public class DFSTopologicalSort {private int vertices; // 顶点数量private List<Integer>[] adjList; // 邻接表public DFSTopologicalSort(int vertices) {this.vertices = vertices;adjList = new List[vertices];for (int i = 0; i < vertices; i++) {adjList[i] = new ArrayList<>();}}
   

   DFSTopologicalSort 类包含图的顶点数量和邻接表，并有一个构造函数来初始化这些变量。

2. 添加边：

   public void addEdge(int src, int dest) {adjList[src].add(dest);
   }
   

   addEdge 方法用于向图中添加边。

3. 递归实现DFS：

   private void DFS(int vertex, boolean[] visited, Stack<Integer> stack) {visited[vertex] = true;for (int neighbor : adjList[vertex]) {if (!visited[neighbor]) {DFS(neighbor, visited, stack);}}stack.push(vertex);
   }
   

   DFS 方法递归访问顶点及其邻接顶点，并在访问完所有邻接顶点后将顶点压入栈中。

4. 基于DFS的拓扑排序：

   public void topologicalSort() {Stack<Integer> stack = new Stack<>();boolean[] visited = new boolean[vertices];for (int i = 0; i < vertices; i++) {if (!visited[i]) {DFS(i, visited, stack);}}System.out.println("拓扑排序结果：");while (!stack.isEmpty()) {System.out.print(stack.pop() + " ");}
   }
   

   topologicalSort 方法实现了基于DFS的拓扑排序，输出拓扑排序结果。

5. 主函数：

   public static void main(String[] args) {DFSTopologicalSort graph = new DFSTopologicalSort(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort();
   }
   

   main 方法创建一个图并进行拓扑排序。

基于DFS算法的执行过程图解

结论

通过上述讲解和实例代码，我们详细展示了Kahn算法和基于DFS的拓扑排序算法的定义、步骤及其实现。希望这篇博客对您有所帮助！

---

如果您觉得这篇文章对您有帮助，请关注我的CSDN博客，点赞并收藏这篇文章，您的支持是我持续创作的动力！

---

关键内容总结：

• Kahn算法的定义和实现
• 基于DFS的拓扑排序算法的定义和实现
• 两种算法的执行过程图解

---

推荐阅读：深入探索设计模式专栏，详细讲解各种设计模式的应用和优化。点击查看：深入探索设计模式。

---

特别推荐：设计模式实战专栏，深入解析设计模式的实际应用，提升您的编程技巧。点击查看：设计模式实战。

如有任何疑问或建议，欢迎在评论区留言讨论。谢谢阅读！