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

-2

您能否让我知道以下DFS代码中的不正确内容。它给出了正确的结果AFAIK，但我不知道它什么时候会失败。python中的深度优先搜索（DFS）代码

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']

来源

2017-04-15 Vicky

首先：不要使用'global's避免他们尽可能！ –

DFS是* search *算法，但有*没有定义目标*您正在寻找... –

感谢您的回应.. visited = [] def dfs（graph，node，visited）： if node不是在访问： visited.append（节点）对于n在图形[节点]： DFS（图表中，n，访问） DFS（graph1， 'A'，访问）打印（受访） – Vicky

我认为你有一个压痕问题存在。假设你的代码如下所示：

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)

来源

2017-05-09 11:55:39 purpletentacle

应该更新的代码包含变量'visited'作为'dict'或'list'吗？ – Sudarshan

更新，谢谢！ – purpletentacle

在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): 
     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()

来源:: this

来源

2018-01-12 05:01:00 harrypotter0

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

回答

相关问题