DEV Community

faangmaster
faangmaster

Posted on

Поиск в ширину (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);
              }
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

Реализация на 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)
Enter fullscreen mode Exit fullscreen mode

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

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

Вначале помещаем 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 и помещаем в очередь.

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

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up