← Назад к графовым алгоритмам

Топологическая сортировка

Порядок вершин в ациклическом ориентированном графе

🐍 Python
n, m = map(int, input().split())
A = [[] for _ in range(n)]
used = [0] * n
R = []
p = [0] * n
f = 0

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A[a].append(b)

def dfs(h):
    global f
    used[h] = 1
    for a in A[h]:
        if used[a] == 0:
            p[a] = h
            dfs(a)
        elif used[a] == 1 and f == 0:
            f = 1
    used[h] = 2
    R.append(h + 1)

for i in range(n):
    if used[i] == 0:
        dfs(i)

if f:
    print(-1)
else:
    R.reverse()
    print(*R)
⚙️ C++
#include <bits/stdc++.h>
using namespace std;
using T = int;

vector<vector<T>> A;
vector<T> used;
vector<T> R;
vector<T> p;
T f;

void dfs(T v) {
    used[v] = 1;
    for (T to : A[v]) {
        if (!used[to]) {
            p[to] = v;
            dfs(to);
        } else if (used[to] == 1 && f == 0) {
            f = 1;
        }
    }
    used[v] = 2;
    R.push_back(v);
}

int main() {
    T n, m, a, b, i;
    cin >> n >> m;
    p.resize(n);
    A.resize(n);
    used.resize(n);
    
    for (i = 0; i < m; i++) {
        cin >> a >> b;
        a--;
        b--;
        A[a].push_back(b);
    }

    for (i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i);
        }
    }
    
    if (f) {
        cout << -1;
        return 0;
    }
    
    reverse(R.begin(), R.end());
    for (T r : R) {
        cout << r + 1 << " ";
    }
    cout << "\n";
    
    return 0;
}

Как работает топологическая сортировка?

Топологическая сортировка — это упорядочивание вершин ориентированного графа таким образом, что для каждого ребра (u → v) вершина u находится в списке раньше, чем v. Алгоритм также обнаруживает циклы (неотъемлемое свойство ориентированного графа).

Алгоритм использует обход в глубину (DFS) и раскраску вершин:

Если во время обхода встречается серая вершина, значит найден цикл (f = 1).

Важно: Топологическая сортировка возможна только для ациклических ориентированных графов (DAG). При наличии цикла программа выводит -1.

После рекурсивного обхода всех потомков вершина добавляется в стек R. В конце стек переворачивается, чтобы получить правильный порядок.

Временная сложность: O(n + m), где n — количество вершин, m — количество рёбер.

Формат ввода и вывода

Ввод:

Вывод:

Пример ввода (DAG):

4 3
1 2
2 3
3 4

Здесь:
n=4 (вершины 1,2,3,4)
Рёбра: 1→2, 2→3, 3→4
Граф — цепочка, цикла нет.

Вывод (один из возможных): 1 2 3 4

Пример ввода (с циклом):

3 3
1 2
2 3
3 1

Здесь:
n=3 (вершины 1,2,3)
Рёбра: 1→2, 2→3, 3→1 — образуют цикл.

Вывод: -1

Попробовать топологическую сортировку онлайн

Введите граф в формате, описанном выше:

Результат появится здесь...