Skip to main content

Пошук в глибину

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

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

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

Алгоритм​

TODO: add detailed description for DFS.

Реалізація​

Найпростіша реалізація:

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

void dfs(int v) {
    visited[v] = true;
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if (!visited[to]) {
            dfs(to);
        }
    }
}

Інколи необхідно знати кольори вершин (0 - не відвідана вершина; 1 - відвідана вершина, але досі у стеці; 2 - відвідана і більше немає у стеці) та "час" заходу та виходу з вершин. Ці допоміжні величини використовуються у декількох наведених прикладах застосування алгоритму.

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

vector<int> color; // кольори вершин (0, 1, або 2)

vector<int> time_in, time_out; // "часи" заходу та виходу з вершин
int dfs_timer = 0; // "таймер" для визначення "часів"

void dfs(int v) {
    time_in[v] = dfs_timer++;
    color[v] = 1;
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if (color[to] == 0) {
            dfs(to);
        }
    }
    color[v] = 2;
    time_out[v] = dfs_timer++;
}

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

  • Пошук будь-якого шляху у графі.

  • Пошук лексикографічно першого шляху в графі.

  • Перевірка чи одна вершина дерева є предком іншої.

    На початку і у кінці ітерації пошуку в глибину будемо запам'ятовувати "час" заходу і виходу з кожної вершині. Тепер за O(1)O(1) можна знайти відповідь: вершина aa є предком вершини bb тоді і тільки тоді, коли time_in[a]<time_in[b]\rm time\_in[a] < time\_in[b] та time_out[a]>time_out[b]\rm time\_out[a] > time\_out[b].

  • Найменший спільний предок.

  • Топологічне сортування.

    Запускаємо серію пошуків в глибину, щоб обійти всі вершини графа. Відсортуємо вершини по спаданню часу виходу - це і буде відповіддю.

  • Перевірка графа на ациклічність і знаходження циклу.

  • Пошук компонент сильної зв'язності.

    Спочатку проводимо топологічне сортування, а потім транспонуємо граф. Після того знову проводимо серію пошуків у глибину, але в порядку вершин, який було отримано топологічним сортуванням. Кожне дерево пошуку - сильнозв'язана компонента.

  • Пошук мостів.

    Спочатку перетворюємо граф в орієнтований, роблячи серію пошуків в глибину, і орієнтуючи кожне ребро так, як ми намагалися по ньому пройти. Потім знаходимо сильнозв'язані компоненти. Мостами є ті ребра, кінці яких належать різним сильнозв'язаним компонентам.

Задачі​