Robert Sedgewick: Algorithmen

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


29. Elementare Algorithmen für Graphen



Darstellung

Um Graphen mit einem Programm verarbeiten zu können, müssen wir zuerst entscheiden, wie sie im Computer dargestellt werden sollen. Wir wollen zwei gewöhnlich zur Anwendung kommende Darstellungsarten betrachten; die Entscheidung zwischen ihnen hängt vor allem davon ab, ob der Graph dicht oder licht ist, obwohl die Art der auszuführenden Operationen wie üblich ebenfalls eine wichtige Rolle spielt.

Der erste Schritt zur Darstellung eines Graphen besteht darin, die Namen der Knoten auf ganze Zahlen zwischen 1 und V abzubilden. Der Hauptgrund hierfür ist, daß es ermöglicht werden soll, mittels Feldindizes schnell auf die jedem Knoten entsprechende Information zuzugreifen. Für diesen Zweck kann jede standardmäßige Suchmethode verwendet werden; zum Beispiel können wir die Knotennamen in ganze Zahlen zwischen 1 und V umwandeln, indem wir eine Hash-Tabelle oder einen binären Baum führen, der durchsucht werden kann, um zu einem beliebigen gegebenen Knotennamen die entsprechende ganze Zahl zu finden. Da wir diese Methoden bereits betrachtet haben, setzen wir voraus, daß eine Funktion index zur Verfügung steht, die Knotennamen in ganze Zahlen zwischen 1 und V umwandelt, und eine Funktion name, die ganze Zahlen in Knotennamen umwandelt. Damit sich unsere Algorithmen leicht nachvollziehen lassen, benutzen wir einbuchstabige Knotennamen, wobei der i-te Buchstabe des Alphabets der Zahl i entspricht. Obwohl sich name und index für unsere Beispiele sehr leicht implementieren lassen, erleichtern sie es, unter Anwendung der Methoden aus den Kapiteln 14-17 die Algorithmen dahingehend zu erweitern, daß sie für Graphen mit realen Knotennamen benutzt werden können.

Die allereinfachste Darstellungsweise für Graphen ist die Darstellung als sogenannte Adjazenzmatrix. Es wird ein Feld der Größe V mal V aus booleschen Variablen geführt, wobei a[x,y] auf true gesetzt wird, wenn eine Kante von Knoten x zu Knoten y vorhanden ist, und auf false, wenn das nicht der Fall ist. Die Adjazenzmatrix für den Graph in Abbildung 29.1 ist in Abbildung 29.3 angegeben (1 bedeutet true und 0 bedeutet false).

Abbildung 29.3
Abbildung 29.3 Darstellung mittels Adjazenzmatrix.

Wie wir sehen, wird jede Kante in Wirklichkeit durch zwei Bits dargestellt: Eine Kante, die x und y verbindet, wird sowohl in a[x,y] als auch in a[y,x] durch »true« dargestellt. Obwohl Platz gespart werden kann, indem nur die Hälfte dieser symmetrischen Matrix gespeichert wird, ist es in Pascal nicht zweckmäßig, dies zu tun, und die Algorithmen sind mit der vollständigen Matrix etwas einfacher. Weiterhin ist es gewöhnlich zweckmäßig anzunehmen, daß eine »Kante« von jedem Knoten zu sich selbst existiert, weshalb a[x,x] für x von 1 bis V auf 1 gesetzt wird. (In manchen Fällen ist es günstiger, die Elemente auf der Diagonalen auf 0 zu setzen; es steht uns frei, das zu tun, wenn es angebracht ist.)

Ein Graph ist durch eine Menge von Knoten und eine Menge von sie verbindenden Kanten definiert. Zur Eingabe eines Graphen müssen wir uns auf ein Format einigen, um diese Mengen einzulesen. Eine Möglichkeit wäre, die Adjazenzmatrix selbst als Eingabeformat zu verwenden, doch wie wir sehen werden, ist dies für lichte Graphen unzweckmäßig. Stattdessen wollen wir ein direkteres Format benutzen: Wir lesen zuerst die Namen der Knoten und dann Paare von Knotennamen (welche Kanten definieren) ein. Wie bereits erwähnt wurde, besteht eine einfache Vorgehensweise darin, die Knotennamen in eine Hash-Tabelle oder einen binären Suchbaum einzulesen und jedem Knotennamen eine ganze Zahl zuzuweisen. Diese wird benutzt, um auf knotenindizierte Felder von der Art der Adjazenzmatrix zuzugreifen. Dem i-ten eingelesenen Knoten kann die Zahl i zugewiesen werden. Im Interesse der Einfachheit unserer Programme lesen wir zuerst V und E ein, dann die Knoten und die Kanten. Eine andere Möglichkeit wäre, die Eingabe mit einem Begrenzer zu realisieren, der die Knoten von den Kanten trennt; das Programm könnte V und E dann aus den Eingabedaten bestimmen. (In unseren Beispielen benutzen wir für die Knotennamen die ersten V Buchstaben des Alphabets. Man könnte daher sogar eine noch einfachere Methode anwenden, nämlich V und E einlesen und anschließend E aus den ersten V Buchstaben des Alphabets gebildete Paare von Buchstaben.) Die Reihenfolge, in der die Kanten erscheinen, ist nicht wesentlich, da alle Kantenanordnungen den gleichen Graph darstellen und die gleiche Adjazenzmatrix ergeben, so wie sie durch das folgende Programm berechnet wird:

    program adjmatrix(input,output);
      const maxV=50;
      var j,x,y,V,E: integer;
          a: array[1..maxV,1..maxV] of boolean;
      begin
      readln(V,E);
      for x:=1 to V do
        for y:=1 to V do a[x,y]:=false;
      for x:=1 to V do a[x,x]:=true;
      for j:=1 to E do
        begin
        readln(v1,v2);
        x:=index(v1); y:=index(v2);
        a[x,y]:=true; a[y,x]:=true
        end;
      end.

