2 Implementation von Graphen

1.

Adjazenzmatrix:

Es ist auch möglich, eventuelle Kantenkosten dabei zu berücksichtigen:

Diese Implementation ist hauptsächlich geeignet für:

• Random Access auf Kanten (in konstanter Zeit möglich !)
• dichtbesetzte Graphen

2.

Adjazenzlisten:

Geeignet für:

• Algorithmen, die die Nachbarn eines Knotens abarbeiten.
• dünnbesetzte Graphen

Auf diesen Listen sind folgende Operationen möglich:

$$\bullet$$ (gibt momentanes Element aus

$$\bullet$$ (rücke einen vor)

$$\bullet$$ (rücke auf Listenanfang zurück)

$$\bullet$$ (füge Element ein)

$$\bullet$$ (lösche momentanes Element)

$$\bullet$$ (lege neue Liste an)

$$\bullet$$ (gibt an, ob Liste leer ist)

$$\bullet$$ (gibt an, ob Element am Listenende steht)

Der nachfolgende Algorithmus führt auf Basis dieser Adjazenzliste eine Tiefensuche durch:

     VAR g: Graph, id: INTEGER, val: ARRAY [0..N-1] OF INTEGER,
          besucht: ARRAY [0..N-1] OF BOOLEAN;
     (* val[i] = j $\Leftrightarrow$ Knoten i bekommt Nr. j *)
     FOR i := 0 TO N-1 DO besucht[i]:= FALSE END;
     FOR i := 0 TO N-1 DO
          IF NOT besucht[i] THEN visit(i) END;
     END;

     PROCEDURE visit(k: INTEGER)
     BEGIN
          id := id + 1;
          val[k] := id;
          besucht[k] := TRUE;
          reset (g[k]);
          WHILE NOT endpos (g[k]) DO
               y := elem (g[k]);
               IF NOT besucht[y] THEN visit(y) END;
               advance (g[k]);
          END
     END

Beispiel:

Die zugehörige Adjazenzliste sieht dann wie folgt aus:

$$\begin{array} {ll} A: & F, C, B, G\ B: & A, C\ C: & A, B\ D: & F, E\ E: & G, F, D\ F: & A, E, D\ G: & E, A\end{array}$$

Der obige Algorithmus liefert dann den folgenden Tiefensuchebaum mit der an den Knoten notierten Besuchreihenfolge:

Zur Laufzeit des Algorithmus ist folgendes zu bemerken:

Jede Kante im Graphen G = (V,E) wird genau zweimal besucht. Der Algorithmus berechnet also die Tiefensuchreihenfolge in O(|V| + |E|) .

Liegt hingegen eine Adjazenzmatrix vor, so ersetze im Algorithmus reset (g[k]) und die WHILE-Schleife durch:

     FOR y:=0 TO N-1 DO
          IF m[k,y] AND NOT besucht [y] THEN visit(y) END
     END

Man sieht leicht, daß der Aufwand des Algorithmus nun in O(|V|²) liegt, also im Mittel schlechter geworden ist.

Die Prozedur visit ist mit Hilfe eines Kellers auch iterativ zu formulieren, sie sieht dann wie folgt aus:

PROCEDURE visit(k: INTEGER);
BEGIN
     push(s,k);
     gesichtet[k] := TRUE;
     WHILE NOT emptystack(s) DO
          k := top(s);
          pop(s);
          id := id + 1;
          val[k] := id;
          reset(g[k]);
          WHILE NOT endpos(g[k]) DO
               y := elem(g[k]);
               IF NOT gesichtet[y] THEN push(s,y);
                    gesichtet[y] := TRUE;
               END;
               advance(g[k]);
          END;
     END;
END;

Im vorangegangenen Graphen ergibt sich dann folgender Tiefensuchebaum:

Der Keller speichert dabei im Laufe der Abarbeitung folgende Werte: