Поиск в ширину (Breadth-first Search)

Еще одним алгоритмом обхода графа является поиск в ширину. Смотри также мою статью про обход в глубину: DFS.

Поиск в ширину обходит граф “по слоям”. Сначала начальную вершину, потом всех ее соседей. Потом всех соседей соседей и т.д.

Реализация обхода в ширину использует очередь.

Алгоритм следующий.

1. Помещаем начальную вершину в очередь. Помечаем ее как посещенную.

2. Пока очередь не пустая. Достаем вершину из очереди. Посещаем ее.

3. Для всех соседей, которые мы еще не посетили: помечаем их как посещенные и помещаем в очередь.

Реализация на Java:

    void bfs(Node root) {
        if (root == null) {
          return;
        }
        Set<Node> visited = new HashSet<>();
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);
        visited.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            visit(node);
            for (Node neighbour : node.getNeighbours()) {
              if (!visited.contains(neighbour)) {
                visited.add(neighbour);
                queue.add(neighbour);
              }
            }
        }
    }

Реализация на Python:

    def bfs(root):
      queue = []
      visited = set()
      queue.append(root)
      visited.add(root)
      while queue:
       node = queue.pop(0)
       visit(node)
       for neighbour in node.neighbours:
        if neighbour not in visited:
          queue.append(neighbour)
          visited.add(neighbour)

Давайте посмотрим как будет работать поиск в ширину на конкретном примере:

Зеленым я буду помечать уже посещенные вершины.

Вначале помещаем root в очередь и помечаем ее как посещенную:

Далее попадаем в цикл. Достаем из очереди 1. Посещаем ее. У нее 3 соседей: 2, 3, 4. Все они еще не посещенные. Помещаем их в очередь и помечаем их как посещенные.

На следующей итерации цикла достаем 2 из очереди. Посещаем ее. У нее соседи: 1, 5, 6. 1 уже посещена. Поэтому в очередь помещаем 5 и 6. Помечаем их как visited.

Далее достаем 3 из очереди. Посещаем ее. У нее соседи 1 и 7. 1 уже помечена как visited. Помещаем 7 в очередь и помечаем ее как visited.

Далее достаем 4 из очереди. Посещаем ее. У нее соседи 1, 8, 9, 10.

1 уже помечена как visited. Помечаем 8, 9, 10 и помещаем их в очередь.

Далее достаем 5. Посещаем ее. У нее соседи 2 и 11. 2 уже помечена. Помечаем 11 и помещаем в очередь.

Для всех оставшихся в очереди ситуция похожая. Достаем из очереди. Посещаем. Все соседи уже помечены, поэтому новые вершины в очередь не добавляем. И так до тех пор, пока очередь не будет пуста.