6.4 Topologisches Sortieren

Falls $G$ zum Beispiel eine "Selbstschleife" $u,u$ hat (nach Definition von Digraphen nicht verboten), dann kann er keine topologische Sortierung haben: $u$ müsste ja als $v_i$ vorkommen, und die Bedingung würde dann $i<i$ verlangen, was natürlich falsch ist.

Beweis. Wir müssen zwei Richtungen zeigen; erstens, falls $G$ einen Kreis hat, dass er keine topologische Sortierung hat; zweitens, falls $G$ keinen Kreis hat, dass er eine topologische Sortierung hat.

Die erste Richtung ist einfacher. Wenn $G$ einen Kreis hat, dann können wir den hinschreiben: $C=\{w_0,w_1,\dots ,w_{k-1}\}$ mit $(w_i,w_{i+1})\in E$ für $i=0,\dots ,k-1$ (mit $i+1$ modulo $k$ interpretiert). Angenommen nun, $G$ hätte eine topologische Sortierung. Sei $w_i\in C$ der Knoten, der in der Auflistung $L=(v_1,\dots ,v_n)$ als letztes vorkommt, also am weitesten rechts, sagen wir $w_i=v_j$. Weil $w_{i+1}\in K$ ist, ist es weiter links in $L$, also $w_{i+1}=v_l$ für $l<j$. Das heißt aber, die Kante $(w_i,w_{i+1}$) geht in $L$ von rechts nach links. Ein Widerspruch.

Die andere Richtung ist anstrengender. Nehmen wir an, $G$ hätte keinen Kreis, und versuchen wir, eine topologische Ordnung zu finden. Verstehen Sie bitte, warum das konzeptuell schwieriger ist. Im ersten Fall hatten wir etwas: einen Kreis; damit konnten wir beginnen, zu arbeiten. Im zweiten Fall wissen wir um die Nichtexistenz von etwas. Wir haben also kein Objekt in der Hand, von dem wir ausgehen können. Um zu beweisen, dass ein DAG $G$ eine topologische Sortierung besitzt, werden wir einen Algorithmus entwickeln, der eine solche erzeugt. Effizienz ist uns hierbei egal. Die werden wir später verbessern. Als erstes brauchen wir eine Definition und eine Beobachtung.

Beweis. Wir beschreiben einen Algorithmus, der entweder (1) einen Senkenknoten findet oder (2) einen Kreis.

1. Nimm einen beliebigen Knoten $u_0$ und initialisiere einen Pfad $P:=[u_0]$. Setze $k:=0$
2. while $\mathrm{\exists }v\notin P$ mit $(u_k,v)\in E$:
1. füge $v$ hinten an $P$ an und nenne es $u_{k+1}$
2. $k\mathtt{\text{++}}$

In jedem Schritt wächst (\P\) um 1; es ist sicherlich ein Pfad, denn $v\notin P$ stellt sicher, dass kein Knoten zweimal in die Liste $P$ eingefügt wird. Da $G$ endlich ist, muss die Schleife spätestens nach $n-1$ durchläufen terminieren. Warum terminiert sie? Entweder gibt es keine Kanten, die aus dem Endknoten $u_k$ ausgehen; dann ist $u_k$ eine Senke. Oder es gibt eine solche Kante; nennen wir sie $(u_k,v)$, aber $v$ ist bereits in $P$, also $v=u_i,i\le k$. Dann bilder $u_i,u_{i+1},\dots ,u_k$ einen Kreis. $◻$

Mit der gleichen Technik können Sie beweisen, dass jeder DAG einen Quellknoten hat: Sie müssen einfach den Pfad $P$ "rückwärts" bauen. Kehren wir nun zu unserem ursprünglichen Vorhaben zurück. Wir haben einen DAG $G$ und wollen eine topologische Sortierung. Hier ist der Algorithmus:

1. $L:=\mathtt{\text{[]}}$, die leere Liste
2. while $G$ noch Knoten besitzt:
1. finde einen Quellknoten $u$ in $G$
2. lösche $u$ und alle angrenzenden Kanten aus $G$
3. hänge $u$ hinten an die Liste.
3. return $L$

Stellen wir noch kurz sicher, dass die Liste $L$ eine topologische Sortierung darstellt. Betrachten wir eine Kante $(u,v)$ im Graphen $G$ (hier bezeichnet $G$ den ursprünglichen Graphen, also vor der Schleife, die nach und nach alle Knoten löscht; wir stellen uns vor, dass wir $G$ nach der Schleife wiederherstellen; beachten Sie: wir sind hier innerhalb eines mathematischen Beweises, nicht innerhalb eines Programms; wir müssen also nicht explizit eine "Kopie" von $G$ anfertigen und verwahren, solange wir uns im klaren sind, was $G$ bedeutet). Wir müssen zeigen, dass $u$ in $L$ vor $v$ vorkommt. Dies ist einfach: $v$ kann kein Quellknoten sein, solange $u$ nicht gelöscht worden ist; also wird $u$ vor $v$ gelöscht - und in die Liste eingefügt. $◻$

Ein Algorithmus für topologisches Sortieren

Dieser Algorithmus ist schneller, weil wir das Löschen nur simulieren, indem wir die Rein-Grade immer aktuell halten. Schritt 1 braucht $\mathrm{\Theta }(n)$ Zeit, weil wir einfach zweimal durch $V$ gehen müssen. Da wir unseren Graphen mit Adjazenzlisten implementiert haben, können wir $\text{indeg}(u)$ in konstanter Zeit ablesen. Die while-Schleife Schritt 2 führt genau $n$ Durchgänge aus, weil sie in jedem Durchgang genau einen Knoten löscht. Schritt 2.a geht in konstanter Zeit; Schritt 2.b benötigt $\mathrm{\Theta }(\text{outdeg}(u))$ Zeit. Die Gesamtzeit ist also

Topologisches Sortieren mit Tiefensuche

Ich werde Ihnen nun einen weiteren Algorithmus vorstellen, der in linearer Zeit eine topologische Sortierung findet. Dieser hat zwei Vorteile. Erstens ist er vom Code her einfacher. Zweitens wird er später Baustein für einen nichttrivialen Algorithmus sein, der die starken Zusammenhangskomponenten (werden wir später erklären) eines Digraphs bestimmt.

def topSortDFS(G):                                    
  L = [] das wird unsere topologisch sortierte Liste
  visited = [False, ..., False] Markierung für die Tiefensuche

  for u in V: 
      if visited[u]: 
          continue

      stack = new Stack(u)
      visited[u] = True

      while (stack.nonEmpty()):
          v = stack.top() 
          if v has unvisited neighbor w:
              visited[w] = True
              stack.push(w)
          else: # wir haben alle Nachbarn von v erkundet 
              stack.pop()
              L.append(v)
  return L

Schauen wir uns ein Beispiel an.

Hier noch einmal das Endergebnis mit den Bäumen, die die Tiefensuche konstruiert hat:

Wir werden nun sehen, dass $L$ eine topologische Sortierung in umgekehrter Reihenfolge darstellt: