Skip to content
Lexikon

Breitensuche

Breitensuche, auch bekannt als Breitensuchverfahren oder Breadth-First-Search (BFS), ist ein grundlegendes Algorithmusverfahren, das in der Graphentheorie und beim Durchsuchen von Baumstrukturen verwendet wird. Es gehört zu den wichtigsten Suchalgorithmen und zeichnet sich durch seine spezifische Eigenschaft und Effizienz aus.

Die Breitensuche kann verwendet werden, um alle Knoten oder Vertices in einem Graphen oder Baum zu durchsuchen, angefangen von einem bestimmten Startknoten. Im Gegensatz zur Tiefensuche (Depth-First-Search) werden dabei zuerst alle Nachbarn des Startknotens besucht, bevor die Nachbarn der Nachbarn besucht werden. Dieses Verfahren wird kontinuierlich angewendet, bis alle erreichbaren Knoten durchsucht wurden.

Der Algorithmus der Breitensuche verwendet eine Datenstruktur namens Queue oder Warteschlange, um die Reihenfolge der Knoten zu verwalten und zu speichern, die in den nächsten Iterationen durchsucht werden sollen. Dadurch werden Knoten schichtweise untersucht und ermöglichen die Auffindung kürzester Pfade oder die Bestimmung der Verbindungen zwischen Knoten in einem Graphen.

Ein Beispiel könnte die Nutzung der Breitensuche beim Finden des kürzesten Pfades in einem Labyrinth sein. Beginnend beim Eingang des Labyrinths wird die Breitensuche verwendet, um alle möglichen Wege schichtweise zu erkunden und letztendlich den kürzesten Weg zum Ausgang zu finden.

Die Breitensuche ist nicht nur in der Graphentheorie und bei Baumstrukturen relevant, sondern wird auch in anderen Anwendungen wie der Bildverarbeitung, der künstlichen Intelligenz und der Netzwerkanalyse eingesetzt.

Insgesamt ist die Breitensuche ein unverzichtbarer Algorithmus, der es ermöglicht, effizient den Überblick über große Datenmengen zu behalten und Verbindungen zwischen Elementen in einem Graphen oder einer Baumstruktur zu finden.

AlleAktien Newsletter

Jetzt abonnieren und nichts mehr verpassen.
Jede Woche Aktienanalysen, die besonders tiefgründig recherchiert sind. Komplett unabhängig, ehrlich, transparent.

B