Graphen (Durchlaufen 2 )

 

Wir betrachten die Aufgabe

Finde alle Knoten, welche mit einem gegebenen Knoten v verbindbar sind.

Sie ist die Basisaufgabe der algorithmischen Graphentheorie. Die Zusammenhangsaufgabe wird dabei mit gelöst.

unser Ansatz 

Wir gehen von v aus auf 'Besuchtour': von einem Knoten über eine Kante zum nächsten.

wichtig 

Um uns nicht im Kreis zu drehen, brauchen wir eine Systematik.

 

Wir unterteilen die Knoten v in die Kategorien

• besucht und erledigt: alle von v ausgehenden Kanten wurden bereits begangen
• besucht und unerledigt: von v aus könnte es noch nicht begangene Kanten geben
• nicht besucht

Hier sind diese Kategorien durch Farben dargestellt. v ist der Startknoten.

Welcher Farbe entspricht 'besucht und erledigt'? Und welcher 'besucht und unerledigt'?

 

Der folgende Algorithmus setzt die Idee um. Die besuchten Knoten werden markiert, die unerledigten Knoten werden zur Weiterbehandlung in einer Datenstruktur D 'gemerkt'.

Knoten suchen 

Algorithmus Durchlaufen

Eingabe: Graph G, Knoten v dieses Graphen
Ausgabe: Markierungen für alle Knoten w von G. Ein Knoten ist genau dann als 'besucht' markiert, wenn er mit v verbindbar ist.

markiere alle Knoten als nicht besucht
markiere v als besucht
füge v in eine (zunächst leere) Datenstruktur D ein
solange D nicht leer ist
     entnehme einen Knoten w aus D
     für alle Kanten {w,u}
          falls u als nicht besucht markiert ist
               markiere u als besucht
               füge u in D ein

 

In welcher Reihenfolge man die Knoten 'besucht' hängt davon ab, wie in die Datenstruktur D eingefügt und aus ihr entnommen wird.

Breitensuche
--
Tiefensuche 

• D ist Queue (=Schlange): am einen Ende einfügen, am andern entnehmen.
      
  Es resultiert Breitensuche ('breadth first').
  
• D ist Stack (Stapel): am selben Ende einfügen und entnehmen.
      
  Es resultiert die Tiefensuche ('depth first').

(Mehr zu Queue und Stack findest du im MathePrisma-Modul Lineare Datenstrukturen)

Knoten besuchen

Hier kannst du Breiten- oder Tiefensuche

• als Film ansehen

und/oder

• interaktiv durch Auswahl der richtigen Knoten selbst durchführen.

Im Modus 'ändern' kannst du die Graphen auch ändern.

(Graph 6 ist der USA-Graph, eingeschränkt auf den Wilden Westen.)

alles klar?

Die Bilder stellen jeweils einen Zustand bei Breiten- oder Tiefensuche dar.
Ordne sie richtig ein.

Beweis? 

Bis jetzt haben wir eher anschaulich motiviert, weshalb der Algorithmus 'Durchlaufen' wirklich alle erreichbaren Knoten findet.
Eine auf der mathematischen Logik aufbauende strenge Beweisführung sieht anders aus. Einen diesem Anspruch genügenden Korrektheitsbeweis findest du auf dieser

 Nebenseite.

Seite 6/12