E024. Breadth-first search

e-maxx algorithm original: C/C++ #algorithm #bfs #emaxx #graph #queue #search

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

Static

Источник: e-maxx.ru/algo, страница PDF 82.

Breadth-first search (обход в ширину, breadth-first search) — это один из основных Algorithmusов на Graphах. В результате поиска в ширину находится путь кратчайшей длины в невзвешененном Graphе, т.е. путь, содержащий наименьшее number рёбер.

Algorithmus работает за

, где

— number вершин,

— number рёбер.

Описание Algorithmusа

На Eingabe Algorithmusа подаётся заданный Graph (невзвешенный), и номер стартовой вершины

. Graph может быть

как ориентированным, так и неориентированным, для Algorithmusа это не важно. Сам Algorithmus можно понимать как процесс "поджигания" Graphа: на нулевом шаге поджигаем только вершину

. На

каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей; т.е. за одну итерацию Algorithmusа происходит расширение "кольца огня" в ширину на единицу (отсюда и название Algorithmusа). Более строго это можно представить следующим образом. Создадим очередь

, в которую будут помещаться

горящие вершины, а также заведём булевский Array

, в котором для каждой вершины будем отмечать, горит

она уже или нет (или иными словами, была ли она посещена).

Изначально в очередь помещается только vertex

, и

, а для всех остальных

вершин

. Затем Algorithmus представляет собой цикл: пока очередь не пуста, достать из её головы одну вершину, просмотреть все рёбра, исходящие из этой вершины, и если какие-то из просмотренных вершин ещё не горят, то поджечь их и поместить в конец очереди. В итоге, когда очередь опустеет, обход в ширину обойдёт все достижимые из

вершины, причём до каждой

дойдёт кратчайшим путём. Также можно посчитать длины кратчайших путей (для чего просто надо завести Array

длин путей

), и компактно сохранить информацию, достаточную для восстановления всех этих кратчайших путей

(для этого надо завести Array "предков"

, в котором для каждой вершины хранить номер вершины, по которой мы попали в эту вершину).

Implementierung

Реализуем вышеописанный Algorithmus на языке C++. Eingabeные данные:

vector < vector<int> > g; // Graph

int n; // number вершин

int s; // стартовая vertex (вершины везде нумеруются с нуля)

// чтение Graphа

... Сам обход:

queue<int> q;

q.push (s);

vector<bool> used (n);

vector<int> d (n), p (n);

used[s] = true;

p[s] = -1;

while (!q.empty()) {

int v = q.front();

q.pop();

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (!used[to]) {

used[to] = true;

q.push (to);

d[to] = d[v] + 1;

p[to] = v;

} } } Если теперь надо восстановить и вывести kürzester Weg до какой-то вершины

, это можно сделать

следующим образом:

if (!used[to])

cout << "No path!";

else {

vector<int> path;

for (int v=to; v!=-1; v=p[v])

path.push_back (v);

reverse (path.begin(), path.end());

cout << "Path: ";

for (size_t i=0; i<path.size(); ++i)

cout << path[i] + 1 << " ";

}

Приложения Algorithmusа

● Поиск кратчайшего пути в невзвешенном Graphе.

● Connected components в Graphе за

. Для этого мы просто запускаем обход в ширину от каждой вершины, за исключением вершин, оставшихся

посещёнными (

) после предыдущих запусков. Таким образом, мы выполняем обычный запуск в ширину

от каждой вершины, но не обнуляем каждый раз Array

, за счёт чего мы каждый раз будем обходить

новую компоненту связности, а суммарное Laufzeit Algorithmusа составит по-прежнему

(такие

несколько запусков обхода на Graphе без обнуления Arrayа

называются серией обходов в ширину).

● Нахождения решения какой-либо задачи (игры) с наименьшим numberм ходов, если каждое

состояние системы можно представить вершиной Graphа, а переходы из одного состояния в другое — рёбрами Graphа. Классический Beispiel — игра, где робот двигается по полю, при этом он может передвигать ящики, находящиеся на этом же поле, и it is required за наименьшее number ходов передвинуть ящики в требуемые позиции. Решается это обходом в ширину по Graphу, где состоянием (вершиной) является набор координат: координаты робота, и координаты всех коробок.

● Нахождение кратчайшего пути в 0-1-Graphе (т.е. Graphе взвешенном, но с весами равными только 0 либо 1):

достаточно немного модифицировать Breadth-first search: если текущее edge нулевого веса, и происходит улучшение расстояния до какой-то вершины, то эту вершину добавляем не в конец, а в начало очереди.

● Нахождение кратчайшего цикла в неориентированном невзвешенном Graphе: производим Breadth-first search

