BFS 和 DFS 实现

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

一些有用的图表术语

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

卡恩算法 (BFS)

脚步

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

代码实现

from collections import defaultdict class Graph:    def __init__(self, vertices):        self.graph = defaultdict(list)        self.V = vertices    def add_edge(self, u, v):        self.graph[u-1].append(v-1)    def topological_sort(self):        in_degree = [0]*(self.V)        visited = [0]*(self.V)        for i in self.graph:            for j in self.graph[i]:                in_degree[j] += 1        top_order = []        queue = []        from heapq import heappush, heappop        for i in range(self.V):            if in_degree[i] == 0:                heappush(queue, i)        while queue:            u = heappop(queue)            if not visited[u]:                top_order.append(u+1)                for i in self.graph[u]:                    in_degree[i] -= 1                    if in_degree[i] == 0:                        heappush(queue, i)                visited[u] = 1                return top_order## Driver code  A = 6B = [[6, 3], [6, 1], [5, 1], [5, 2], [3, 4], [4, 2]]graph = Graph(A)for u, v in B:    graph.add_edge(u, v)        res = graph.topological_sort()print(res) # [5, 6, 1, 3, 4, 2]

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

改进的深度优先搜索

脚步

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

代码实现

from collections import defaultdict class Graph:    def __init__(self, vertices):        self.graph = defaultdict(list)        self.V = vertices        def add_edge(self, u, v):        self.graph[u-1].append(v-1)    def helper(self,u,visited, res):        visited[u] = True        for i in self.graph[u]:            if visited[i] == False:                self.helper(i, visited, res)        res.insert(0, u+1)    def topological_sort(self):        visited = [False]*self.V        res =[]        for i in reversed(range(self.V)):            if visited[i] == False:                self.helper(i, visited, res)                        return res## Driver codeA = 6B = [[6, 3], [6, 1], [5, 1], [5, 2], [3, 4], [4, 2]]graph = Graph(A)for u, v in B:    graph.add_edge(u, v)        res = graph.topological_sort()print(res) # [5, 6, 1, 3, 4, 2]

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

快乐编码！

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