Loading AI tools
Z Wikipedii, wolnej encyklopedii
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.
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.
|
Najpopularniejsze algorytmy sortowania topologicznego działają w czasie Θ(|V|+|E|).
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ą.
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
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.