Не могли бы вы сообщить мне, что неправильно в приведенном ниже коде 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']
Я думаю, что у вас проблема с отступами. Предположим, что ваш код выглядит следующим образом:
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)
Без рекурсии: ``python 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() возврат посещённых
print (dfs(graph1, 'A'))
Вывод:
['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']
Реализация DFS в Python
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()
Источник :: this