首页 文章

递归深度优先搜索算法

提问于
浏览 次
4

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

我的输入是存储为邻接列表的图形：

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配对的第一个值一直递增，直到a

RuntimeError: maximum recursion depth exceeded

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

有什么想法吗？

python algorithm recursion depth-first-search

1 回答

  • 4

    问题出在您的 dfs() 函数中，您没有检查该节点是否已被访问过，您正在检查该节点是否 0 在 if 条件下 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}
    回复于

相关问题