递归深度优先搜索算法

Question

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

我的输入是一个以邻接表形式存储的图:

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

从那里，我写了两个函数，一个主函数和一个辅助函数，组成了程序。

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()函数中，你没有检查节点是否已经被访问过，你正在检查节点是否在if条件下是0 - if key == 0:，所以它继续递归0节点，即使它已经被访问过。

由于0节点的这种不确定递归，当达到最大递归极限时，它会弹出错误- RuntimeError: maximum recursion depth exceeded。

你应该从图'中检查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}