Introduction

Willkommen zurück zur Serie Graph-Algorithmen! Nach der Tiefensuche wenden wir uns der Breitensuche (Breadth-First Search, BFS) zu, dem anderen grundlegenden Graph-Traversierungsverfahren.

Während die Tiefensuche (DFS) in die Tiefe geht, exploriert die Breitensuche (BFS) in Schichten: zuerst den Startknoten, dann alle seine Nachbarn, dann alles, was zwei Schritte entfernt ist, und so weiter. Diese schichtweise Reihenfolge ist genau das, was die BFS dazu befähigt, kürzeste Pfade in ungewichteten Graphen zu finden.

Wie im Rest der Serie wird ein Graph als n (Anzahl der Knoten, 0 bis n - 1) und edges, ein flaches Array aus ungerichteten Paaren [u0, v0, u1, v1, ...], angegeben.

Fangen wir an!