Sortowanie Topologiczne

Mirosław Mortka

Sortowanie topologiczne możemy wykonać wyłącznie na grafach nieskierowanych acyklicznych (DAG’ach – ang. directed acyclic graph). W wyniku jego wykonania uzyskujemy uporządkowany ciąg wierzchołków zgodny z czasami ich przetworzenia. Oznacza to, że jeżeli wierzchołek v znajdzie się po uporządkowaniu przed wierzchołkiem w, to znaczy że wierzchołek v musi być przetwarzany przed wierzchołkiem w.

Najprostszą implementację sortowania topologicznego możemy uzyskać wykorzystując algorytm DFS. Po wywołaniu algorytmu DFS dodajemy na początek listy uporządkowanych wierzchołków ten wierzchołek, który został całkowicie przetworzony (tzn. odwiedzono wszystkich jego sąsiadów).

Przykładowe zadanie

Rare order

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License