Die Typen der Variablen v1 und v2 wurden in diesem Programm weggelassen, ebenso der Programmabschnitt für index. Diese können in Abhängigkeit von der gewünschten Eingabedarstellung des Graphen in einfacher Weise hinzugefügt werden. (Für unsere Beispiele könnten v1 und v2 vom Typ char sein, und index könnte eine einfache Funktion sein, die die Pascal-Funktion ord verwendet.)

Die Darstellung mit Hilfe der Adjazenzmatrix ist nur dann zufriedenstellend, wenn die zu verarbeitenden Graphen dicht sind: Die Matrix benötigt V2 Bits Speicherplatz und V2 Schritte allein für ihre Initialisierung. Falls die Anzahl der Kanten (die Anzahl der 1-Bits in der Matrix) proportional zu V2 ist, mag dies akzeptabel sein, da dann auf jeden Fall ungefähr V2 Schritte benötigt werden, um die Kanten einzulesen. Falls der Graph jedoch licht ist, könnte allein die Initialisierung der Matrix zum dominierenden Faktor für die Laufzeit eines Algorithmus werden. Dies könnte auch die beste Darstellung für einige Algorithmen sein, die mehr als V2 Schritte für ihre Ausführung benötigen.

Betrachten wir nun eine Darstellung, die für nicht so dichte Graphen geeigneter ist. Bei der Darstellung als Adjazenzstruktur werden für jeden Knoten alle mit ihm verbundenen Knoten in einer Adjazenzliste für diesen Knoten aufgelistet. Dies läßt sich leicht mit verketteten Listen realisieren, wie das nachstehende Programm zeigt, das die Adjazenzstruktur für den Graph aus unserem Beispiel erzeugt. Die verketteten Listen werden wie gewöhnlich mit einem künstlichen Knoten z am Ende (welcher auf sich selbst zeigt) erzeugt. Die künstlichen Knoten für den Anfang der Listen werden in einem knotenindizierten Feld adj gespeichert. Um zu dieser Darstellung des Graphen eine Kante hinzuzufügen, die x mit y verbindet, fügen wir x zu der Adjazenzliste von y und y zu der Adjazenzliste von x hinzu:

    program adjlist(input,output);
      const maxV=1000;
      type link=^node;
           node=record v: integer; next: link end;
      var j,x,y,V,E: integer;
          t,z: link;
          adj: array[1..maxV] of link;
      begin
      readln(V,E);
      new(z); z^.next:=z;
      for j:=1 to V do adj[j]:=z;
      for j:=1 to E do
        begin
        readln(v1,v2);
        x:=index(v1); y:=index(v2);
        new(t); t^.v:=x; t^.next:=adj[y]; adj[y]:=t;
        new(t); t^.v:=y; t^.next:=adj[x]; adj[x]:=t;
        end;
      end.

Falls die Kanten in der Reihenfolge AG AB AC LM JM JL JK ED FD HI FE AF GE erscheinen, erzeugt das obige Programm die Adjazenzlistenstruktur, die in Abbildung 29.4 dargestellt ist. Wir bemerken wiederum, daß jede Kante zweimal dargestellt wird: Eine Kante, die x und y verbindet, wird in der Adjazenzliste von y als Knoten dargestellt, der x enthält, und in der Adjazenzliste von x als Knoten, der y enthält. Es ist wesentlich, daß beide aufgenommen werden, da andernfalls einfache Fragen wie »Welche Knoten sind mit Knoten x direkt verbunden?« nicht effizient beantwortet werden könnten.

Abbildung 29.4
Abbildung 29.4 Eine Darstellung mit Hilfe einer Adjazenzstruktur.

