拓扑排序，含解析、源码

**标题：** 拓扑排序：原理、算法与实现 **摘要：** 本文将介绍拓扑排序的概念、算法和实现。通过 JavaScript 和 Python 的示例代码，我们将深入理解拓扑排序的工作原理和应用。 **目录：** 1. 引言 2. 拓扑排序简介 3. 拓扑排序算法 4. JavaScript 实现 5. Python 实现 6. 结论 7. 参考文献 **引言：** 在图论中，拓扑排序是一个重要的概念。它用于对有向无环图（DAG）的节点进行排序，使得对于每一条有向边 (u, v)，u 都在 v 的前面。这种排序方法在诸如任务调度、课程安排等许多实际问题中都有广泛应用。 **拓扑排序简介：** 拓扑排序主要分为两个步骤：首先，找出图中所有的入度为 0 的节点（即没有前置任务），然后将这些节点依次从图中删除，并更新其他节点的入度。这个过程会一直重复，直到图为空或存在环。 **拓扑排序算法：** 这里我们介绍两种常见的拓扑排序算法：Kahn 算法和深度优先搜索（DFS）算法。 * **Kahn 算法：** 1. 找出所有入度为 0 的节点，并加入队列。 2. 从队列中取出一个节点，并输出。 3. 从图中删除该节点和它的出边。 4. 重复步骤 1-3，直到队列为空。 * **深度优先搜索（DFS）：** 1. 对图进行深度优先搜索，每次访问一个节点就输出。 2. 在搜索过程中，维护一个 stack，将访问过的节点压入 stack。 3. 当访问一个节点的所有子节点后，将该节点弹出 stack 并输出。 4. 重复步骤 1-3，直到图为空或存在环。 **JavaScript 实现：** 这里是一个简单的拓扑排序的 JavaScript 实现，使用了 Kahn 算法： ```javascript function topoSort(graph) { const inDegree = {}; // 记录每个节点的入度 const queue = []; // 存储入度为0的节点 const result = []; // 存储拓扑排序的结果 // 初始化入度数组 for (const node in graph) { inDegree[node] = 0; for (const neighbor in graph[node]) { inDegree[neighbor]++; // 计算每个节点的入度 } } // 将入度为0的节点加入队列 for (const node in graph) { if (inDegree[node] === 0) { queue.push(node); } } // 依次取出队列中的节点，进行拓扑排序 while (queue.length > 0) { const currentNode = queue.shift(); // 取出一个节点 result.push(currentNode); // 将该节点加入结果数组 for (const neighbor in graph[currentNode]) { inDegree[neighbor]--; // 将该节点的所有邻居的入度减1 if (inDegree[neighbor] === 0) { // 如果邻居的入度为0，加入队列 queue.push(neighbor); } } } return result; // 返回拓扑排序结果 } ``` **Python 实现：** 以下是一个使用深度优先搜索（DFS）算法的拓扑排序的 Python 实现： ```python from collections import defaultdict class Graph: def __init__(self, vertices): self.graph = defaultdict(list) self.V = vertices def addEdge(self, u, v): self.graph[u].append(v) def topologicalSortUtil(self, v, visited, stack): visited[v] = True for i in self.graph[v]: if visited[i] == False: self.topologicalSortUtil(i, visited, stack) stack.insert(0, v) def topologicalSort(self): visited = [False] * (self.V) stack = [] for i in range(self.V): if visited[i] == False: self.topologicalSortUtil(i, visited, stack) print(stack) g = Graph(6) g.addEdge(5, 2) g.addEdge(5, 0) g.addEdge(4, 0) g.addEdge(4, 1) g.addEdge(2, 3) g.addEdge(3, 1) print("拓扑排序结果：") g.topologicalSort() ``` 这个程序首先创建一个有向图，然后使用深度优先搜索遍历该图，每次遍历完成后将节点推入堆栈。最后打印堆栈中的顺序即为拓扑排序的结果。 **结论：** 通过上述的 JavaScript 和 Python 实现，我们可以看到拓扑排序的核心思想是找到有向无环图（DAG）中的入度为 0 的节点，然后依次删除这些节点，并更新它们的邻居节点的入度。这个过程一直重复，直到图为空或存在环。在实现中，我们使用了两种常见的算法：Kahn 算法和深度优先搜索（DFS）算法。无论是哪种算法，都需要用到一个数据结构来存储节点的入度，以及另一个数据结构来存储排序的结果。在 JavaScript 实现中，我们使用了对象来存储节点的入度，数组来存储排序的结果，而 Python 实现中，我们使用了 defaultdict 来存储节点的入度，列表来存储排序的结果。 **参考文献：** [1]拓扑排序的算法和应用，[URL:https://www.cnblogs.com/xdp-gcl/p/3495897.html]。 [2]深度优先搜索和拓扑排序，[URL:https://www.cnblogs.com/fengzheng/p/3492589.html]。 [3]拓扑排序的实现和使用，[URL:https://www.jianshu.com/p/1062989f1d38]。