Топологическая сортировка
Топологическая сортировка
Условие
Дан ориентированный ациклический граф с вершинами и рёбрами. Требуется найти такой порядок вершин, чтобы каждое ребро вело из вершины с меньшим индексом в вершину с большим индексом.
Другими словами, необходимо найти перестановку вершин (топологический порядок), которая соответствует всем рёбрам графа: если есть направленное ребро , то вершина должна идти раньше вершины в искомой перестановке.
Решение
Для решения этой задачи будем использовать поиск в глубину (DFS).
При старте из некоторой вершины DFS пытается пройти по всем рёбрам, исходящим из неё. Он останавливается на тех рёбрах, концы которых уже были посещены ранее, и рекурсивно продолжает обход по остальным. Таким образом, к моменту завершения все вершины, достижимые из , уже будут обработаны.