6. Graphen

6.4 Topologisches Sortieren

Definition (DAG). Ein gerichteter Graph, der keinen Kreis enthält, heißt azyklsicher gerichteter Graph, auf Englisch directed acyclic graph, als Abkürzung DAG.

Ein gerichteter azyklischer Graph, absichtlich chaotisch gezeichnet, damit es nicht so offensichtlich ist, dass er keine Kreise besitzt.

Topologische Sortierung Sei $G = (V,E)$ ein Digraph. Eine topologische Sortierung ist eine Auflistung $v_1,\dots,v_n$ der Knotenmenge $V$ (Auflistung heißt, dass jeder Knoten genau einmal vorkommt) mit der Eigenschaft $$ (v_i, v_j) \in E \Longrightarrow i < j \ . $$ In Worten, alle Kanten von $G$ gehen von links nach rechts in der Liste.

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.

Theorem Ein Digraph ist genau dann azyklisch, wenn er eine topologische Sortierung hat.

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.

Definition. Sei $G = (V,E)$ ein gerichteter Graph. Ein Knoten $u \in V$ heißt Quellknoten oder einfach Quelle, wenn es keine Kante $(v,u)$ gibt. Er heißt Senkenknoten oder einfach Senke, wenn es keine Kante $(u,v)$ gibt.

Lemma (DAGs, Quellen und Senken) Jeder endliche DAG hat mindestens einen Senkenknoten.

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

Nimm einen beliebigen Knoten $u_0$ und initialisiere einen Pfad $P := [u_0]$. Setze $k := 0$
while $\exists v \not \in P$ mit $(u_k, v) \in E$:

füge $v$ hinten an $P$ an und nenne es $u_{k+1}$
$k\texttt{++}$

In jedem Schritt wächst (\P\) um 1; es ist sicherlich ein Pfad, denn $v \not \in 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, \quad i \leq k$. Dann bilder $u_i, u_{i+1}, \dots, u_k$ einen Kreis. $\square$

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:

$L := \texttt{[]}$, die leere Liste
while $G$ noch Knoten besitzt:

finde einen Quellknoten $u$ in $G$
lösche $u$ und alle angrenzenden Kanten aus $G$
hänge $u$ hinten an die Liste.

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. $\square$

Ein Algorithmus für topologisches Sortieren

Wir haben oben nicht nur bewiesen, dass jeder DAG eine topologische Sortierung hat; wir haben auch einen Algorithmus angegeben, der eine solche findet. Allerdings ist dieser nicht besonders effizient, wenn wir ihn naiv implementieren; wie zum Beispiel finden wir einen Quellknoten schnell? Wenn wir hierfür $O(n)$ Zeit brauchen, dann ist der ganze Algorithmus $O(nm)$, also nicht gut. Besser geht es, wenn wir die in-degrees jedes Knoten in einer separate Liste speichern.

Definition Sei $G = (V,E)$ ein Digraph und $u \in V$. Die Raus-Nachbarn von $u$ sind alle Knoten, zu denen $u$ eine Kante hat; die Rein-Nachbarn von $u$ sind alle Knoten, die eine Kante nach $u$ haben: $$ \begin{eqnarray*} \outneighbors_G(u) & := \{v \in V \ | \ (u,v) \in E \} \\ \inneighbors_G(u) & := \{w \in V \ | \ (w,u) \in E \} \\ \end{eqnarray*} $$ Der Raus-Grad (bzw. Rein-Grad) von $u$ ist die Anzahl seiner Raus-Nachbarn (bzw. Rein-Nachbarn): $$ \begin{eqnarray*} \outdeg_G(u) & := |\outneighbors_G(u) | \\ \indeg_G(u) & := |\inneighbors_G(u)| \\ \end{eqnarray*} $$ Wenn aus dem Kontext klar ist, über welchen Graphen $G$ wir reden, dann lassen wir den Subscript gerne weg und schreiben einfach auch einfach $\outdeg(u), \indeg(u)$.

Wenn $G$ ein Graph ist, also ungerichtet, dann schreiben wir $\neighbors_G(u) := \{v \in V \ | \ \{u,v\} \in E\}$ und $\deg_G(u) := |\neighbors_G(u)|$ und sprechen von den Nachbarn und dem Grad von $u$ (Englisch degree).

Hier ist unser Algorithmus für topologisches Sortieren:

Algorithmus: Topologisches Sortieren mit Quellknoten-Löschen

