Besucht
In der Warteschlange
Geprüfte Kanten

  • Aktuell
  • In der Warteschlange
  • Besucht
  • Weg
Ein Klick auf einen Knoten setzt

Mehr über die Breitensuche

Breitensuche (BFS)

Die Breitensuche erkundet einen Graphen in Ringen: zuerst jeden Knoten neben dem Start, dann jeden Knoten, der zwei Kanten entfernt ist, und so weiter. Dazu nutzt sie eine Warteschlange: Was zuerst hineinkommt, kommt zuerst heraus. Klicken Sie auf einen Knoten, um dort zu starten, wählen Sie bei Bedarf ein Ziel und gehen Sie die Suche Schritt für Schritt durch: Die Warteschlange wächst und schrumpft, jeder Knoten erhält seinen Abstand, und ein kürzester Weg erscheint. Drücken Sie Abspielen, um der Suche zuzusehen, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Klicken Sie auf einen Knoten, um ihn zum Start zu machen; stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten, um einen kürzesten Weg dorthin zu suchen. Die Zahl auf jedem Knoten ist sein Abstand vom Start, und die Reihe unter dem Graphen ist die Warteschlange. Neuer Graph erzeugt einen anderen Graphen; wählen Sie, wie viele Knoten und Kanten er hat. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.

Wie es funktioniert

  1. Klicken Sie auf einen Knoten, um ihn zum Start zu machen. Um einen Weg zu suchen, stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten.
  2. Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück schrittweise vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Suche zu springen.
  3. Beobachten Sie die Warteschlange unter dem Graphen und den Abstand auf jedem Knoten. Neuer Graph erzeugt einen anderen Graphen zum Ausprobieren.

So funktioniert die Breitensuche

Legen Sie den Startknoten mit Abstand 0 in eine Warteschlange. Dann wiederholen Sie: Nehmen Sie den Knoten vorne aus der Warteschlange und betrachten Sie jeden seiner Nachbarn. Ein Nachbar, der noch nicht gesehen wurde, erhält einen um eins höheren Abstand als der genommene Knoten, merkt sich diesen Knoten als den, über den er erreicht wurde, und kommt hinten in die Warteschlange. Schon gesehene Nachbarn werden übersprungen. Ist die Warteschlange leer, hat jeder erreichbare Knoten seinen Abstand.

Warum sie kürzeste Wege findet

Die Warteschlange gibt die Knoten in der Reihenfolge heraus, in der sie gefunden wurden, und die Knoten werden Ring für Ring gefunden: Alle Knoten mit Abstand 1 kommen in die Warteschlange, bevor einer mit Abstand 2 hinzukommt, und so weiter. Wird ein Knoten zum ersten Mal erreicht, dann also über einen Weg mit möglichst wenigen Kanten. Folgt man den gemerkten Knoten vom Ziel zurück zum Start, erhält man diesen Weg. Dabei zählen nur die Kanten; haben Kanten unterschiedliche Längen, braucht man den Dijkstra-Algorithmus.

Häufig gestellte Fragen

Was ist Breitensuche?

Ein Verfahren, um einen Graphen von einem Startknoten aus zu erkunden: zuerst alle seine Nachbarn, dann deren Nachbarn und so weiter, Ring für Ring. Eine Warteschlange hält die Knoten in der Reihenfolge, in der sie gefunden wurden.

Findet die Breitensuche den kürzesten Weg?

Ja, wenn jede Kante gleich zählt: Wenn BFS einen Knoten zum ersten Mal erreicht, hat sie möglichst wenige Kanten benutzt. Bei Kanten mit unterschiedlichen Längen nehmen Sie stattdessen den Dijkstra-Algorithmus.

Was ist der Unterschied zwischen BFS und DFS?

Die Breitensuche nutzt eine Warteschlange und breitet sich gleichmäßig aus, Ring für Ring. Die Tiefensuche nutzt einen Stapel (oder Rekursion) und folgt einem Weg so tief wie möglich, bevor sie zurückgeht. BFS findet kürzeste Wege in Kanten, DFS nicht, aber sie eignet sich gut, um Zyklen zu finden und topologisch zu sortieren.

Wie schnell ist die Breitensuche?

Sie nimmt jeden Knoten einmal aus der Warteschlange und betrachtet jede Kante von beiden Enden aus, also wächst der Aufwand mit der Zahl der Knoten plus der Zahl der Kanten.

Wird mein Graph irgendwohin gesendet?

Nein. Der Graph wird in Ihrem Browser erzeugt und durchsucht, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor