Breitensuche vs. Tiefensuche

Breitensuche

Zum Algorithmus (informell):

1. Speichere den Startknoten in einer leeren Warteschlange (auch Queue gennant) ab und führe Schritt 2 aus.
2. Falls die Warteschlange leer ist, wurden alle vom Startknoten erreichbaren Knoten untersucht und der gesuchte Knoten nicht gefunden. Brich die Suche ab und gib “NICHT GEEFUNDEN” aus. Anderenfalls gehe zu Schritt 3.
3. Entnimm einen Knoten und markiere diesen. Falls der entnommene Knoten der Gesuchte ist, brich die Suche ab und gib “GEFUNDEN” aus. Anderenfalls hänge alle unmarkierten Nachfolger dieses Knotens ans Ende der Warteschlange und gehe zu Schritt 2.

Tiefensuche

Zum Algorithmus (informell):

1. Wähle einen Startknoten an dem die Suche beginnen soll und gehe zu Schritt 2.
2. Falls der aktuelle Knoten der gesuchte Knoten ist, brich die Suche ab und gib “GEFUNDEN” aus. Anderenfalls gehe zu Schritt 3.
3. Markiere den aktuellen Knoten und speichere alle unmarkierten Nachfolger in einen Stack. Rufe anschließend für alle Knoten aus dem Stack rekursiv den Algorithmus auf (ab Schritt 2). Falls der Stack leer ist, tue nichts.

Applet

Im nachfolgenden Applet kann man sich ein Bild von der Arbeitsweise der Breiten.- bzw. Tiefensuche machen.

Zur Bedienung des Applets:

• Taster Breitensuche/Tiefensuche wechselt zwischen den beiden Algorithmen.
• Im Modus definiere Start-/Stopknoten kann man durch Anclicken eines Knotens abwechselnd den Start- bzw. Stopknoten (Knoten nach dem gesucht wird) abändern.

GraphBFSvsDFS.cdy (Dieses Applet kann in Cinderella ausgeführt werden.)