Traversieren von Graphen

Im Prinzip ist das Traversieren von Graphen vergleichbar mit dem Traversieren von Bäumen. Es muß jedoch beim Graphen darauf geachtet werden, daß dieser Zyklen besitzen kann. Durch Diese Zyklen kann es passieren, daß man beim traversieren in eine Endlosschleife gerät. Die kürzeste Endlosschleife wäre hierbei über eine Kante, die auf den Knoten zurückzeigt auf dem man sich gerade befindet.

Um Endlosschleifen zu verhindern muß man sich beim traversieren die Knoten merken, die man schon besucht hat. Dies geschieht über eine Marke die im Knoten selbst gespeichert wird. Erreicht man also einen unmarkierten Knoten wird dieser markiert und man kann fortfahren. Ist der Knoten bereits markiert wird er nicht weiter untersucht.

Bei Graphen werden zwei Traversierungsarten unterschieden:

1. Tiefensuche (depth first)
2. Breitensuche (breath first)

1.Tiefensuche

Ein typischer Algorithmus könnte im Pseudocode folgendermaßen aussehen:
 

TraverDepth (k: Knoten)

begin
    if k unmarkiert
    then begin
           markiere k;
           besuche alle Nachbarn von k mit TraversDeep;
        end;

end;


2.Breitensuche

TraversBreath (k: knoten)

begin
    trage k in die Warteschlange ein;
    repeat
        k := hole den nächsten Knoten aus der Warteschlange
        if k unmarkiert
        thenbegin
               markiere k;
               reihe alle Nachbarknoten in die Warteschlange ein;
        end;
    until Warteschlange leer
end;

3.Delphi-Beispiele für Travers-Depth und Travers-Breath

procedure TGraph.TraversDeep(StartIndex: IndexType);

 procedure Depth_First_Visit(n: IndexType);
 var       Knoten           :PKnoten;
           i                :IndexType;
 begin
  Knoten := PointItem(n);
  if Knoten.Marke = 0 then
   begin
    inc(Knoten.Marke);
    if Knoten.KantenCount > 0 then
     for i := 0 to Knoten.KantenCount-1 do
      Depth_First_Visit(Knoten.Kanten[i].DestKnoten);
   end;
 end;

begin
 ZeroKnotenMarken;
 Depth_First_Visit(StartIndex);
end;



procedure TGraph.TraversWidth(StartIndex: IndexType);
type      PQueueItem = ^TQueueItem;
          TQueueItem = record
                         Successor: PQueueItem;
                         KnotenIndex: IndexType;
                       end;
var       QueueStart, QueueEnd    :PQueueItem;

 procedure EnQueue(KnotenIndex: IndexType);
 var       NewKnoten          :PQueueItem;
 begin
  New(NewKnoten);
  NewKnoten.KnotenIndex := KnotenIndex;
  if assigned(QueueEnd) then
   QueueEnd.Successor := NewKnoten;
  NewKnoten.Successor := nil;
  QueueEnd := NewKnoten;
  if not assigned(QueueStart) then
   QueueStart := NewKnoten;
 end;

 function DeQueue: IndexType;
 var      TmpKnoten         :PQueueItem;
 begin
  Result := QueueStart.KnotenIndex;
  TmpKnoten := QueueStart.Successor;
  Dispose(QueueStart);
  QueueStart := TmpKnoten;
  if not assigned(TmpKnoten) then
   QueueEnd := nil;
 end;

var       Knoten           :PKnoten;
          i, Index         :IndexType;
begin
 QueueStart := nil;
 QueueEnd := nil;
 ZeroKnotenMarken;
 EnQueue(StartIndex);

 while assigned(QueueEnd) do // not istLeer
  begin
   Index := DeQueue;
   Knoten := PointItem(Index);
   if Knoten.Marke = 0 then
    begin
     inc(Knoten.Marke);
     if Knoten.KantenCount > 0 then
      for i := 0 to Knoten.KantenCount-1 do
       EnQueue(Knoten.Kanten[i].DestKnoten);
    end;
  end;
end;

 zurück zur Startseite