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 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 = 6
B = [[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 的节点索引。

改进的深度优先搜索

脚步

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

代码实现

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 code
A = 6
B = [[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/小程序/网站源码资源！