Pythonの深さ優先検索（DFS）コード

Question

以下の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) 

出力：

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

Answer 1

私はあなたがそこにインデントの問題を抱えていると思います。あなたのコードを仮定すると、次のようになります

は

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) 

Answer 2

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