python - 如何使用 DFS 在有向图中递归查找路径

Question

我似乎无法弄清楚如何将我的解决方案转换为在有向图而不是无向图上工作。

我目前有两种不同的方法；迭代和递归。

迭代：

def dfs_iterative(graph, start_vertex):
    visited = set()
    traversal = []
    stack = [start_vertex]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            traversal.append(vertex)
            stack.extend(reversed(graph[vertex]))   
    return traversal

递归：

def dfs_recursive(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs_recursive(graph,n, visited)
    return visited

当根据下面显示的输出测试这些时graph，输出始终是Undirected。

graph = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}
# returns ['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']

我想首先弄清楚如何更改我的代码，使我的图的边缘指向一个方向，然后如何调用这些函数来获取图中的其余不同路径。

如果我不得不猜测后者的一些伪代码，我会假设

Call function with random vertex
    store result in Dict
    repeat while result not in Dict
    Repeat recursively 

可以迭代完成吗？

标签： pythonrecursiongraphiterationdepth-first-search