Что делает: сортирует вершины ациклического ориентированного графа так, чтобы все ребра были направлены слева направо и чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером

Где применяется: быстрое нахождение кратчайших путей в DAG, конденсация графа, еще че то та

Общая идея:

С помощью DFS вычислить времена выхода вершин (когда красим в чёрный) и после завершении работы над вершиной внеси её в начало массива, затем ревёрснуть массив и все будет чики пуки

Реализация:

// псевдокод писала Я так что чекните если что не так!

int main() {
	for u из G(V) do
		u.color = white // помечаем все вершинки белым O(|V|)
	for u из G(V) do
		if (u.color == white) // запускаем DFS для всех не пройденных вершинок
			topsortDFS(u)
}

void topsortDFS(int u) {
		for v из G(V) do
			if v.color == white
				DFS(v)
	u.color = black // после обхода всех смежных вершин помечаем, что вершина прошла DFS
	result.push_back(u) // т.к. при окраске в чёрный цвет можно вычислить время выхода
											// вершинки, после обхода DFSом закидываем вершину в массив
}

int main(): // в мейне
cout << result.reverse() // выводим массив в обратном порядке

‼ Особенности топсорта:

1. работает только в ориентированных ациклических графах!
2. первая вершина в топологической сортировке — это всегда вершина без входящих ребер

Визуализация: этим я займусь чуть попозже