Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


32. Gerichtete Graphen



Streng zusammenhängende Komponenten

Falls ein Graph einen gerichteten Zyklus enthält (falls wir von einem Knoten aus zu diesem gleichen Knoten zurück gelangen können, indem wir Kanten in der angegebenen Richtung folgen), so handelt es sich um keinen dag, und er kann nicht topologisch sortiert werden: Unabhängig davon, welcher Knoten im Zyklus zuerst ausgegeben wird, wird stets ein anderer Knoten existieren, der auf diesen zeigt und der noch nicht ausgegeben wurde. Die Knoten im Zyklus sind in dem Sinne untereinander erreichbar, daß es einen Weg gibt, um von jedem Knoten im Zyklus zu jedem anderen Knoten im Zyklus und zurück zu gelangen. Andererseits ist es selbst dann, wenn ein Graph zusammenhängend ist, unwahrscheinlich, daß jeder Knoten von jedem anderen aus über einen gerichteten Pfad erreicht werden kann. Tatsächlich lassen sich die Knoten in Mengen einteilen, die streng zusammenhängende Komponenten genannt werden; diese haben die Eigenschaft, daß alle Knoten innerhalb einer Komponente untereinander erreichbar sind, daß es jedoch keinen Weg gibt, um von einem Knoten einer Komponente zu einem Knoten einer anderen Komponente und zurück zu gelangen. Die streng zusammenhängenden Komponenten des gerichteten Graphen in Abbildung 32.1 sind zwei einzelne Knoten B und K, ein Paar von Knoten H I, eine Gruppe von drei Knoten D E F und eine große Komponente mit sechs Knoten A C G J L M. Beispielsweise gehört Knoten A zu einer anderen Komponente als Knoten F, da zwar ein Pfad von A nach F existiert, jedoch kein Weg, um von F nach A zu gelangen.

Die streng zusammenhängenden Komponenten eines gerichteten Graphen können, wie der Leser sicher erwartet hat, unter Benutzung einer Variante der Tiefensuche gefunden werden. Das Verfahren, das wir betrachten wollen, wurde 1972 von R. E. Tarjan entwickelt. Da es auf der Tiefensuche beruht, läuft es in einer zu V + E proportionalen Zeit ab, doch in Wirklichkeit ist es ein sehr wohldurchdachtes Verfahren. Es erfordert nur wenige einfache Modifikationen unserer grundlegenden Prozedur visit, doch bevor es von Tarjan vorgestellt wurde, war für dieses Problem kein in linearer Zeit ablaufender Algorithmus bekannt, obwohl viele Wissenschaftler daran gearbeitet hatten.

Die modifizierte Variante der Tiefensuche, die wir benutzen, um die streng zusammenhängenden Komponenten eines Graphen zu finden, ist dem Programm sehr ähnlich, das wir in Kapitel 30 für die Bestimmung von zweifach zusammenhängenden Komponenten untersucht haben. Die unten angegebene rekursive Funktion visit verwendet die gleiche Berechnung von min, um den höchsten Knoten zu finden, der (über eine nach oben führende Verbindung) von irgendeinem Nachfolger des Knotens k aus erreichbar ist, benutzt jedoch den Wert von min in einer etwas anderen Weise, um die streng zusammenhängenden Komponenten auszudrucken:

    function visit(k: integer): integer;
      var t: link;
      m,min: integer;
      begin
      id:=id+1; val[k]:=id; min:=id;
      stack[p]:=k; p:=p+1;
      t:=adj[k];
      while t<>z do
        begin
        if val[t^.v]=0
          then m:=visit(t^.v)
          else m:=val[t^.v];
        if m<min then min:=m;
        t:=t^.next
        end;
      if min=val[k] then
        begin
        repeat
          p:=p-1; write(name(stack[p]));
          val[stack[p]]:=V+1
        until stack[p]=k;
        writeln
        end;
      visit:=min;
      end;

