Zunächst einmal aber: Was bedeutet eigentlich Breitensuche ?
Strategie bei der Breitensuche |
Wähle als nächsten zu expandierenden Knoten einen beliebigen unter denen mit minimaler Pfadlänge (Tiefe) aus. |
Und man könnte hier hinzufügen: ... und stelle das Expandieren der dem jetzigen Pfad nachfolgenden solange zurück, bis alle Knoten der zuletzt expandierten Ebene sich als nicht erfolgreich erwiesen haben. |
Unser Beispiellabyrinth soll wieder die folgende Form haben:
1 | -- | 2 | -- | 3 |
I | I | |||
4 | -- | 5 | 6 | |
I | I | I | ||
7 | 8 | 9 |
Wir gehen dabei wieder zunächst einmal von einem einfachen gerichteten Graphen aus, also einem Baum. Als Startknoten wählen wir wieder den Wurzel - Knoten 1 und als Zielknoten den Knoten 8.
Verfolgen Sie einmal -unabhängig von einer Lösung im Programm- die Schritte der Expansion des Graphen auf der Grundlage der o.a. Forderung !
[Zur Datenstruktur siehe bei der Tiefensuche.]