In der Graph-Theorie ist Breitensuche (BFS) eine Strategie, um in einem Graphen zu suchen, wenn Suche auf im Wesentlichen zwei Operationen beschränkt wird: (A) besuchen und untersuchen einen Knoten eines Graphen; (b) gewinnen Zugang, um die Knoten zu besuchen, die an den zurzeit besuchten Knoten grenzen. Der BFS beginnt an einem Wurzelknoten, und untersuchen Sie alle benachbarten Knoten. Dann für jeden jener Nachbarknoten der Reihe nach untersucht es ihre Nachbarknoten, die und so weiter verlassen waren. Vergleichen Sie es mit der Tiefensuche.

Wie es arbeitet

BFS ist eine uninformierte Suchmethode, die zum Ziel hat, alle Knoten eines Graphen oder Kombination von Folgen durch das systematische Durchsuchen jeder Lösung auszubreiten und zu untersuchen. Mit anderen Worten sucht es erschöpfend den kompletten Graphen oder die Folge, ohne die Absicht zu denken, bis es es findet.

Von der Einstellung des Algorithmus werden alle erhaltenen Kinderknoten durch die Erweiterung eines Knotens zu einem FIFO (d. h., Zuerst In, Zuerst) Warteschlange hinzugefügt. In typischen Durchführungen werden Knoten, die für ihre Nachbarn noch nicht untersucht worden sind, in einen Behälter gelegt (wie eine Warteschlange, oder hat Liste verbunden) genannt "offen", und dann einmal untersucht werden in den "geschlossenen" Behälter gelegt.

(Informeller) Algorithmus

1. Reihen Sie den Wurzelknoten ein
2. Entfernen Sie ein Knoten und untersuchen Sie ihn
3. *, Wenn das gesuchte Element in diesem Knoten gefunden wird, verlässt die Suche und geben ein Ergebnis zurück.
4. * reihen Sonst irgendwelche Nachfolger ein (die direkten Kinderknoten), die noch nicht entdeckt worden sind.
5. Wenn die Warteschlange leer ist, ist jeder Knoten auf dem Graphen untersucht worden - verlässt die Suche und Rückkehr "nicht gefunden".
6. Wenn die Warteschlange nicht leer ist, wiederholen Sie sich vom Schritt 2.

Referenzen: Das Verwenden eines Stapels statt einer Warteschlange würde diesen Algorithmus in eine Tiefensuche verwandeln.

Pseudocode

Eingang: Ein Graph G und eine Wurzel v G

1 Verfahren BFS (G, v):

2 schaffen eine Warteschlange Q

3 reihen v auf Q ein

4 Zeichen v

5, während Q nicht leer ist:

6 t  Q.dequeue

7, wenn t ist, wonach wir suchen:

8 Rückkehr t

9 für alle Ränder e in G.incidentEdges tun (t)

10 o  G.opposite (t, e)

11, wenn o nicht gekennzeichnet wird:

12 Zeichen o

13 reihen o auf Q ein

Eigenschaften

Raumkompliziertheit

Wenn die Zahl von Scheitelpunkten im Graphen vorzeitig bekannt ist, und zusätzliche Datenstrukturen verwendet werden, um zu bestimmen, welche Scheitelpunkte bereits zur Warteschlange hinzugefügt worden sind, kann die Raumkompliziertheit als ausgedrückt werden, wo der cardinality des Satzes von Scheitelpunkten ist.

Zeitkompliziertheit

Die Zeitkompliziertheit kann als seit jedem Scheitelpunkt ausgedrückt werden, und jeder Rand wird im Grenzfall erforscht. Bemerken Sie: Kann sich zwischen und abhängig von bekannten Schätzungen der Zahl von Graph-Rändern ändern.

Anwendungen

Breitensuche kann verwendet werden, um viele Probleme in der Graph-Theorie zum Beispiel zu beheben:

• Die Entdeckung aller Knoten innerhalb eines verbundenen Bestandteils
• Sammlung, der Algorithmus von Cheney kopierend
• Die Entdeckung des kürzesten Pfads zwischen zwei Knoten u und v
• Die Prüfung eines Graphen für die Zweiteiligkeit
• Cuthill-McKee (rück)-Ineinandergreifen, das numeriert
• Methode von Ford-Fulkerson, für den maximalen Fluss in einem Fluss-Netz zu schätzen
• Serialization/Deserialization eines binären Baums gegen die Anordnung in der sortierten Ordnung, erlaubt dem Baum, auf eine effiziente Weise wieder aufgebaut zu werden.

Entdeckung verbundener Bestandteile

Der Satz von Knoten, die durch einen BFS (Breitensuche) Form der verbundene Bestandteil erreicht sind, der den Startknoten enthält.

Prüfung der Zweiteiligkeit

BFS kann verwendet werden, um Zweiteiligkeit, durch das Starten der Suche an jedem Scheitelpunkt und das Geben von Wechseletiketten den während der Suche besuchten Scheitelpunkten zu prüfen. D. h. geben Sie Etikett 0 dem Startscheitelpunkt, 1 allen seinen Nachbarn, 0 den Nachbarn jener Nachbarn und so weiter. Wenn an einem Schritt ein Scheitelpunkt Nachbarn mit demselben Etikett wie selbst (besucht) hat, dann ist der Graph nicht zweiteilig. Wenn die Suchenden ohne solch ein Situationsauftreten, dann ist der Graph zweiteilig.

Siehe auch

• Tiefensuche

Links

• Breite die erste Erklärung und das Beispiel