Sortowanie topologiczne
Z Wikipedii
W teorii grafów sortowanie topologiczne skierowanego grafu acyklicznego to liniowe uporządkowanie wierzchołków, w którym jeśli istnieje krawędź skierowana prowadząca od wierzchołka x do y, to x znajdzie się przed wierzchołkiem y. Innymi słowy, każdy wierzchołek poprzedza wszystkie te wierzchołki, do których prowadzą wychodzące od niego krawędzie.
Wierzchołki w każdym grafie acyklicznym skierowanym można posortować topologicznie na jeden lub więcej sposobów.
[edytuj] Zastosowanie
Sortowanie topologiczne pozwala na ustalenie kolejności wykonywania jakichś operacji (czynności), np. służy do ustalenia poprawnej kolejności instalacji w automatycznym uzupełnianiu zależności pakietów w systemach uniksopodobnych. Prostszym przykładem może być kolejność czynności potrzebnych do upieczenia ciasta.
Poszczególne czynności są reprezentowane jako wierzchołki, a zależności pomiędzy nimi - jako krawędzie. Jeśli krawędź prowadzi od A do B, to znaczy, że czynność A musi zostać wykonana przed czynnością B.
Zdarza się, że wykonanie jakiegoś zadania musi być poprzedzone wykonaniem innego (np. zanim obierzemy ziemniaki, musimy je kupić), ale równie dobrze czynności mogą zostać wykonane równocześnie lub w dowolnej kolejności (np. przed upieczeniem ciasta musimy kupić mąkę i jajka, choć nie ma znaczenia kolejność kupowania składników). Wynika z tego możliwość ustalenia więcej niż jednego topologicznego porządku wierzchołków dla niektórych grafów.
 |
Wierzchołki przedstawionego na rysunku grafu można posortować topologicznie na kilka sposobów, np.
|
[edytuj] Algorytmy
Najpopularniejsze algorytmy sortowania topologicznego działają w czasie Θ(|V|+|E|).
[edytuj] Usuwanie wierzchołków "niezależnych"
Jeden z takich algorytmów polega na stopniowym usuwaniu z grafu wierzchołków o stopniu wchodzącym 0 wraz z wychodzącymi z nich krawędziami. Kolejność, w jakiej wierzchołki będą usuwane, jest poszukiwanym rozwiązaniem.
Jeśli po usunięciu wszystkich takich wierzchołków (wraz z krawędziami) graf nie pozostanie pusty, oznacza to, że zawiera cykle.
By zastosować powyższy algorytm, należy wykorzystać kontener, w którym przechowywane będą wierzchołki do usunięcia.
Q ← Kolejka z wierzchołkami o stopniu wchodzącym równym 0
dopóki Q jest niepusta rób
usuń wierzchołek n z przodu kolejki Q
wypisz n
dla każdego wierzchołka m o krawędzi e od n do m rób
usuń krawędź e z grafu
jeżeli do m nie prowadzi żadna krawędź to
wstaw m do Q
jeżeli graf ma wierzchołki to
wypisz komunikat o błędzie (graf zawiera cykl)
Zważywszy na częste istnienie wielu rozwiązań problemu sortowania, Q nie musi być kolejką - równie dobrze może być stosem, kolejką priorytetową lub zwykłą tablicą.
