Skip to main content

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

Дано орієнтований граф з nn вершинами та mm ребрами. Потрібно пронумерувати його вершини таким чином, аби кожне ребро вело з вершини з меншим номером у вершину з більшим.

Іншими словами, потрібно знайти перестановку вершин (топологічний порядок), відповідну порядку, що задається усіма ребрами у графі.

Топологічне сортування може бути не унікальним (наприклад, коли є три такі вершини aa, bb, cc, що з aa є шлях в bb та в cc, але ні з bb в cc, ні з cc в bb добратися не можна).

Топологічне сортування може не існувати зовсім - якщо граф містить цикли. Оскільки тоді виникає протиріччя: є шлях і з однієї вершини в іншу, і навпаки.

Алгоритм​

Для розв'язку скористаємось пошуком в глибину.

Припустимо, що граф ациклічний, тобто розв'язок існує. Що робить пошук в глибину? При запуску з якоїсь вершини vv він намагається запуститися уздовж всіх ребер, вихідних з vv. Уздовж тих ребер, кінці яких вже були відвідані раніше, він не проходить, а уздовж всіх інших - проходить і викликає себе від їх кінців.

Таким чином, на момент виходу з виклику dfs(v){\rm dfs}(v) всі вершини, досяжні з vv як безпосередньо (по ребру), так і дотично (по деякому шляху), вже відвідані пошуком в глибину. Отже, якщо ми будемо в момент виходу з dfs(v){\rm dfs}(v) додавати нашу вершину в початок деякого списку, то у кінці алгоритму в цьому списку отримаємо топологічне сортування.

Пояснити можна також за допомогою поняття "часу виходу" пошуку в глибину. Час виходу для кожної вершини vv - це момент часу, в який закінчив працювати виклик dfs(v){\rm dfs}(v) пошуку в глибину. Часи виходу можна пронумерувати від 11 до nn. Легко зрозуміти, що при пошуці в глибину час виходу з будь-якої вершини vv завжди більший, ніж час виходу з усіх вершин, досяжних з неї (тобто вони були відвідані або до виклику dfs(v){\rm dfs}(v), або під час нього). Таким чином, шукане топологічне сортування - це сортування у порядку зменшення часів виходу.

Складність алгоритму така ж як і у пошуку в глибину - O(n+m)O(n+m), де nn - кількість вершин, mm - кількість ребер.

Реалізація​

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

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

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);
        }
    }
    ans.push_back(v);
}

void topological_sort() {
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }
    ans.clear();
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    reverse(ans.begin(), ans.end());
}

Тут константа MAXN задає максимально можливу кількість вершин у графі.

Основна функція розв'язку - це topological_sort. Вона ініціалізує допоміжний масив visited пошуку в глибину, запускає його, і у кінці масив ans містить шукане топологічне сортування.

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

  • Є nn змінних, значення яких нам невідомі. Відомо лише про деякі пари змінних, у яких одна змінна менша іншої. Потрібно перевірити чи не суперечливі ці нерівності, і якщо ні, видати змінні у порядку їх зростання (якщо розв'язків декілька - видати будь-який).

    Потрібно створити граф з nn вершинами, де ребра ведуть з меншої змінної у більшу. Провести перевірку на ациклічність. Якщо граф містить цикл, то нерівності суперечливі, а якщо не містить циклу, то вершини у топологічному порядку відповідатимуть змінним у порядку їх зростання.

Задачі​