Bfs — алгоритм обхода графа в ширину

BFS — алгоритм обхода графа в ширину

""" ****** Стандартный алгоритм обхода графа в ширину (bfs). ****
 Алгоритм работает следующим образом:
1. Начните с размещения любой вершины графа в конце очереди.
2. Возьмите передний элемент очереди и добавьте его в список посещенных.
3. Создайте список смежных узлов этой вершины. 
 Добавьте те, которых нет в списке посещенных, в конец очереди.
4. Продолжайте повторять шаги 2 и 3, пока очередь не опустеет. 

"""



graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = [] # List to keep track of visited nodes.
queue = []   # Initialize a queue

def bfs(visited, graph, node):
    global queue
    visited.append(node)
    queue.append(node)

    while queue:
        s = queue.pop(0)
        print (s, end = " ")

        for neighbour in graph[s]:
            if neighbour not in visited:
                visited.append(neighbour)
                queue.append(neighbour)

# Driver Code
bfs(visited, graph, 'A')