Nie, to nie jest kolejne straszne sortowanie :D To akurat jest dość proste, a sortuje nam wierzchołki według "głębokości" na której się znajdują. Najpierw będą wierzchołki, do których nie dochodzą krawędzie, potem wierzchołki do których dochodzi się w jednym kroku z innych, potem te, do których dojdziemy w dwóch krokach itd.
edit: Nie do końca. Topsort wypisuje wierzchołki w takiej kolejności, żeby dla każdej krawędzi
$(u,v)$ wierzchołek $u$ znalazł się przed wierzchołkiem $v$. Nie ma to wiele wspólnego z kolejnością wg. głębokości.
edit2: Ma znaczenie - bo musi być zachowana kolejność rosnąca głębokości wszystkich punktów na danej ścieżce od wierzchołka początkowego (takiego od którego krawędzie tylko wychodzą) do wierzchołka końcowego.
edit3: Przypomnij sobie Krzysiu pierwsze zadanie na sprawdzianie. W podpunckie a) czwórka musiała być na początku topologicznego posortowania, a w b) przedostatnia…a była cały czas samo "głęboko" od jedynki. Mając taki graf skierowany:
1 -> 2
2 -> 3
3 ->
4 -> 3
5 ->4
Mogę go posortować topologicznie na pare sposobów: 54123,51423,51243,12543,15243,15423… a graf jest cały czas taki sam:).
edit4: a przeczytałeś miszczak że chodzi o ścieżki? w każdym z twoich przypadków to co napisałem jest prawdziwe.. :/
edit5: co nie zmienia faktu, że nie taka jest definicja porządku topologicznego :) - Lech Duraj
Jak to zrobić?? Bardzo prosto:
void DFS(int v) { if (odwiedzony[v]) return; odwiedzony[v]=1; wywolal_DFS_dla_wszystkich_sasiadow_v(); stos[i]=v; i++; }
Po wywołaniu takiego DFSa, po prostu wypisujemy stos od końca ;)
EDIT: Stosu nie wypisuje się od końca, ponieważ udostępnia on tylko takie operacje: pop, top, size, empty. Pomijać fakt, że ten przytoczony "stos" w tym kodzie jest najnormalniejszą tablicą, którą wystarczy normalnie wypisać po bożemu - codemind.
