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

Задача топологической сортировки графа звучит так: дан ориентированный граф, нужно упорядочить его вершины в массиве так, чтобы все графа рёбра вели из более ранней вершины в более позднюю.

Это может быть полезно, например, при планировании выполнения связанных задач: вам нужно одеться, в правильном порядке надев шорты (1), штаны (2), ботинки (3), подвернуть штаны (4) — как хипстеры — и завязать шнурки (5).

Во-первых, сразу заметим, что граф с циклом топологически отсортировать не получится — как ни располагай цикл в массиве, все время идти вправо по ребрам цикла не получится.

Во-вторых, верно обратное. Если цикла нет, то его обязательно можно топологически отсортировать — сейчас покажем, как.

Заметим, что вершину, из которой не ведет ни одно ребро, можно всегда поставить последней, а такая вершина в ациклическом графе всегда есть (иначе можно было бы идти по обратным рёбрам бесконечно). Из этого сразу следует конструктивное доказательство: будем итеративно класть в массив вершину, из которой ничего не ведет, и убирать ее из графа. После этого процесса массив надо будет развернуть.

Этот алгоритм проще реализовать, обратив внимание на времена выхода вершин в dfs. Вершина, из которой мы выйдем первой — та, у которой нет новых исходящих ребер. Дальше мы будем выходить только из тех вершин, которые если имеют исходящие ребра, то только в те вершины, из которых мы уже вышли.

Следовательно, достаточно просто выписать вершины в порядке выхода из dfs, а затем полученный список развернуть, и мы получим какую-то из корректных топологических сортировок.