Deutsch
Menü

Was ist Breitensuche (Breadth-First Search)?

Verfahren zum Durchsuchen eines Graphen oder Baums, das die Knoten nach ihrer Entfernung vom Start besucht: zuerst die eine Kante entfernten, dann die zwei Kanten entfernten und so weiter. Es wird mit einer Warteschlange implementiert und findet in einem Graphen ohne Kantengewichte die kleinste Zahl von Kanten vom Start zu jedem Knoten. Abgekürzt BFS.

Japanische Bezeichnung: 幅優先探索

„Breitensuche (Breadth-First Search)“ kommt in 4 Übungsfragen aus 1 Themen vor, z. B. Datenstrukturen und Algorithmen.

Fachgebiet: Datenstrukturen und Algorithmen

Jetzt üben: Fragen zu Breitensuche (Breadth-First Search)

In eine leere Warteschlange (Queue) werden die Elemente A, B und C in dieser Reihenfolge eingefügt. Dann wird ein Element entnommen, D eingefügt und ein Element entnommen, E eingefügt und ein Element entnommen. In welcher Reihenfolge werden die Elemente entnommen?

  1. AA, B, C
  2. BC, D, E
  3. CC, B, A
Antwort und Erläuterung anzeigen

Antwort: A. A, B, C

Eine Warteschlange ist eine FIFO-Struktur (First In, First Out): Die Elemente werden in der Reihenfolge entnommen, in der sie eingefügt wurden. Nach dem Einfügen von A, B und C liefert die erste Entnahme A. Auch wenn danach D und E hinten angefügt werden, kommen zuerst B und C von vorn heraus; die Entnahmereihenfolge ist also A, B, C, und D und E bleiben übrig. C, D, E wäre die Reihenfolge eines Stacks (LIFO), der jedes Mal das zuletzt eingefügte Element entnimmt. Warteschlangen werden für Druckaufträge, für Message Queues zur Datenübergabe zwischen Tasks und für die Breitensuche verwendet.

Wie lässt sich ein dünn besetzter Graph, also einer mit wenigen Kanten im Verhältnis zur Zahl der Knoten, etwa ein Straßennetz mit rund 1 Million Knoten und 3 Millionen Kanten, geeignet im Speicher ablegen?

  1. AAls Adjazenzmatrix: Sie prüft in O(1), ob zwei Knoten verbunden sind, und braucht zudem den wenigsten Speicher
  2. BAls Adjazenzlisten: Der Speicherbedarf ist proportional zur Zahl der Knoten plus der Zahl der Kanten, und sie eignen sich, um die von einem Knoten ausgehenden Kanten der Reihe nach zu verfolgen
  3. CAls Adjazenzmatrix: Ihr Speicherbedarf ist nur proportional zur Zahl der Kanten
Antwort und Erläuterung anzeigen

Antwort: B. Als Adjazenzlisten: Der Speicherbedarf ist proportional zur Zahl der Knoten plus der Zahl der Kanten, und sie eignen sich, um die von einem Knoten ausgehenden Kanten der Reihe nach zu verfolgen

Eine Adjazenzmatrix verwendet für V Knoten eine Tabelle mit V × V Einträgen; 1 Million Knoten brauchen also 10¹² Einträge, selbst bei 1 Bit pro Eintrag etwa 125 GB. Adjazenzlisten speichern nur die Nachbarn jedes Knotens, der Speicherbedarf ist also O(V + E), in diesem Beispiel nur einige Millionen Einträge. Eine Adjazenzmatrix hat den Vorteil, eine Kante in O(1) prüfen zu können, und eignet sich für dicht besetzte Graphen oder Graphen mit wenigen Knoten. Für Verfahren, die nacheinander die von jedem Knoten ausgehenden Kanten verfolgen, etwa die Breitensuche und den Dijkstra-Algorithmus, sind Adjazenzlisten effizienter.

„Breitensuche (Breadth-First Search)“ in den Erläuterungen

Fragen mit „Breitensuche (Breadth-First Search)“ (4)

  1. In eine leere Warteschlange (Queue) werden die Elemente A, B und C in dieser Reihenfolge eingefügt. Dann wird ein Element entnommen, D eingefügt und ein Element entnommen, E eingefügt und ein Element entnommen. In welcher Reihenfolge werden die Elemente entnommen?
  2. Wie lässt sich ein dünn besetzter Graph, also einer mit wenigen Kanten im Verhältnis zur Zahl der Knoten, etwa ein Straßennetz mit rund 1 Million Knoten und 3 Millionen Kanten, geeignet im Speicher ablegen?
  3. In einem Graphen mit ungewichteten Kanten soll die kleinste Zahl von Kanten vom Startknoten zu jedem anderen Knoten bestimmt werden. Welche Kombination aus Suchverfahren und Datenstruktur ist geeignet?
  4. In einem ungerichteten Graphen sind die Nachbarn der Knoten A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Eine rekursive Tiefensuche beginnt bei Knoten A. Die Nachbarn werden in der angegebenen Reihenfolge geprüft, und sobald ein unbesuchter Knoten gefunden wird, geht die Suche zu ihm weiter. In welcher Reihenfolge werden die Knoten besucht?

Verwandte Begriffe

Warteschlange (Queue) Tiefensuche (Depth-First Search) Dijkstra-Algorithmus Rekursion Stack (Stapelspeicher) Binäre Suche (Binary Search) Binärer Heap (Binary Heap) Binärer Suchbaum (Binary Search Tree) Dynamische Programmierung Greedy-Algorithmus

Zur Glossarübersicht