Python栈的应用：图的深度优先遍历和拓扑排序

2023-04-10 00:00:00 遍历排序拓扑

图的深度优先遍历：

深度优先遍历是一种重要的图遍历方法，它遍历图的方式是先访问出发节点，然后依次沿着出发节点的每个未访问过的邻节点深入遍历，直到所有节点都被访问为止。

实现深度优先遍历的常用方法是使用栈，将出发节点入栈，并依次将其邻节点入栈，直到遍历完所有节点。

下面是Python的实现代码：

#定义邻接表存储图
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

#深度优先遍历函数
def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

print(dfs(graph, 'A')) #输出{'E', 'D', 'F', 'A', 'C', 'B'}

拓扑排序：

拓扑排序是一种有向无环图的遍历方法，它可以将有向无环图中所有节点排序，使得对于每条有向边 (u, v)，节点 u 都排在节点 v 的前面。

实现拓扑排序的常用方法是使用深度优先遍历和逆拓扑排序。

Python代码实现：

#定义邻接表存储图
graph = {'A': set(['D']),
         'B': set(['D', 'E']),
         'C': set(['E']),
         'D': set(['F']),
         'E': set(['F']),
         'F': set([])}

#深度优先遍历函数，返回逆拓扑排序结果
def dfs_topsort(graph, start, visited, result):
    visited.add(start)
    for neighbor in graph[start]:#遍历邻节点
        if neighbor not in visited:
            dfs_topsort(graph, neighbor, visited, result)
    result.append(start)#逆序添加到拓扑序列的开头

#逆拓扑排序函数，返回拓扑序列
def topsort(graph):
    visited, result = set(), []
    for start in graph:
        if start not in visited:
            dfs_topsort(graph, start, visited, result)
    return result[::-1]

print(topsort(graph)) #输出['C', 'B', 'A', 'D', 'E', 'F']

注意，此处的输出结果是逆拓扑序列，需要对其进行逆序。

相关文章