Топологическая сортировка
Published: 2023-12-14 11:11:22


Топологическая сортировка это третий алгоритм на графах, который нужно знать для успешного прохождения алгоритмического собеседования. Два других это [DFS ](https://dev.to/faangmaster/dfs-depth-first-searchpoisk-v-ghlubinu-28ea)(поиск в глубину) и [BFS ](https://dev.to/faangmaster/poisk-v-shirinu-breadth-first-search-3kaa)(поиск в ширину).

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

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9z0gn1lkhu95q8aifmcv.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wrl2grf82eo7ktob1yxh.png)

или 


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7jc2aahtd8frpsa2nuq2.png)

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

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

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

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

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

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

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

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

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

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

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tusnsznxgialsn6cd5ug.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8ity7eoqv05hk3w9a70y.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nboz4p4oj9oirfiza9gi.png)


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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ps3hqop2ww6vytauf2ff.png)



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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n3bt0zfjepjvvkoaw8rh.png)


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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pcupbdka19ptf9pxjdv0.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ucbnf2gsh4ljh0xnz6ro.png)

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

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

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yeohcvqru1wn2v1ndzz4.png)

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

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

```java
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;
}
```