Поиск в ширину (Breadth-first Search)
Published: 2023-11-25 22:06:59


Еще одним алгоритмом обхода графа является поиск в ширину. Смотри также мою статью про обход в глубину: [DFS](https://dev.to/faangmaster/dfs-depth-first-searchpoisk-v-ghlubinu-28ea).

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

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

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

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

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

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

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

```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:

```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)
```

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

![](https://cdn-images-1.medium.com/max/2000/1*jQ5Gbc1r8ZDErByX0Vv6rw.png)

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

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

![](https://cdn-images-1.medium.com/max/2902/1*yKCSZCupY_X-QyaJgvEOUw.png)

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

![](https://cdn-images-1.medium.com/max/2902/1*y68RpB8YHClr35u45jiIiw.png)

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

![](https://cdn-images-1.medium.com/max/2902/1*VBN5Ej1340pnf1quCCjGUw.png)

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

![](https://cdn-images-1.medium.com/max/2902/1*UpDZVlP-YcSZ6n0gg_LShA.png)

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

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

![](https://cdn-images-1.medium.com/max/3126/1*iTj4oKuVKDi9u7_vFyItdw.png)

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

![](https://cdn-images-1.medium.com/max/3126/1*CYPKsdWOQsXzf35u5dxiLg.png)

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

![](https://cdn-images-1.medium.com/max/3126/1*rDfo4gwAsKMj4gT42-rwBg.png)