Skip to main content

Пошук в ширину

Пошук в ширину (обхід в ширину, BFS) - це один з основних алгоритмів на графах.

В результаті пошуку в ширину знаходиться шлях найкоротшої довжини у незваженому графі, тобто шлях, що містить найменшу кількість ребер.

Алгоритм працює за O(n+m)O(n+m), де nn - кількість вершин, mm - кількість ребер.

Алгоритм​

На вхід алгоритму подається незважений граф і номер стартової вершини ss. Граф може бути як орієнтованим, так і неорієнтованим, для алгоритму це не важливо.

Сам алгоритм можна сприймати як процес "підпалювання" графа: на нульовому кроці підпалюємо тільки вершину ss. На кожному наступному кроці вогонь з кожної вершини, що вже горить, поширюється на всіх її сусідів; тобто за одну ітерацію алгоритму відбувається розширення "кільця вогню" в ширину на одиницю (звідси і назва алгоритму).

Формальний опис алгоритму. Створимо чергу qq, в яку будуть додаватися вершини, що горять, а також заведемо булевий масив visited[]\rm visited[], в якому для кожної вершини будемо відзначати, горить вона вже чи ні (або іншими словами, чи була вона переглянутою).

Спершу в чергу додається тільки вершина ss, і visited[s]=true\rm visited[s] = true, а для всіх інших вершин visited[]=false\rm visited[] = false. Потім алгоритм представляє собою цикл: поки черга не порожня, дістати з її голови одну вершину, переглянути всі ребра, що виходять з цієї вершини, і якщо якісь з переглянутих вершин (на протилежних кінцях ребер) ще не горять, то підпалити їх і додати в кінець черги.

В результаті, коли черга стане пустою, обхід в ширину обійде всі досяжні з ss вершини, причому до кожної дійде найкоротшим шляхом. Також можна порахувати довжини найкоротших шляхів (для чого треба завести масив довжин шляхів d[]\rm d[]), і компактно зберегти інформацію, якої достатню для відновлення всіх цих найкоротших шляхів (для цього треба завести масив "предків" p[]\rm p[], в якому для кожної вершини зберігати номер вершини, з якої ми потрапили в цю вершину).

Реалізація​

Реалізуємо вищеописаний алгоритм на мові C++.

Вхідні дані:

vector<vector<int>> g; // граф, список суміжності
int n; // кількість вершин
int s; // стартова вершина (вершини нумеруються з нуля)

// читання графа
...

Сам обхід:

queue<int> q;
vector<bool> visited(n);
vector<int> d(n), p(n);

q.push(s);
visited[s] = true;
p[s] = -1;

while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if (!visited[to]) {
            visited[to] = true;
            q.push(to);
            d[to] = d[v] + 1;
            p[to] = v;
        }
    }
}

Якщо потрібно відновити і вивести найкоротший шлях до якоїсь вершини to\rm to, то це можна зробити наступним чином:

if (!visited[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 (int i = 0; i < path.size(); i++) {
        cout << path[i] + 1 << " ";
    }
}

Застосування​

  • Пошук найкоротшого шляху у незваженому графі.

    Описано у цій статті.

  • Пошук компонент зв'язності у графі за O(n+m)O(n+m).

    Для цього запускаємо обхід в ширину від кожної вершини, за винятком вершин, що залишилися відвіданими (visited=true\rm visited=true) після попередніх запусків. Таким чином, ми виконуємо звичайний запуск в ширину від кожної вершини, але не зануляємо кожний раз масив visited[]\rm visited[], за рахунок чого ми кожний раз будемо обходити нову компоненту зв'язності, а сумарний час роботи алгоритму буде як і раніше O(n+m)O(n+m) (такі декілька запусків обходу на графі без занулення масиву visited\rm visited називається серією обходів в ширину).

  • Знаходження розв'язку будь-якої задачі з найменшим числом ходів, якщо кожний стан системи можна уявити вершиною графа, а переходи з одного стану в інші - ребрами графа.

    Класичний приклад - гра, де робот рухається по полю, при цьому він може переміщати ящики, що знаходяться на цьому ж полі, і потрібно за найменше число ходів пересунути ящики в необхідні позиції. Розв'язується обходом в ширину по графу, де станом (вершиною) є набір координат: координати робота, і координати всіх коробок.

  • Знаходження найкоротшого шляху в 0-1-графі (зважений граф, але з вагами рівними тільки 0 або 1).

    Достатньо трохи модифікувати пошук в ширину: якщо поточне ребро нульової ваги, і відбувається покращення відстані до якоїсь вершини, то цю вершину додаємо не в кінець, а в початок черги.

  • Знаходження найкоротшого циклу в орієнтованому незваженому графі.

    Для цього запускаємо пошук в ширину з кожної вершини. Як тільки в процесі обходу ми намагаємося піти з поточної вершини по якомусь ребру до вже відвіданої вершини, то це означає, що ми знайшли найкоротший цикл, і зупиняємо обхід в ширину. Серед всіх таких знайдених циклів (по одному від кожного запуску обходу) вибираємо найкоротший.

  • Знайти всі ребра, що лежать на будь-якому найкоротшому шляху між заданою парою вершин (a,b)(a,b).

    Для цього треба запустити 2 пошуки в ширину: з aa, і з bb. Позначимо через da[]d_a[] масив найкоротших відстаней, отриманий в результаті першого обходу, а через db[]d_b[] - в результаті другого обходу. Тепер для будь-якого ребра (u,v)(u,v) легко перевірити чи лежить він на будь-якому найкоротшому шляху: критерієм буде умова da[u]+1+db[v]=da[b]d_a[u] + 1 + d_b[v] = d_a[b].

  • Знайти всі вершини, що лежать на будь-якому найкоротшому шляху між заданою парою вершин (a,b)(a,b).

    Для цього треба запустити 2 пошуки в ширину: з aa, і з bb. Позначимо через da[]d_a[] масив найкоротших відстаней, отриманий в результаті першого обходу, а через db[]d_b[] - в результаті другого обходу. Тепер для будь-якої вершини vv легко перевірити чи лежить вона на будь-якому найкоротшому шляху: критерієм буде умова da[v]+db[v]=da[b]d_a[v] + d_b[v] = d_a[b].

  • Знайти найкоротший парний шлях в графі (тобто шлях парної довжини).

    Для цього треба побудувати допоміжний граф, вершинами якого будуть стани (v,c)(v,c), де vv - номер поточної вершини, c=0…1c = 0 \ldots 1 - поточна парність. Будь-яке ребро (a,b)(a,b) вихідного графа в новому графі перетвориться в два ребра ((u,0),(v,1))((u,0),(v,1)) та ((u,1),(v,0))((u,1),(v,0)). Після цього на цьому графі треба обходом в ширину знайти найкоротший шлях з стартової вершини в кінцеву, з парністю, рівною 0.

Задачі​