递归深度优先搜索算法

Question

递归深度优先搜索算法

pythonalgorithmrecursiondepth-first-search

4

我将尝试编写一个递归深度优先搜索算法，它接受一个表示图的邻接表并打印出顶点的访问顺序。

我的输入是以邻接表形式存储的图：

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循环应该遍历剩余的键值对并将值更改为访问顶点的顺序，但我不确定为什么它没有这样做。

有什么想法吗？

- superfluousAM

由于graph中的第一个键是0，因此您始终在for循环的第一次迭代中发送递归调用dfs(key, count, graph)。尽管我不确定为什么要检查key == 0，或者您的算法应该如何工作。 - Blorgbeard

@Blorgbeard 基本上，我正在获取输入顶点，并标记它们全部为0，以显示它们尚未被访问。如果一个顶点没有被访问过，它将被传递到第二个函数中，然后将0更改为与顶点被访问时对应的数字。由于顶点0首先被访问，其值从0更改为1，然后函数应该继续移动到下一个顶点，将其值从0更改为2，以此类推。 - superfluousAM

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anand S Kumar · Accepted Answer

问题在于你的 dfs() 函数中，没有检查节点是否已经被访问过，而是在 if 条件语句中检查节点是否为 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}