из каждой вершины; как только в процессе обхода мы пытаемся пойти из текущей вершины по какому-то ребру в уже посещённую вершину, то это означает, что мы нашли кратчайший цикл, и останавливаем обход в ширину; среди всех таких найденных циклов (по одному от каждого запуска обхода) выбираем кратчайший.

● find все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин

Для этого надо запустить 2 поиска в ширину: из

, и из

. Обозначим через

Array кратчайших

расстояний, полученный в результате первого обхода, а через

— в результате второго обхода. Теперь для

любого ребра

легко проверить, лежит ли он на каком-либо кратчайшем пути: критерием будет

Beschreibung

● find все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин

Для этого надо запустить 2 поиска в ширину: из

, и из

. Обозначим через

Array кратчайших

расстояний, полученный в результате первого обхода, а через

— в результате второго обхода. Теперь для

любой вершины

легко проверить, лежит ли он на каком-либо кратчайшем пути: критерием будет

Beschreibung

● find кратчайший чётный путь в Graphе (т.е. путь чётной длины). Для этого надо построить

вспомогательный Graph, vertexми которого будут состояния

, где

— номер текущей вершины,

— текущая чётность. Любое edge

исходного Graphа в этом новом Graphе превратится в два

ребра

и

. После этого на этом Graphе надо обходом в ширину find kürzester Weg из стартовой вершины в конечную, с чётностью, равной 0.

Задачи в online judges

Список задач, которые можно сдать, используя обход в ширину:

● SGU #213 "Strong Defence" [Complexity: средняя]

C# Lösung

Auto-Entwurf, vor dem Einreichen prüfen

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    vector < List<int> > g; // граф
    int n; // число вершин
    int s; // стартовая вершина (вершины везде нумеруются с нуля)
    // чтение графа
    ...
    queue<int> q;
    q.push (s);
    List<bool> used (n);
    List<int> d (n), p (n);
    used[s] = true;
    p[s] = -1;
    while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (size_t i=0; i<g[v].size(); ++i) {
                    int to = g[v][i];
                    if (!used[to]) {
                            used[to] = true;
                            q.push (to);
                            d[to] = d[v] + 1;
                            p[to] = v;
                    }
            }
    }
    if (!used[to])
            Console.WriteLine( "No path!";
    else {
            List<int> path;
            for (int v=to; v!=-1; v=p[v])
                    path.push_back (v);
            reverse (path.begin(), path.end());
            Console.WriteLine( "Path: ";
            for (size_t i=0; i<path.size(); ++i)
                    Console.WriteLine( path[i] + 1 << " ";
    }
}

C++ Lösung

zugeordnet/original

vector < vector<int> > g; // граф
int n; // число вершин
int s; // стартовая вершина (вершины везде нумеруются с нуля)
// чтение графа
...
queue<int> q;
q.push (s);
vector<bool> used (n);
vector<int> d (n), p (n);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (size_t i=0; i<g[v].size(); ++i) {
                int to = g[v][i];
                if (!used[to]) {
                        used[to] = true;
                        q.push (to);
                        d[to] = d[v] + 1;
                        p[to] = v;
                }
        }
}
if (!used[to])
        cout << "No path!";
else {
        vector<int> path;
        for (int v=to; v!=-1; v=p[v])
                path.push_back (v);
        reverse (path.begin(), path.end());
        cout << "Path: ";
        for (size_t i=0; i<path.size(); ++i)
                cout << path[i] + 1 << " ";
}

Java Lösung

Auto-Entwurf, vor dem Einreichen prüfen

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    vector < ArrayList<Integer> > g; // граф
    int n; // число вершин
    int s; // стартовая вершина (вершины везде нумеруются с нуля)
    // чтение графа
    ...
    queue<int> q;
    q.push (s);
    ArrayList<Boolean> used (n);
    ArrayList<Integer> d (n), p (n);
    used[s] = true;
    p[s] = -1;
    while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (size_t i=0; i<g[v].size(); ++i) {
                    int to = g[v][i];
                    if (!used[to]) {
                            used[to] = true;
                            q.push (to);
                            d[to] = d[v] + 1;
                            p[to] = v;
                    }
            }
    }
    if (!used[to])
            System.out.println( "No path!";
    else {
            ArrayList<Integer> path;
            for (int v=to; v!=-1; v=p[v])
                    path.push_back (v);
            reverse (path.begin(), path.end());
            System.out.println( "Path: ";
            for (size_t i=0; i<path.size(); ++i)
                    System.out.println( path[i] + 1 << " ";
    }
}

Материал разбит как Algorithmusическая Aufgabe: изучить постановку, понять асимптотику и реализовать Algorithmus на выбранном языке.

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.