Sortowanie topologiczne
Sortowanie topologiczne skierowanego grafu acyklicznego – liniowe uporządkowanie wierzchołków, w którym jeśli istnieje krawędź skierowana prowadząca od wierzchołka do to znajdzie się przed wierzchołkiem 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.
Zastosowanie
[edytuj | edytuj kod]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.
|
Algorytmy
[edytuj | edytuj kod]Najpopularniejsze algorytmy sortowania topologicznego działają w czasie Θ(|V| |E|).
Usuwanie wierzchołków „niezależnych”
[edytuj | edytuj kod]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 krawędzie 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ą.
Wykorzystanie algorytmu DFS
[edytuj | edytuj kod]Kolejny algorytm, którym można się posłużyć, to DFS. Wystarczy, że podczas wykonywania jego tradycyjnej wersji będziemy na początek listy dodawać aktualnie przetworzony wierzchołek, a otrzymamy listę w pożądanym porządku.
L ← Lista wierzchołków posortowanych w kolejności topologicznej dla każdego wierzchołka rób jeśli nie był jeszcze odwiedzony, ustaw jako odwiedzony dla każdej krawędzi z niego wychodzącej rób jeśli prowadzi do nieodwiedzonego jeszcze wierzchołka przetwórz wierzchołek rekurencyjnie wstaw wierzchołek na początek listy