Legen eine Liste currentIndeg = [indeg(u) for u in V] an, die in Rein-Grade im derzeitigen Graphen repräsentiert (erinnern Sie sich: wir "verstümmeln" den Graphen, indem wir Knoten löschen; jetzt simulieren wir das durch eine Liste von Rein-Graden.

currentSources = [u in V if indeg(u) == 0]

while currentSources not empty:
1. Nimm einen Knoten $u$ aus der Liste currentSources und entferne ihn aus ihr.
2. for v in outNeighbors(u)
  1. currentIndeg[v]--
  2. if currentIndeg[v] == 0: add v to currentSources

Dieser Algorithmus ist schneller, weil wir das Löschen nur simulieren, indem wir die Rein-Grade immer aktuell halten. Schritt 1 braucht $\Theta(n)$ Zeit, weil wir einfach zweimal durch $V$ gehen müssen. Da wir unseren Graphen mit Adjazenzlisten implementiert haben, können wir $\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 $\Theta(\outdeg(u))$ Zeit. Die Gesamtzeit ist also

$$ \Theta\left( n + \sum_{u \in V} \outdeg(u)\ \right) = \Theta(n + m), $$ da $\sum_{u \in V} \outdeg(u) = m$ gilt. Unser Algorithmus hat lineare Laufzeit.

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.

Algorithmus: Topologisches Sortieren mit Tiefensuche (DFS)

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

  for u in V: 
      dfsAndPrint(u)
  
  def dfsAndPrint(u):
      if visited[u]: 
          return 
      else :
          visited[u] = True 
          for v in outNeighbors(u):
              dfsAndPrint(v)
          L.append(u)      

  return L

Schauen wir uns ein Beispiel an.

Die ganze Animation finden Sie auch in topsort.pdf. Hier noch einmal das Endergebnis.

Wir sehen in der Mitte die verschiedenen DFS-Bäume. Nennen wir diese mal $T_1,\dots,T_k$.

Beobachtung Sei $G$ ein DAG. Die DFS-Bäume $T_1,\dots,T_k$ von $G$ haben folgende Eigenschaften:

Wenn $u ,v$ im gleichen Baum $T_i$ vorkommen und $u$ ein Vorfahre von $v$ ist, dann gibt es in $G$ einen Pfad von $u$ nach $v$ (den Pfad sehen Sie ja in $T_i$ selbst);
aber nicht von $v$ nach $u$ (sonst hätte $G$ einen Kreis);
der Knoten $u$ kommt später in $L$ als $v$; dies folgt direkt aus dem Code, weil dfsAndPrint(u) den Knoten $u$ erst am Schluß an $L$ anfügt, wenn alle rekursiven Aufrufe (zu denen ja auch dfsAndPrint(v) gehört), abgearbeitet sind.
Wenn $u$ in $T_i$ liegt und $v$ in einem weiter rechts gelegenen $T_j$, also $i < j$, dann gibt es keinen Pfad von $u$ nach $v$.

Beweis von Punkt 4.

Dies ist nicht so offensichtlich wie Punkte 1, 2, 3. Nehmen wir an, es gäbe einen solchen Pfad, also $u = u_0, u_1, \dots, u_l = v$. Sei $w$ der erste Knoten auf diesem Pfad, für den dfsAndPrint aufgerufen worden ist; zu dem Zeitpunkt, wo dfsAndPrint(w) aufgerufen wird, sind alle Knoten auf dem Teilpfad $w, \dots \dots, v$ unmarkiert. Die Tiefensuche wird also alle diese Knoten von $w$ aus erforschen; insbesondere liegt $w$ im gleichen DFS-Baum wie $v$, also in $T_j$. Da $w$ in einem weiter rechts gelegenen DFS-Baum als $u$ liegt, muss dfsAndPrint(w) später als dfsAndPrint(u) aufgerufen worden sein. Ein Widerspruch, weil wir ja angenommen haben, $w$ sei der erste solche Knoten.$\square$

Einfacher, aber nicht ganz formal korrekt ausgedrückt: gäbe es einen Pfad von $u$ nach $v$, dann hätte die Tiefensuche spätestens von $u$ aus (aber vielleicht schon zuvor) den Knoten $v$ besucht; $v$ könnte also nicht in einem weiter rechts gelegenen Baum als $u$ sein.

Theorem Die Liste $L$, die von unserem Algorithmus topSortDFS erstellt wird, ist eine topologische Sortierung in umgekehrter Reihenfolge. Das heißt, wenn $(u,v) \in E$, dann kommt $u$ rechts von $v$ in $L$.

Beweis. Für $w \in V$ sei $T_w$ der DFS-Baum, der $w$ enthält. Da $(u,v) \in E$ gilt, gibt es offensichtlich einen Pfad von $u$ nach $v$. Nach unserer obigen Beobachtung kann $T_v$ also nicht nach $T_u$ in der Liste der DFS-Bäume vorkommen. Es bleiben zwei Möglichkeiten:

$T_v$ steht links von $T_u$. Dann steht $v$ sicherlich links von $u$ in der Output-Liste $L$.
$T_u = T_v$. Dieser Fall ist schwieriger. Halten wir fest, dass $v$ kein Vorfahre von $u$ ist (ansonten würde der Pfad von $v$ nach $u$ zusammen mit der Kante $(u,v)$ einen Kreis schließen). Es gibt nun zwei Fälle:
1. wenn dfsAndPrint(u) vor dfsAndPrint(v) aufgerufen wird, dann wird dfsAndPrint(u) sicherlich einen Aufruf von dfsAndPrint(v) nach sich ziehen, und somit wird $v$ zuerst an $L$ angefügt werden;
2. wenn dfsAndPrint(v) vor dfsAndPrint(u), dann erforscht die Tiefensuche von $v$ aus einen Teilbaum $T'$ mit $v$ als Wurzelknoten; $u$ ist nicht in $T'$; alle Knoten von $T'$ werden also an $L$ angefügt, bevor die Tiefensuche $T'$ verlässt und weitermacht (und schließlich bei $u$ ankommt); also steht $v$ links von $u$ in $L$

In allen Fällen und Unterfällen erkennen wir, dass $v$ zuerst an $L$ angefügt wird und somit weiter links steht. $\square$