七爪源码：拓扑排序-Python

BFS 和 DFS 实现

DAG 的拓扑排序是其节点的部分线性排序，因此如果该图有一条从 u 指向 v 的边，则 u 应该放在 v 之前的排序中。部分排序在许多情况下非常有用。调度问题，依赖解决方案。

一些有用的图表术语

• indegree - 指向它的边数。
• outdegree - 从顶点向外延伸的边数。
• Source Vertex— 没有边指向它的顶点。它的边缘只指向外面。
• Sink Vertex — 没有出边的顶点。它的边缘只指向它。

卡恩算法 (BFS)

脚步

1. 将所有节点的入度存储在图中。
2. 识别入度为 0 的节点。将每个节点添加到将被迭代的队列中。
3. 当包含入度为 0 的节点的集合不为空时，删除一个节点。将节点存储在结果列表中。对于移除的每个节点，迭代其边缘，递减边缘上每个目标节点的入度。如果一个节点现在的入度为 0，则按照步骤 2 将其添加到队列和列表中。
4. 最后，返回每个节点附加到的列表。这将包含节点的拓扑排序。

代码实现

from collections import defaultdictclassGraph:def__init__(self, vertices):self.graph = defaultdict(list)self.V = verticesdefadd_edge(self, u, v):self.graph[u-1].append(v-1)deftopological_sort(self):
        in_degree = [0]*(self.V)
        visited = [0]*(self.V)foriinself.graph:forjinself.graph[i]:
                in_degree[j]  =1top_order = []
        queue = []
        from heapq import heappush, heappopforiinrange(self.V):ifin_degree[i] ==0:
                heappush(queue, i)whilequeue:u = heappop(queue)ifnotvisited[u]:
                top_order.append(u 1)foriinself.graph[u]:
                    in_degree[i] -=1ifin_degree[i] ==0:
                        heappush(queue, i)
                visited[u] =1returntop_orderDriver codeA =6B = [[6,3], [6,1], [5,1], [5,2], [3,4], [4,2]]graph = Graph(A)foru, vinB:graph.add_edge(u, v)
        
res = graph.topological_sort()
print(res)[5, 6, 1, 3, 4, 2]

在上面的实现中，我使用了 heapq，因为我想确保结果在字典上是最小的，以防我们有多个订单。 另外，我使用了（u-1 和 v-1），因为我使用的是基于 1 的节点索引。

改进的深度优先搜索

脚步

1. 从任何顶点开始并在其上调用 DFS 函数。
2. 继续沿着该路径遍历，直到找到一个没有进一步出边的节点。
3. 将其添加到拓扑排序中（我们将其插入堆栈中第 0 个索引处，否则我们将获得相反的顺序）。
4. 回溯到具有更多未访问后代的前一个节点。
5. 继续，直到您访问了所有节点。

代码实现

from collections import defaultdictclassGraph:def__init__(self, vertices):self.graph = defaultdict(list)self.V = verticesdefadd_edge(self, u, v):self.graph[u-1].append(v-1)defhelper(self,u,visited, res):
        visited[u] = Trueforiinself.graph[u]:ifvisited[i] ==False:self.helper(i, visited, res)
        res.insert(0, u 1)deftopological_sort(self):
        visited = [False]*self.V
        res =[]foriinreversed(range(self.V)):ifvisited[i] ==False:self.helper(i, visited, res)returnresDriver codeA =6B = [[6,3], [6,1], [5,1], [5,2], [3,4], [4,2]]
graph = Graph(A)foru, vinB:graph.add_edge(u, v)
        
res = graph.topological_sort()
print(res)[5, 6, 1, 3, 4, 2]

在上面的实现中，我使用了 reversed(range(self.V)) ，因为我想确保结果在字典上是最小的，以防我们有多个订单。

快乐编码！

关注七爪网，获取更多APP/小程序/网站源码资源！