Graphen | MathePrisma

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'?

grau
grün
blau

Und welcher 'besucht und unerledigt'?

grau
grün
blau

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?

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.