python - 递归深度优先搜索算法

Question

我正在尝试编写一个递归深度优先搜索算法，它采用表示图形的邻接列表并打印顶点的访问顺序。

我的输入是一个存储为邻接表的图:

graphAL2 = {0 : [1,2,3],
        1 : [0,3,4],
        2 : [0,4,5],
        3 : [0,1,5],
        4 : [1,2],
        5 : [2,3] }

从那里开始，我编写了构成程序的 2 个函数，一个主要函数和一个辅助函数。

import sys

def main():
count = 0
graphAL2v = {}

for key, value in graphAL2.items():
    graphAL2v[key] = 0

print graphAL2v

for key in graphAL2v: 
    if key == 0: 
        dfs(key, count, graphAL2v)
def dfs(v, count, graph):
    count = count + 1 
    graph[v] = count
    for key in graph: 
        if key == 0:
            dfs(key, count, graph)
if __name__ == "__main__":
    sys.exit(main())

现在如果我运行它，输出是:

{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
{0: 1, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}

第一个与键0配对的值一直递增直到

RuntimeError: maximum recursion depth exceeded

达到了。 for 循环应该遍历其余的键对值并将值更改为访问顶点的顺序，但我不确定为什么不这样做。

有什么想法吗？

Answer 1

问题出在您的 dfs() 函数中，您没有检查该节点是否已经被访问过，而是检查该节点是否为 0 或不在 if 条件 - if key == 0: 中，因此它会继续递归 0th 节点，即使它已经被访问过.

由于 0 节点的无限递归，当达到最大递归限制时，它会弹出错误 - RuntimeError: maximum recursion depth exceeded。

您应该检查 graph` 中 key 的值，而不是图表本身。而且您也没有在任何地方使用邻接列表。您应该基于邻接表而不是访问的字典进行循环。

例子-

graphAL2 = {0 : [1,2,3],
        1 : [0,3,4],
        2 : [0,4,5],
        3 : [0,1,5],
        4 : [1,2],
        5 : [2,3] }

def main():
    count = 0
    graphAL2v = {}

    for key, value in graphAL2.items():
         graphAL2v[key] = 0

    print(graphAL2v)

    for key in graphAL2v: 
        if graphAL2v[key] == 0: 
            dfs(key, count, graphAL2, graphAL2v)

    print(graphAL2v)


def dfs(v, count, graphal, graphvisited):
    count = count + 1
    print("Visiting ",v)
    graphvisited[v] = count
    for elem in graphal[v]:
        if not graphvisited[elem]:
            dfs(elem, count, graphal, graphvisited)

main()

演示 -

{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
Visiting  0
Visiting  1
Visiting  3
Visiting  5
Visiting  2
Visiting  4
{0: 1, 1: 2, 2: 5, 3: 3, 4: 6, 5: 4}