Question

помогите реализовать bfs на питоне

Answer 1

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