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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License