递归深度优先搜索算法

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:，所以它不断递归为0日节点，即使它已经被访问过。

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

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

示例 -

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}