Moore und Breitensuche in ungewichteten Graphen

Moore/BFS steht für eine systematische Ebenensuche in Graphen. Ausgehend von einem Startknoten werden zuerst direkte Nachbarn betrachtet, danach Knoten in der nächsten Entfernungsebene.

Damit wird ein Graph algorithmisch handhabbar. Er ist nicht nur ein Modell, sondern eine Struktur, auf der ein Verfahren arbeiten kann. Erreichbarkeit und kürzeste Wege in ungewichteten Graphen werden berechenbar.

Für Q1.5 ist das der operative Einstieg in Graphalgorithmen.

BFS steht im Kontext von Weg- und Suchproblemen. Aus lokalen Nachbarschaften soll eine globale Aussage entstehen: Welche Knoten sind erreichbar? In welcher Entfernung liegen sie? Über welchen Vorgänger wurde ein Knoten entdeckt?

Diese Fragen passen direkt zur Q1.5-Seite. Netzwerke bestehen aus Beziehungen. Um sie algorithmisch zu nutzen, muss man Nachbarschaften systematisch abarbeiten.

BFS übersetzt diese Idee in ein klares Verfahren mit Startknoten, Queue und visited-Markierung.

Die technische Struktur von BFS besteht aus wenigen Kernelementen. Eine Queue speichert die als Nächstes zu bearbeitenden Knoten. Eine visited-Markierung verhindert Wiederholungen. Eine Distanz- oder Ebeneninformation speichert die Entfernung vom Start. Eine Vorgängerstruktur erlaubt die Rekonstruktion eines Pfades.

Diese Bausteine verbinden mehrere D-Book-Schichten. Queue stammt aus Q1.4, Algorithmusdarstellung aus Q1.2, Graphmodellierung aus Q1.5. Zusammen entsteht ein klarer Graphalgorithmus.

BFS ist daher ein Integrationspunkt der Programmierkette.

Im Unterricht materialisiert sich BFS gut über eine Adjazenzliste. Der Startknoten wird markiert und in die Queue gelegt. Dann wird wiederholt ein Knoten entnommen, seine Nachbarn werden betrachtet, neue Knoten werden markiert und hinten in die Queue eingefügt.

Eine Spurentabelle macht sichtbar, wie sich Queue, visited-Menge und Vorgänger verändern. Dadurch wird die Ebenenlogik nachvollziehbar.

Die Implementierung kann später in Java erfolgen, aber die Verfahrensspur ist der didaktische Kern.

Die Bedeutung von BFS liegt darin, dass die erste Entdeckung eines Knotens in einem ungewichteten Graphen einen kürzesten Weg nach Kantenzahl liefert. Das folgt aus der Ebenenstruktur: Alle Knoten mit Abstand k werden vor Knoten mit Abstand k+1 bearbeitet.

Für Q1.5 ist das stark, weil es eine klare Brücke von Modell zu Aussage liefert. Ein Graph wird gespeichert, durchlaufen und liefert eine begründete Antwort.

BFS zeigt damit, was Graphalgorithmik leistet: systematische Suche statt intuitives Nachzeichnen.

BFS gilt für ungewichtete Graphen beziehungsweise für gleiche Kantengewichte. Sobald Kanten unterschiedliche Kosten besitzen, reicht die Ebenenlogik nicht mehr aus. Dann wird ein Verfahren wie Dijkstra relevant.

BFS ist außerdem nicht DFS. DFS geht in die Tiefe und eignet sich für andere Strukturfragen. BFS arbeitet schichtweise und ist besonders stark für kürzeste Wege nach Kantenzahl.

Diese Abgrenzung ist für Q1.5 wesentlich, weil sie Verfahren über ihre Voraussetzungen unterscheidet.