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

Топологическая сортировка это третий алгоритм на графах, который нужно знать для успешного прохождения алгоритмического собеседования. Два других это DFS (поиск в глубину) и BFS (поиск в ширину).

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

Для наглядности рассмотрим такую задачу. Например, у нас есть список задач, выполнение которых зависит друг от друга. Например, задача 2 не может быть выполнена без выполнения задачи 1, 3 и 4. А задача 3 не может быть выполнена до выполнения задачи 1 и 4.
Это можно отобразить в виде направленного графа:

Нам нужно определить в каком порядке нужно выполнять задачи.
Для данного примера порядок выполнения может быть следующий:

или

Т.е. вначале мы можем выполнить задачи 1 и 4 (в любом порядке), т.к. для их выполнения не нужно выполнять другие задачи (нет входящих ребер). После выполнения задач 1 и 4 мы может выполнить задачу 3, т.к. она зависит от задач 1 и 4, которые были выполнены ранее. И наконец, после выполнения задачи 3, мы может выполнить задачу 2.

Решением данной задачи будет алгоритм топологической сортировки. Есть несколько реализаций данного алгоритма, я приведу один из них, который легче понять и запомнить, по моему мнению. Это алгоритм Кана.

Работает он следующим образом:

1) Для каждой вершины будем хранить множество вершин, от которых зависит данная задача (есть входящее ребро). Для нашего примера это: для вершины 1 и 4 нет входящих ребер. Для вершины 3 это вершины 1 и 4, и для вершины 2 это ребра из вершин 1, 3, 4.
В виде hash-таблицы это можно представить так:

{
 1 -> empty,
 4 -> empty,
 3 -> {1, 4}
 2 -> {1, 3, 4} 
}

2) Найдем независимые вершины. Т.е. такие вершины, для которых нет входящих ребер.

3) Каждую такую независимую вершину будем добавлять в результат выполнения программы

4) Для каждой такой независимой вершины будем обновлять множество зависимостей из 1) путем удаления всех ребер исходящих из этой независимой вершины

5) Выполним снова шаг 2 в цикле. Найдем вновь образовавшиеся независимые вершины и т.д.

Давайте посмотрим как это будет работать шаг за шагом на нашем примере.

Инициализируем hash-таблицу inbound входящих ребер:

Найдем независимые: это вершины 1 и 4, т.к. в таблице inbound у них нет входящих ребер. Добавим их в результат:

Обновим таблицу inbound путем удаления ребер исходящих из вершин 1 и 4:

Удалим вершины 1 и 4 из таблицы inbound, как уже посещенные:

Найдем новые независимые вершины. Это вершина 3. Т.к. в таблице inbound только у нее нет входящих ребер.
Добавим ее в результат:

Обновим таблицу inbound путем удаления ребер исходящих из 3 и удалим саму вершину 3 как уже посещенную:

Проделаем все еще раз. Теперь независимая вершина это 2. Добавим ее в результат, удалим ее из inbound и все ребра исходящие из нее. Получим:

На следующей итерации цикла у нас не будет обнаружено новых независимых вершин и работа алгоритма завершается.

Как мы видим, в конце работы таблица inbound пуста. Но есть edge-case, когда у нас в графе есть цикл. Тогда мы вывалимся из цикла до того, как мы обработаем все вершины.

Например, для такого графа:

Мы найдем независимую вершину 1, но после ее обработки мы не найдем новых независимых вершин из-за цикла. Поэтому когда мы вывалимся из цикла, то у нас inbound таблица будет не пуста. Этот случай мы можем обработать отдельно. Например, вернув пустой результат или бросив ошибку.

Вот код алгоритма. На вход нам подается список вершин и список зависимостей между ними. На выходе мы получаем результат топологической сортировки. Для нашего примера - это порядок выполнения задач, которые зависят друг от друга.

public static List<Integer> topologicalSort(List<Integer> jobs, List<Integer[]> deps) {
    //Граф зависимостей
    Map<Integer, Set<Integer>> dependencies = new HashMap<>();
    //Входящие ребра
    Map<Integer, Set<Integer>> incoming = new HashMap<>();
    for (Integer task : jobs) {
        incoming.put(task, new HashSet<>());
        dependencies.put(task, new HashSet<>());
    }
    for (Integer[] dep : deps) {
        Integer from = dep[0];
        Integer to = dep[1];
        dependencies.get(from).add(to);
        incoming.get(to).add(from);
    }
    List<Integer> result = new ArrayList<>();
    List<Integer> independentTasks = null;
    do {
        //получаем список вершин, без входящих зависимостей
        independentTasks = getIndependentTasks(incoming);
        for (Integer task : independentTasks) {
            for (Integer dep : dependencies.get(task)) {
                //для каждой вершины, без входящих зависимостей
                //удаляем ребро исходящее из него
                incoming.get(dep).remove(task);
            }
            result.add(task);
            incoming.remove(task);
        }

    } while (!independentTasks.isEmpty());
    //Если incoming не пустая, то у нас цикл в графе
    return incoming.isEmpty() ? result : new ArrayList<>();
}

private static List<Integer> getIndependentTasks(Map<Integer, Set<Integer>> incoming) {
    List<Integer> result = new ArrayList<>();
    for (Integer task : incoming.keySet()) {
        if (incoming.get(task).isEmpty()) {
            result.add(task);
        }
    }
    return result;
}