def BFS(graph, start): from queue import Queue visited = set() to_visit = Queue() to_visit.put(start) visited.add(start) while not to_visit.empty(): node = to_visit.get() for child in graph[node]: if child not in visited: visited.add(child) to_visit.put(child) return visited
Answers & Comments
Verified answer
Python 3У меня находится компонента связности в графе, представленном списком смежности.
graph = {'a': ['b', 'c', 'e'], 'b': ['a', 'c'], 'c': ['a', 'b', 'e'], 'd': [], 'e': ['a', 'c']}
def BFS(graph, start):
from queue import Queue
visited = set()
to_visit = Queue()
to_visit.put(start)
visited.add(start)
while not to_visit.empty():
node = to_visit.get()
for child in graph[node]:
if child not in visited:
visited.add(child)
to_visit.put(child)
return visited
print(BFS(graph, 'a'))
print(BFS(graph, 'd'))
Вывод:
{'b', 'c', 'e', 'a'}
{'d'}