python中的深度优先搜索（DFS）代码

本文介绍了python中的深度优先搜索（DFS）代码的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

请让我知道下面DFS代码中的错误之处。它给出正确的结果AFAIK，但我不知道何时会失败。

Can you please let me know what is incorrect in below DFS code. It's giving correct result AFAIK, but I don't know when it will fail.

graph1 = { 'A' : ['B','S'], 'B' : ['A'], 'C' : ['D','E','F','S'], 'D' : ['C'], 'E' : ['C','H'], 'F' : ['C','G'], 'G' : ['F','S'], 'H' : ['E','G'], 'S' : ['A','C','G'] } visited = [] def dfs(graph,node): global visited if node not in visited: visited.append(node) for n in graph[node]: dfs(graph,n) dfs(graph1,'A') print(visited)

输出：

['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']

推荐答案

我认为您有一个缩进问题。假设您的代码如下所示：

I think you have an indentation problem there. Assuming your code looks like this:

graph1 = { 'A' : ['B','S'], 'B' : ['A'], 'C' : ['D','E','F','S'], 'D' : ['C'], 'E' : ['C','H'], 'F' : ['C','G'], 'G' : ['F','S'], 'H' : ['E','G'], 'S' : ['A','C','G'] } visited = [] def dfs(graph,node): global visited if node not in visited: visited.append(node) for n in graph[node]: dfs(graph,n) dfs(graph1,'A') print(visited)

我会说两件事：

• 如果可以的话，请避免使用全局变量
• 不要使用访问列表，而是使用一组

加：

• 这不适用于森林，但我想您已经知道了
• 如果引用的节点不存在，则会失败。

更新的代码：

graph1 = { 'A' : ['B','S'], 'B' : ['A'], 'C' : ['D','E','F','S'], 'D' : ['C'], 'E' : ['C','H'], 'F' : ['C','G'], 'G' : ['F','S'], 'H' : ['E','G'], 'S' : ['A','C','G'] } def dfs(graph, node, visited): if node not in visited: visited.append(node) for n in graph[node]: dfs(graph,n, visited) return visited visited = dfs(graph1,'A', []) print(visited)