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.]