Dieses Programm legt die Namen der Knoten zu Beginn von visit in einem Stapel ab, entnimmt sie und gibt sie dann nach dem Besuchen des letzten Elements jeder streng zusammenhängenden Komponente aus. Die entscheidende Stelle bei der Berechnung ist der Test am Ende, ob min=val[k] gilt; ist dies der Fall, so gehören alle Knoten, die seit Eintritt in die Schleife angetroffen wurden (mit Ausnahme der bereits ausgegebenen), der gleichen streng zusammenhängenden Komponente an wie k. Wie gewöhnlich kann dieses Programm leicht dahingehend modifiziert werden, daß kompliziertere Operationen ausgeführt werden als eine einfache Ausgabe der Komponenten.

Eigenschaft 32.4 Die streng zusammenhängenden Komponenten eines Graphen können in linearer Zeit gefunden werden.

Ein exakter Beweis der Tatsache, daß der obige Algorithmus die streng zusammenhängenden Komponenten berechnet, würde über den Rahmen dieses Buches hinausgehen, doch wir können die Grundideen skizzieren. Das Verfahren beruht auf zwei Beobachtungen, die wir bereits in anderem Zusammenhang gemacht haben. Erstens, wenn wir das Ende eines Aufrufs von visit für einen Knoten erreicht haben, werden wir in der gleichen streng zusammenhängenden Komponente keine weiteren Knoten mehr antreffen (da alle Knoten, die von diesem Knoten aus erreicht werden können, verarbeitet worden sind, wie wir oben für das topologische Sortieren bemerkt haben). Zweitens stellen die nach oben führenden Verbindungen im Baum einen zweiten Pfad von einem Knoten zu einem anderen dar und verbinden die streng zusammenhängenden Komponenten miteinander. Wie im Falle des Algorithmus aus Kapitel 30 für die Bestimmung von Gelenkpunkten verfolgen wir den am weitesten oben befindlichen Vorgänger, der von irgendeinem Nachfolger des jeweiligen Knotens über eine nach oben führende Verbindung erreichbar ist. Falls nun ein Knoten x keine Nachfolger oder nach oben führende Verbindungen im Tiefensuchbaum besitzt, oder falls er einen Nachfolger im Tiefensuchbaum mit einer nach oben führenden Verbindung besitzt, die auf x zeigt, doch keine Nachfolger mit nach oben führenden Verbindungen, die auf Knoten weiter oben im Baum zeigen, so bilden dieser Knoten und alle seine Nachfolger (mit Ausnahme solcher Knoten, die die gleiche Eigenschaft besitzen, und ihrer Nachfolger) eine streng zusammenhängende Komponente. So genügen im Tiefensuchbaum in Abbildung 32.2 die Knoten B und K der ersten Bedingung (so daß sie selbst streng zusammenhängende Komponenten darstellen), und die Knoten F (der F E D repräsentiert), H (der H I repräsentiert) und A (der A G J L M C repräsentiert) genügen der zweiten Bedingung. Die Elemente der Komponente, die durch A repräsentiert wird, werden gefunden, indem B K F und ihre Nachfolger gelöscht werden (sie erscheinen in früher ermittelten Komponenten). Jeder Nachfolger y von x, der nicht die gleiche Eigenschaft besitzt, hat einen Nachfolger, der eine nach oben führende Verbindung besitzt, die auf einen im Baum höher als y befindlichen Knoten zeigt. Es existiert ein Pfad von x nach y, der im Baum abwärts führt; ein Pfad von y nach x kann auch gefunden werden, indem von y abwärts zu dem Knoten gegangen wird, der die nach oben an y vorbeiführende Verbindung besitzt, und indem dann der gleiche Prozeß fortgesetzt wird, bis x erreicht ist. Eine wesentliche zusätzliche Vorkehrung besteht darin, daß wir, nachdem wir mit einem Knoten fertig sind, diesem Knoten einen hohen Wert von val geben, so daß Querverbindungen zu diesem Knoten ignoriert werden. w.z.b.w.

Dieses Programm liefert eine täuschend einfache Lösung für ein relativ kompliziertes Problem. Es veranschaulicht sicher die Schwierigkeiten, die bei der Suche in gerichteten Graphen auftreten, wobei diese Schwierigkeiten (in diesem Falle) mit Hilfe eines sorgfältig erstellten rekursiven Programms gelöst werden können.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]