python中的深度优先搜索（DFS）代码
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/43430309/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Depth-first search (DFS) code in python
提问by Vicky
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.
您能否让我知道以下 DFS 代码中有什么不正确。它给出了正确的结果 AFAIK，但我不知道它什么时候会失败。
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)
Output:
输出：
['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']
回答by Juan Leni
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)
I would say a couple of things:
我想说几件事：
- Avoid globals if you can
- Instead of a list for visited, use a set
- 如果可以，请避免使用全局变量
- 使用集合代替访问列表
plus:
加：
- This will not work for forests but I assume you already know that
- It will fail if you reference a node that does not exist.
- 这不适用于森林，但我想你已经知道了
- 如果您引用不存在的节点，它将失败。
Updated code:
更新代码：
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)
回答by gaetano
Without recursion:
没有递归：
def dfs(graph, node):
visited = [node]
stack = [node]
while stack:
node = stack[-1]
if node not in visited:
visited.extend(node)
remove_from_stack = True
for next in graph[node]:
if next not in visited:
stack.extend(next)
remove_from_stack = False
break
if remove_from_stack:
stack.pop()
return visited
print (dfs(graph1, 'A'))
Output:
输出：
['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']
回答by Saurabh
Here's an iterative (non-recursive) implementation of a DFS:
这是 DFS 的迭代（非递归）实现：
def dfs_iterative(graph, start_vertex):
visited = set()
traversal = []
stack = [start_vertex]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
traversal.append(vertex)
stack.extend(reversed(graph[vertex])) # add vertex in the same order as visited
return traversal
test_graph = {
'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']
}
print(dfs_iterative(test_graph, 'A'))
Output:
输出：
['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']
['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']
回答by Sneha Mule
graph = {'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']}
def dfs(s,d):
def dfs_helper(s,d):
if s == d:
return True
if s in visited :
return False
visited.add(s)
for c in graph[s]:
dfs_helper(c,d)
return False
visited = set()
return dfs_helper(s,d)
dfs('A','E') ---- True
dfs('A','M') ---- False
回答by Aslesha Ch
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
def DFS(self,v,vertex):
visited = [False]*vertex
print(self. graph)
# print(len(self.graph),"+++")
self.DFSUtil(v,visited)
def DFSUtil(self,v,visited):
visited[v]=True
print(v)
for i in self.graph[v]:
if visited[i] == False:
# print(visited)
self.DFSUtil(i,visited)
g= Graph()
vertex=7
g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(0,6)
g.addEdge(0,5)
g.addEdge(5,3)
g.addEdge(5,4)
g.addEdge(4,3)
g.addEdge(6,4)
g.DFS(0,vertex)
This is the modification for the above code because that doesn't work with in all cases.
We have to specify the number of vectors and then give edges manually.
这是对上述代码的修改，因为这不适用于所有情况。
我们必须指定向量的数量，然后手动给出边缘。
回答by Akash Kandpal
DFS implementation in Python
Python中的DFS实现
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
def DFSUtil(self, v, visited):
visited[v]=True
print(v)
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
def DFS(self):
V = len(self.graph)
visited = [False]*(V)
for i in range(V):
if visited[i] == False:
self.DFSUtil(i, visited)
# Driver code
# Create a graph given in the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print("Following is Depth First Traversal")
g.DFS()
Source :: this
来源：：这个
