Sortowanie topologiczne: uporządkowanie grafu acyklicznego

Uporządkowanie grafu mającego „przed” i „po"

Graf acykliczny zorientowany (DAG) jest dokładnie tym, czym brzmieje: krawędzie mają kierunek, a nie ma cykli — nie ma sposobu na to, aby podążając po kierowanych krawędziach wrócić do punktu wyjścia. Gdy krawędzie grafu oznaczają „musi się zdarzyć przed” — skompiluj ten plik przed tym drugim, ukończ ten kurs przed tym drugim, oblicz tę komórkę arkusza kalkulacyjnego przed tą inną — uporządkowanie topologiczne to pełny porządek wszystkich wierzchołków tak, aby każda krawędź wskazywała z wierzchołka earlier na later. To formalna odpowiedź na pytanie „w jakim porządku mogę bezpiecznie wykonać wszystko to.”

Algorytm Kahn'a: odłącz węzły bez zależności

Najintuzyjniejszy algorytm (Kahn, 1962) śledzi indegree każdego węzła — liczbę krawędzi prowadzących do niego, czyli liczbę niestartujących wymagań początkowych. Każdy węzeł o indegree równej zero nie ma już niczego blokującego go, więc jest bezpieczny do wydruku; usunięcie go z grafu spowalnia indegree wszystkich węzłów, do których prowadziły krawędzie tego węzła, co może oswobodzić dodatkowe węzły.

kahn(graf): indegree[v] = liczba przychodzących krawędzi dla każdego węzła v kolejka = wszystkie węzły o indegree == 0 porządek = [] podczas gdy kolejka nie jest pusta: u = kolejka.pop() porządek.append(u) dla każdej krawędzi u -> v: indegree[v] -= 1 jeśli indegree[v] == 0: kolejka.push(v) jeśli długość porządku < liczbę węzłów w grafie: zwróć "wykryto cykl — nie ma jednoznacznej kolejności topologicznej" zwróć porządek demo interaktywna · odłączanie węzłów bez zależności z grafu zależności● LIVE Każdy węzeł i każda krawędź jest odwiedzany stałą liczbą razy, więc algorytm Kahn'a działa w czasie O(V + E). Porządek, który tworzy, nie musi być jednoznaczny — dwa węzły, które nigdy się nie zależą od siebie bezpośrednio ani pośrednio, mogą występować w dowolnej porządku względem siebie, więc DAG zwykle ma wiele poprawnych kolejności topologicznych.

kahn(graph):
  indegree[v] = number of incoming edges, for every node v
  queue = all nodes with indegree == 0
  order = []

  while queue not empty:
    u = queue.pop()
    order.append(u)
    for each edge u -> v:
      indegree[v] -= 1
      if indegree[v] == 0:
        queue.push(v)

  if len(order) < total node count:
    return "cycle detected — no topological order exists"
  return order

Alternatywa DFS: odwrotna postorder

Druga, równie popularna metoda polega na wykonaniu wyszukiwania w głębokości z każdego nieodwiedzonego węzła i zapisywaniu każdego węzła w chwili zakończenia jego wywołania DFS — po tym, jak wszystkie jego potomki już zakończyły. Odwrócenie listy zgodnie z porządkiem zakończeń daje prawidłową topologiczną kolejność, ponieważ węzeł nie może zakończyć przed tym, gdy każdy węzeł do którego się odnosi, już zakończył (potomek ten musiał być koniecznie odwiedzony i zakończony podczas tego samego wywołania DFS). Ta wersja jest elegancka i nie wymaga żadnej jasnej rejestrowania stopnia wejściowego, ale detekcja cyklu wymaga osobnego śledzenia bieżacego stosu rekurencji (odwiednienie węzła „zielonego” podczas nadal istniejącego na stosie oznacza cykl), co w przeciwieństwie do algorytmu Kahn'a, który dostaje detekcję cyklu za darmo jako efekt uboczny sprawdzenia końcowego liczebnika.

Cykly zniszczają wszystko

Jeśli graf zawiera cykl, nie może istnieć żadnej topologicznej kolejności: każdy węzeł w tym cyklu musiałby być jednocześnie przed i po innym węźle w tym samym cyklu, co jest kontradukcją logiczną. To dokładnie dlaczego sprawdzanie resztkowych węzłów w algorytmie Kanańskim działa jako detekcja cykli — węzły zatrapione wewnątrz cyklu zawsze pozostają z przynajmniej jednym przychodzącego krawędzi od tego samego cyklu i dlatego nigdy nie osiągną stopnia wejściowego równego zero, nigdy nie zostaną dodane do kolejki i nigdy nie dostaną się do wynikowej kolejności.

Gdzie to działa codziennie

Systemy budowania (Make, Bazel, graf zadań npm/yarn) topologicznie uporządkowują graf zależności celów tak, aby każdy cel był kompilowany tylko po tym, jak wszystkie zależne od niego cele zostaną skompilowane. Menadżery pakietów rozwiązywają kolejność instalacji w ten sam sposób. Planowanie wymagań kursu, ocena formuł w arkuszu kalkulacyjnym (rekalkulacja komórki B2 tylko po tym, jak każda komórka, której odwołuje się do niej, osiągnęła stan spokojny), oraz harmonogramy zadań w silnikach przepływów pracy rozproszonych wszystko w skrypcji redukują do tej samej problematyki: budowanie grafu "muszą nastąpić" zależności, a następnie uruchamianie algorytmu Kahn'a lub DFS poorder, aby znaleźć bezpieczny porządek wykonania — lub odkryć, że nie ma bezpiecznego porządku ze względu na wprowadzoną zależność cykliczną.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Topological Sort — Ordering a DAG i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.