Топологическая сортировка: алгоритмы Кана и DFS с примерами

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

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

Простая аналогия

Представьте список задач с зависимостями:

• Задача B зависит от A (сначала A, потом B)
• Задача C зависит от A и B
• Задача D зависит от C

Топологическая сортировка даёт порядок выполнения: A → B → C → D

Визуализация

    A ──→ B ──→ D
    │     │
    ↓     ↓
    C ←───┘

Возможные топологические порядки:
- A, B, C, D
- A, B, D, C (если D не зависит от C)

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

Только для DAG (Directed Acyclic Graph):

• Граф должен быть ориентированным
• Не должно быть циклов

Если в графе есть цикл, топологическая сортировка невозможна.

Алгоритм Кана (BFS-подход)

Идея

1. Найти вершины с нулевой входящей степенью (без зависимостей)
2. Добавить их в результат и "удалить" из графа
3. Повторять, пока есть вершины с нулевой степенью

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Реализация на JavaScript

function kahnTopologicalSort(n, edges) {
    // Строим граф и считаем входящие степени
    const graph = Array.from({ length: n }, () => []);
    const inDegree = new Array(n).fill(0);

    for (const [from, to] of edges) {
        graph[from].push(to);
        inDegree[to]++;
    }

    // Очередь вершин с нулевой входящей степенью
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }

    const result = [];

    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node);

        // "Удаляем" вершину из графа
        for (const neighbor of graph[node]) {
            inDegree[neighbor]--;

            // Если степень стала 0 — добавляем в очередь
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }

    // Если не все вершины обработаны — есть цикл
    if (result.length !== n) {
        return null; // Топологическая сортировка невозможна
    }

    return result;
}

// Пример
const edges = [[0, 1], [0, 2], [1, 3], [2, 3]];
console.log(kahnTopologicalSort(4, edges)); // [0, 1, 2, 3] или [0, 2, 1, 3]

Реализация на Python

from collections import deque

def kahn_topological_sort(n, edges):
    # Строим граф
    graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    # Начинаем с вершин без входящих рёбер
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # Проверка на цикл
    if len(result) != n:
        return None

    return result


# Пример
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
print(kahn_topological_sort(4, edges))  # [0, 1, 2, 3]

Сложность алгоритма Кана

• Время: O(V + E)
• Память: O(V + E)

Алгоритм на основе DFS

Идея

1. Запускаем DFS из каждой непосещённой вершины
2. При выходе из вершины (после обработки всех соседей) добавляем её в стек
3. Результат — стек в обратном порядке

Реализация на JavaScript

function dfsTopologicalSort(n, edges) {
    const graph = Array.from({ length: n }, () => []);

    for (const [from, to] of edges) {
        graph[from].push(to);
    }

    const visited = new Array(n).fill(0); // 0: не посещена, 1: в процессе, 2: завершена
    const result = [];
    let hasCycle = false;

    function dfs(node) {
        if (hasCycle) return;

        visited[node] = 1; // В процессе обработки

        for (const neighbor of graph[node]) {
            if (visited[neighbor] === 1) {
                // Нашли обратное ребро — цикл!
                hasCycle = true;
                return;
            }
            if (visited[neighbor] === 0) {
                dfs(neighbor);
            }
        }

        visited[node] = 2; // Завершена
        result.push(node); // Добавляем при выходе
    }

    for (let i = 0; i < n; i++) {
        if (visited[i] === 0) {
            dfs(i);
        }
    }

    if (hasCycle) {
        return null;
    }

    return result.reverse(); // Разворачиваем для правильного порядка
}

// Пример
const edges = [[0, 1], [0, 2], [1, 3], [2, 3]];
console.log(dfsTopologicalSort(4, edges)); // [0, 2, 1, 3] или другой валидный порядок

Реализация на Python

