Previous Contents Next

9   Graphen

Literatur: Kapitel 23 aus [CLR90]. Breitensuche stammt von Moore [Moo59]. Der Erfinder der Tiefensuche scheint unbekannt. Der angegebene Algorithmus für die starken Zusammenhangskomponenten ist von Tarjan [Tar72].
Inhalt Graphen ·Repräsentierungen ·Erreichbarkeit ·Breitensuche ·Tiefensuche ·backtracking ·topologisches Sortieren ·Berechnung starker Zusammenhangskomponenten
Suchen in Graphen
Graphen und ihre Repräsentierung
Definition 4  [Graph]   Ein (gerichteter) Graph G = (V,E): V Menge von Knoten, EÍ V × V Kanten.
Breitensuche
Prinzip
Breitensuche (2) 



bfs (G,s) =      // Graph und Quellknoten 
  for each vertex u in V[G] - {s}
  do color[u] := white
     d[u]     := $\infty$;
     p[u]     := nil
  done;
  color[s]    := gray;
  d[s]        := 0;
  p[s]        := nil;
  Q.enqueue(s);                 // beginne mit der Quelle

  while not Q.isempty()
  do
     u := Q.head();             // noch kein dequeue!
     for each v in Adj[u]       // alle Nachbarn.
     do
        if   color[v] = white
        then color[v] := gray;
             d[v]     := d[u] + 1;
             p[v]     := u
             Q.enqueue(v)      // speichere den Nachbarn
        fi;
     done;
     Q.dequeue()            // u ist abgearbeitet
     color(u) := black;     // und als fertig markiert
  done


Breitensuchalgorithmus: Analyse
Korrektheitsargument
Siehe Vorlesung

Tiefensuche
Algorithmus (1) 

DFS(G)                           // Gerichteter Graph
  for all vertices $v \in V[G]$  // Initialisierung
  do 
     color[u] := white;          
      pred[u] := nil; 
  od
  time := 0;                     // Ende der Initialisierung
  for all vertices  $u \in V[G]$
  do
      if color[u] = white then DFS-Visit(u); // eigentl. Tiefensuche
  done;
Algorithmus (2) 

DFS-visit(u)                       // Eigentliche Tiefensuche
  color[u] := gray;                // Knoten entdeckt
  time := time + 1;  d[u] := time; // merke Entdeckungszeit
  for each v in Adj[u]             // erkunde Kante (u,v)
  do  if   color[v] = white
      then pred[v] := u            // pred = Entdeckerknoten
           DFS-visit(v)            // rek. Abstieg
  done;
  color[u] := black;               // u ist fertig, merke
  time := time + 1; f[u] := time;  // die Fertigstellzeit


Tiefensuche: Analyse


Weitere Eigenschaften
[Klammerung] Gegeben zwei Knoten u, v aus G = (V, E). Es gilt genau eine der folgenden Bedingungen:
  1. [d[u],f[u]] ist echtes Teilintervall von [d[v], f[v]], u ist Nachfahre von v in Tiefensuchbaum
  2. Symmetrisch.
  3. [d[u],f[u]] und [d[v], f[v]] disjunkt
Knoten v ist echter Nachfolger von u im Tiefensuchwald gdw. d[u] < d[v] < f[v] < f[u]

Topologisches Sortieren


Zunächst ein paar Definitionen:
Definition 5   Gegeben eine binäre Relation R. Die reflexive, transitive Hülle R of R ist gegeben als die kleinste binäre Relation sodaß x R x und x R y R z impliziert x R z. Mit R+ ist die Relation R R gemeint.
Definition 6   Eine binäre Relation R Í S × S auf einer Menge S ist eine Halbordnung (Notation dann oft £ für R) wenn sie reflexiv, transitiv, und antisymmentrisch ist. Eine totale oder lineare Ordnung ist eine Halbordnung mit der zusätzlichen Eigenschaft der Vergleichbarkeit. (" x,y. x£ y oder y£ x)
Definition 7  [DAG]   Ein gerichteter, azyklischer Graph (DAG) ist ein gerichteter Graph ohne Zyklen, d.h., es für alle Knoten u, v Î V gilt: Wenn u ®+ v, dann u ¹ v.

Topologisches Sortieren (2) 



Topological-Sort(G)               // G ist ein DAG

  call DFS(G) to compute  finishing-times f[v] for all v;
  as each vertex is finished, insert it onto the front of a list;
  return the linked list


Topologisches Sortieren (3)
Satz 2  [Weiße Pfade]   Gegeben Graph G. Im Tiefensuchwald für G gilt: v ist Nachfahre von u gdw. zur Zeit d[u] der Knoten v durch u auf einem weißen Pfad erreichbar ist.12

Lemma 3   Ein gerichteter Graph ist azyklisch gdw. die Tiefensuche keine Rückwärtskanten produziert.
Beweis: Sei G zyklisch Þ es gibt einen Zyklus c: w ®+ w. Sei v der erste entdeckte Knoten aus c und u sein Vorgänger im Zyklus. Zur Zeit d[v]: weißer Pfad v ®* u  Þ  u wird Nachfolger im Tiefensuchwald Þ Behauptung ((u,v) ist Rückwärtskante). Þ DFS findet Rückwärtskante (v,u), andererseits u ®* v mittels Baumkanten (weil u Vorgänger von v im Tiefensuchbaum)


Lemma 4  [Korrektheit]   Der Algorithmus angewandt auf einen DAG, liefert eine topologische Sortierung.
Beweis: Prüfen der Kompatibilität: falls u ®+ v in G, dann f[u] < f[v]. Sei (u,v) eine Kante. Wenn sie mit DFS erkundet wird, ist v nicht Grau (sonst wäre v ein Vorfahre Þ Rückwärtskante) Þ v ist weiß oder schwarz. v weiß v wird Nachfahre von u Þ f[v] < f[u] v schwarz Dann sofort f[v] < f[u]


Starke Zusammenhangskomponenten


Definition 8  [Starker Zusammenhang]   Gegeben gerichteter Graph G = (V, E). Eine starke Zusammenhangskomponente von G ist eine maximale Knotenmenge UÍ V mit: für alle u1, u2 Î U gilt u1®* u2 und u2®*u1.
Algorithmus 



Strongly-connected-components(G)    // G: gerichteter Graph

  call DFS(G) to obtain finishing times f[u] for the vertices;

  compute $G^t$ = transpose(G)        // transponiere G

  call DFS($G^t$), but in the main loop of DFS, 
       consider the vertices in order of 
       decreasing f[u]

  output the vertices of each tree in the depth-first 
      forest from the previous step as a separated strongly 
      connected component.




Analyse
Lemma 5   Der Vorvater f(u) bzgl. einer Tiefensuche ist ein Vorgänger von u,
Für alle Knoten u gilt: u und f(u) liegen in der selben starken Zusammenhangskomponente.

Beweis: Folgt direkt aus dem vorangegangenen und der Definition von Vorvater.


Analyse (2)


January 23, 2001
Previous Contents Next