Zur Modellierung unseres Problems haben wir Graphen gewählt. Wir können aber meistens in einem Graphen nicht alle Wege auszählen, um den kürzesten zu finden. Die Rechenzeit würde astronomisch hoch sein. Ein effizienteres Verfahren kürzeste Wege zu finden erhalten wir, wenn wir kurzgefasst gleichzeitig alle Nachbarn abarbeiten, markieren, besuchte Knoten in eine Warteschlange schreiben und einen Zähler benutzen. Dieses Verfahren in eine Handlungsvorschrift, einen Algorithmus, umgesetzt, ergibt die Breitensuche oder Breadth-First-Search (BFS).
Probiere den Algorithmus auf verschiedenen Graphen aus. Was geschieht zum Beispiel, wenn Du einen unzusammenhängenden Graphen zu Grunde legst?
Wenn Du zuerst ein automatisch ablaufendes Beispiel sehen willst, klicke hier.
| Knoten bewegen | ||||
| Knoten hinzufügen | ||||
| ungerichtete Kante hinzufügen | ||||
| gerichtete Kante hinzufügen | ||||
| Elemente löschen | ||||
| Startknoten wählen | ||||
| Nächster Schritt im Algorithmusablauf | ||||
| Zurücksetzen |