def dfs_topological_sort(n, edges):
    graph = [[] for _ in range(n)]

    for u, v in edges:
        graph[u].append(v)

    # 0: белый (не посещён), 1: серый (в процессе), 2: чёрный (завершён)
    color = [0] * n
    result = []
    has_cycle = False

    def dfs(node):
        nonlocal has_cycle
        if has_cycle:
            return

        color[node] = 1  # Серый

        for neighbor in graph[node]:
            if color[neighbor] == 1:  # Обратное ребро
                has_cycle = True
                return
            if color[neighbor] == 0:
                dfs(neighbor)

        color[node] = 2  # Чёрный
        result.append(node)

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

    if has_cycle:
        return None

    return result[::-1]


# Пример
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
print(dfs_topological_sort(4, edges))  # [0, 2, 1, 3]

Сложность алгоритма DFS

• Время: O(V + E)
• Память: O(V) для рекурсии + O(V + E) для графа

Сравнение алгоритмов

Применение топологической сортировки

Задача 1: Course Schedule (LeetCode 207)

Можно ли пройти все курсы, учитывая зависимости?

function canFinish(numCourses, prerequisites) {
    const result = kahnTopologicalSort(numCourses, prerequisites);
    return result !== null;
}

// Пример
console.log(canFinish(2, [[1, 0]])); // true: сначала 0, потом 1
console.log(canFinish(2, [[1, 0], [0, 1]])); // false: цикл

Задача 2: Course Schedule II (LeetCode 210)

Вернуть порядок прохождения курсов:

def find_order(num_courses, prerequisites):
    # prerequisites[i] = [a, b] означает: для курса a нужен курс b
    edges = [(b, a) for a, b in prerequisites]
    return kahn_topological_sort(num_courses, edges) or []

Задача 3: Alien Dictionary (LeetCode 269)

Восстановить алфавит по отсортированному словарю:

function alienOrder(words) {
    // Собираем все буквы
    const chars = new Set();
    for (const word of words) {
        for (const c of word) {
            chars.add(c);
        }
    }

    // Строим граф зависимостей
    const graph = new Map();
    const inDegree = new Map();

    for (const c of chars) {
        graph.set(c, []);
        inDegree.set(c, 0);
    }

    // Сравниваем соседние слова
    for (let i = 0; i < words.length - 1; i++) {
        const w1 = words[i];
        const w2 = words[i + 1];

        // Проверка на невалидный порядок
        if (w1.length > w2.length && w1.startsWith(w2)) {
            return ""; // "abc" перед "ab" — невозможно
        }

        // Находим первое различие
        for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
            if (w1[j] !== w2[j]) {
                graph.get(w1[j]).push(w2[j]);
                inDegree.set(w2[j], inDegree.get(w2[j]) + 1);
                break;
            }
        }
    }

    // Алгоритм Кана
    const queue = [];
    for (const [c, deg] of inDegree) {
        if (deg === 0) queue.push(c);
    }

    const result = [];
    while (queue.length > 0) {
        const c = queue.shift();
        result.push(c);

        for (const next of graph.get(c)) {
            inDegree.set(next, inDegree.get(next) - 1);
            if (inDegree.get(next) === 0) {
                queue.push(next);
            }
        }
    }

    return result.length === chars.size ? result.join('') : "";
}

Задача 4: Parallel Courses (Минимальное количество семестров)

def minimum_semesters(n, relations):
    graph = [[] for _ in range(n + 1)]
    in_degree = [0] * (n + 1)

    for prev, next_course in relations:
        graph[prev].append(next_course)
        in_degree[next_course] += 1

    # BFS по уровням
    queue = deque([i for i in range(1, n + 1) if in_degree[i] == 0])
    semesters = 0
    courses_taken = 0

    while queue:
        semesters += 1
        # Обрабатываем все курсы текущего семестра
        for _ in range(len(queue)):
            course = queue.popleft()
            courses_taken += 1

            for next_course in graph[course]:
                in_degree[next_course] -= 1
                if in_degree[next_course] == 0:
                    queue.append(next_course)

    return semesters if courses_taken == n else -1