Für diese Darstellung ist die Reihenfolge, in der die Kanten bei der Eingabe erscheinen, sehr wichtig: Sie bestimmt (zusammen mit der benutzten Einfügemethode in die Liste) die Reihenfolge, in der die Knoten in den Adjazenzlisten erscheinen. Folglich kann der gleiche Graph in einer Adjazenzlistenstruktur auf viele unterschiedliche Weisen dargestellt werden. Tatsächlich läßt sich nur schwer vorhersagen, wie die Adjazenzlisten aussehen werden, wenn man nur die Folge der Kanten betrachtet, da jede Kante Einfügungen in zwei Adjazenzlisten erfordert.

Die Reihenfolge, in der Kanten in der Adjazenzliste erscheinen, beeinflußt wiederum die Reihenfolge, in der Kanten durch Algorithmen verarbeitet werden. Das heißt, daß die Struktur der Adjazenzliste bestimmt, wie verschiedene Algorithmen, die wir betrachten werden, den Graph »sehen«. Obwohl ein Algorithmus unabhängig von der Anordnung der Kanten in den Adjazenzlisten zu einer richtigen Lösung gelangen muß, könnte er für verschiedene Reihenfolgen über sehr unterschiedliche Berechnungsfolgen zu dieser Lösung gelangen. Weiterhin können, wenn mehr als eine »richtige Lösung« existiert, verschiedene Reihenfolgen der Eingabedaten zur Ausgabe verschiedener Ergebnisse führen.

Einige einfache Operationen werden durch diese Darstellung nicht unterstützt. Zum Beispiel könnte man beabsichtigen, einen Knoten x und alle mit ihm verbundenen Kanten zu löschen. Dafür genügt es nicht, Knoten aus der Adjazenzliste zu löschen: Durch jeden Knoten in der Adjazenzliste wird ein weiterer Knoten vorgegeben, dessen Adjazenzliste durchsucht werden muß, um einen x entsprechenden Knoten zu löschen. Dieses Problem kann beseitigt werden, indem man die beiden Knoten der Liste, die einer bestimmten Kante entsprechen, miteinander verkettet und damit die Adjazenzlisten zu doppelt verketteten Listen macht. Wenn dann eine Kante entfernt werden soll, können beide Knoten, die dieser Kante entsprechen, schnell gelöscht werden. Natürlich ist die Verarbeitung dieser zusätzlichen Verkettungen mühsam, und sie sollten nur dann aufgenommen werden, wenn Lösch- oder ähnliche Operationen benötigt werden.

Aus solchen Überlegungen wird auch klar, warum wir keine »direkte« Darstellung für Graphen benutzen, eine Datenstruktur, die den Graph exakt modelliert, mit Knoten, die als zugeordnete Datensätze dargestellt sind, und Listen von Kanten, die Verbindungen zu Knoten anstelle von Knotennamen enthalten. Wie sollte man einem derartig dargestellten Graph eine Kante hinzufügen?

Gerichtete und gewichtete Graphen werden mit Hilfe ähnlicher Strukturen dargestellt. Für gerichtete Graphen bleibt alles unverändert, mit der Ausnahme, daß jede Kante nur einmal dargestellt wird: Eine Kante von x nach y wird durch true in a[x,y] in der Adjazenzmatrix oder durch das Erscheinen von y in der Adjazenzliste von x in der Adjazenzstruktur dargestellt. Demzufolge kann man sich einen ungerichteten Graph als einen gerichteten Graph vorstellen, der gerichtete Kanten besitzt, die zwischen jedem Paar von durch eine Kante verbundenen Knoten in beiden Richtungen verlaufen. Für gewichtete Graphen bleibt ebenfalls alles genauso, nur daß die Adjazenzmatrix mit Gewichten anstatt mit booleschen Werten ausgefüllt wird (wobei zur Darstellung von false irgendein nicht existierendes Gewicht benutzt wird), oder daß in der Adjazenzstruktur ein Feld für das Gewicht der Kante in die Datensätze der Adjazenzlisten eingefügt wird.

Oft ist es notwendig, mit den Knoten oder Ecken eines Graphen weitere Informationen zu verknüpfen, um die Möglichkeit zu schaffen, mit ihm kompliziertere Objekte zu modellieren, oder um in komplizierten Algorithmen Verwaltungs-Informationen zu speichern. Mit jedem Knoten verknüpfte zusätzliche Informationen können untergebracht werden, indem Hilfsfelder mit der Knotennummer als Index verwendet werden, oder indem adj in der Adjazenzstruktur-Darstellung zu einem Feld von Datensätzen gemacht wird. Mit jeder Kante verknüpfte zusätzliche Informationen können in den Knoten der Adjazenzlisten gespeichert werden (oder in einem Feld a von Datensätzen in der Adjazenzmatrix-Darstellung), oder in Hilfsfeldern mit der Nummer der Kante als Index (was eine Numerierung der Kanten erfordert).


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