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

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

Условие

Дан ориентированный ациклический граф с $n$ вершинами и $m$ рёбрами. Требуется найти такой порядок вершин, чтобы каждое ребро вело из вершины с меньшим индексом в вершину с большим индексом.

Другими словами, необходимо найти перестановку вершин (топологический порядок), которая соответствует всем рёбрам графа: если есть направленное ребро $x \rightarrow y$, то вершина $x$ должна идти раньше вершины $y$ в искомой перестановке.

Решение

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

При старте из некоторой вершины $x$ DFS пытается пройти по всем рёбрам, исходящим из неё. Он останавливается на тех рёбрах, концы которых уже были посещены ранее, и рекурсивно продолжает обход по остальным. Таким образом, к моменту завершения все вершины, достижимые из , уже будут обработаны.