Задача 5: Longest Path in DAG

function longestPathDAG(n, edges) {
    const graph = Array.from({ length: n }, () => []);
    const inDegree = new Array(n).fill(0);

    for (const [from, to, weight] of edges) {
        graph[from].push([to, weight]);
        inDegree[to]++;
    }

    // Топологическая сортировка (Кан)
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }

    const topoOrder = [];
    while (queue.length > 0) {
        const node = queue.shift();
        topoOrder.push(node);
        for (const [neighbor] of graph[node]) {
            if (--inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }

    // Динамика по топологическому порядку
    const dist = new Array(n).fill(-Infinity);
    dist[0] = 0; // Стартовая вершина

    for (const node of topoOrder) {
        if (dist[node] === -Infinity) continue;

        for (const [neighbor, weight] of graph[node]) {
            dist[neighbor] = Math.max(dist[neighbor], dist[node] + weight);
        }
    }

    return Math.max(...dist);
}

Обнаружение циклов

В алгоритме Кана

function hasCycle(n, edges) {
    const result = kahnTopologicalSort(n, edges);
    return result === null;
}

В DFS (три цвета)

def has_cycle_dfs(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(node):
        color[node] = GRAY

        for neighbor in graph[node]:
            if color[neighbor] == GRAY:  # Обратное ребро
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True

        color[node] = BLACK
        return False

    for i in range(n):
        if color[i] == WHITE:
            if dfs(i):
                return True

    return False

Все топологические сортировки

Для перечисления всех возможных порядков:

def all_topological_sorts(n, edges):
    graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    result = []

    def backtrack(path, in_deg):
        if len(path) == n:
            result.append(path[:])
            return

        for node in range(n):
            if in_deg[node] == 0 and node not in path:
                # Выбираем вершину
                path.append(node)

                # Уменьшаем степени соседей
                for neighbor in graph[node]:
                    in_deg[neighbor] -= 1

                backtrack(path, in_deg)

                # Откат
                path.pop()
                for neighbor in graph[node]:
                    in_deg[neighbor] += 1

    backtrack([], in_degree[:])
    return result


# Пример
edges = [(0, 2), (1, 2)]
print(all_topological_sorts(3, edges))
# [[0, 1, 2], [1, 0, 2]]

Типичные ошибки

Ошибка 1: Неправильное направление рёбер

// Условие: course a requires course b
// Ребро: b → a (не a → b!)
for (const [a, b] of prerequisites) {
    graph[b].push(a); // b должен быть раньше a
}

Ошибка 2: Забыли проверить цикл

// Всегда проверяйте!
if (result.length !== n) {
    return null; // или throw Error
}

Ошибка 3: Пустой граф

// Граф без рёбер — все вершины в любом порядке
if (edges.length === 0) {
    return Array.from({ length: n }, (_, i) => i);
}

Анализ сложности

Задачи для практики

1. Course Schedule (LeetCode 207) — проверка возможности
2. Course Schedule II (LeetCode 210) — получить порядок
3. Alien Dictionary (LeetCode 269) — построить граф из слов
4. Sequence Reconstruction (LeetCode 444) — единственность порядка
5. Parallel Courses (LeetCode 1136) — минимальное время
6. Longest Increasing Path in Matrix — топосортировка + DP

Заключение

Топологическая сортировка — важный инструмент для работы с зависимостями:

• Два подхода: Кан (BFS) и DFS
• Обнаружение циклов — встроено в оба алгоритма
• Время O(V + E) — линейное

Рекомендуемый порядок изучения:

1. Алгоритм Кана — проще для понимания
2. DFS-подход — понять связь с обратными рёбрами
3. Обнаружение циклов
4. Практические задачи (Course Schedule)
5. Построение графа из условий (Alien Dictionary)
6. Комбинация с DP для поиска путей