Breitensuche - Ein BFS Graph Traversal Guide mit 3 Leetcode-Beispielen

Breadth First Search (BFS) ist einer der beliebtesten Algorithmen zum Suchen oder Durchlaufen einer Baum- oder Diagrammdatenstruktur. In diesem Tutorial lernen wir kurz, wie BFS funktioniert, und untersuchen ein grundlegendes Muster, mit dem einige mittlere und einfache Probleme in Leetcode gelöst werden können.

Fangen wir an, sollen wir?

Was ist die Breitensuche?

Wir alle wissen also, dass ein Graph eine Menge von Eckpunkten und Kanten ist: G = {V, E}. Das Durchlaufen eines Diagramms bedeutet, jeden Scheitelpunkt und jede Kante genau einmal in geordneter Weise zu besuchen .

In BFS müssen wir den Graphen in der Breite oder Ebene durchlaufen. Dies bedeutet, dass wir uns zuerst horizontal bewegen und alle Knoten der aktuellen Ebene besuchen, bevor wir zur nächsten Ebene übergehen.

Daher können wir die BFS-Technik verwenden , wenn wir aufgefordert werden, eine Level-Order-Durchquerung durchzuführen .

In BFS würden wir mit dem Durchlaufen von 1 (dem Stammknoten) beginnen und die untergeordneten Knoten 8, 5 und 2 besuchen. Wir würden sie in der Reihenfolge speichern, in der sie besucht wurden. Dies würde es uns ermöglichen, zuerst die untergeordneten Knoten von 8 (dh 6, 4 und 3), dann von 5 (dh null) und dann von 2 (dh 9) usw. zu besuchen.

Implementierung

Um BFS zu implementieren, wird eine Warteschlangendatenstruktur verwendet. Die Warteschlange speichert den Knoten und markiert ihn als "besucht", bis alle benachbarten Scheitelpunkte markiert sind.

Die Warteschlange folgt der FIFO-Methode (First In First Out). Dies bedeutet, dass die Nachbarn des Knotens in der Reihenfolge besucht werden, in der sie eingefügt wurden.

BFS Zauber:

  1. Fügen Sie der Warteschlange einen Knoten hinzu
  2. Knoten entfernen
  3. Rufen Sie nicht besuchte Nachbarn des entfernten Knotens ab und fügen Sie sie der Warteschlange hinzu
  4. Wiederholen Sie die Schritte 1, 2 und 3, solange die Warteschlange nicht leer ist.

Schauen wir uns nun einige Leetcode-Probleme an und wenden das Gelernte an.

102. Durchlaufen der Reihenfolge auf Binäre Baumebene (Schwierigkeitsgrad: Mittel)

Die Frage fordert uns auf, das Diagramm zu durchlaufen und die Knoten auf jeder Ebene in einer verknüpften Liste zu drucken. Um dieses Problem zu lösen, müssen wir nur unseren Zauberspruch anwenden!

Stellen Sie sicher, dass Sie den Code gut verstehen, da dies die grundlegende Vorlage ist, mit der wir mehrere Probleme lösen. Also lasst uns das durchgehen.

Im obigen Code haben wir zunächst den Wurzelknoten in die Warteschlange eingefügt. Während die Warteschlange nicht leer ist, haben wir diesen Knoten aus der Warteschlange entfernt und sein linkes und rechtes untergeordnetes Element in die Warteschlange eingefügt.

Aber vorher haben wir geprüft, ob jedes seiner Kinder null ist oder nicht. Wenn null, hätten wir eine Nullzeiger-Ausnahme erhalten.

Der Vorgang wird erneut mit den nächsten Elementen wiederholt, die in der Warteschlange verbleiben. Die for-Schleifewird gepflegt, um uns die Liste der Knoten auf jeder Ebene in separaten verknüpften Listen zu geben.

637. Durchschnitt der Ebenen in einem Binärbaum (Schwierigkeitsgrad: Einfach)

Diese Frage sagt uns, dass wir den Durchschnittswert der Knoten auf jeder Ebene eines Binärbaums in einem Array ermitteln sollen. Dies folgt dem gleichen Verfahren wie unser vorheriges Problem mit einer kleinen Optimierung.

Wie Sie sehen, haben wir lediglich den Vorlagencode kopiert und eingefügt. Dann setzen wir einfach eine Summenvariable in die for-Schleife, die uns die Summe der Knotenwerte auf jeder Ebene geben kann. Dies wird verwendet, um unseren gewünschten Durchschnitt zu berechnen.

429. N-ary Tree Level Order Traversal (Schwierigkeitsgrad: Mittel)

Ein Baum, in dem jeder Knoten nicht mehr als N Kinder hat, wird als N-Baum bezeichnet.

Dies folgt genau der gleichen Prozedur wie das Durchlaufen eines Binärbaums, außer dass hier alle untergeordneten Knoten eines Knotens in die Warteschlange eingefügt werden. Denken Sie daran, dass wir bei der Lösung von Problemen im Zusammenhang mit dem Binärbaum nur die linken und rechten untergeordneten Elemente eines bestimmten Knotens in die Warteschlange eingefügt haben.

Das ist alles! Ich hoffe, dies hat Ihnen geholfen, BFS besser zu verstehen und das Tutorial hat Ihnen gefallen. Bitte empfehlen Sie diesen Beitrag, wenn Sie der Meinung sind, dass er für jemand anderen nützlich sein könnte!