imported>Horst Gräbner: Änderungen von ~2025-40186-31 (Diskussion) auf die letzte Version von Invisigoth67 zurückgesetzt

2025-12-12T10:05:10Z

Änderungen von ~2025-40186-31 (Diskussion) auf die letzte Version von Invisigoth67 zurückgesetzt

Neue Seite

[[Datei:Breadth-First-Search-Algorithm.gif|mini|300px|[[Animation]] der Breitensuche in einem [[Baum (Datenstruktur)|Baum]]]]

'''Breitensuche''' ({{enS|breadth-first search}}, ''BFS'') ist ein Verfahren in der [[Informatik]] zum Durchsuchen bzw. Durchlaufen der [[Knoten (Graphentheorie)|Knoten]] eines [[Graph (Graphentheorie)|Graphen]]. Sie zählt zu den [[Suchalgorithmus#Heuristische (Informierte) Suchalgorithmen|uninformierten Suchalgorithmen]]. Im Gegensatz zur [[Tiefensuche]] werden zunächst alle Knoten beschritten, die vom Ausgangsknoten direkt erreichbar sind. Erst danach werden Folgeknoten beschritten (siehe Abbildung).

== Arbeitsweise ==
Die Breitensuche ist eine [[Suchalgorithmus#Heuristische (Informierte) Suchalgorithmen|uninformierte Suche]], welche durch Expansion der einzelnen ''Level'' der [[Graph (Graphentheorie)|Graphen]] ausgehend vom Startknoten den Graph ''in die Breite'' nach einem Element durchsucht.

Zuerst wird ein Startknoten <math>u</math> ausgewählt. Von diesem [[Knoten (Graphentheorie)|Knoten]] aus wird nun jede [[Kante (Graphentheorie)|Kante]] <math>(u,v)</math> betrachtet und getestet, ob der gegenüberliegende Knoten <math>v</math> schon entdeckt wurde bzw. das gesuchte Element ist. Ist dies noch nicht der Fall, so wird der entsprechende Knoten in einer [[Warteschlange (Datenstruktur)|Warteschlange]] gespeichert und im nächsten Schritt bearbeitet. Hierbei ist zu beachten, dass Breitensuche immer zuerst alle Knoten der gleichen Ebene bearbeitet, und nicht wie die [[Tiefensuche]] einem [[Pfad (Graphentheorie)|Pfad]] in die Tiefe folgt. Nachdem alle Kanten des Ausgangsknotens betrachtet wurden, wird der erste Knoten der Warteschlange entnommen und das Verfahren wiederholt.

{|
|[[Datei:DepthFirstSearch graph cities de.svg|links|mini|350x350px|Eine [[Graphentheoretisch|graphentheoretische]] Landkarte von [[Deutschland]], [[Österreich]] und der [[Schweiz]] mit den Verbindungen zwischen einigen Städten. Dieses Beispiel ist ein ungerichteter Graph mit 10 Knoten.]]
|[[Datei:BreadthFirstSearch tree cities de.svg|mini|350x350px|Der Baum, welcher entsteht, wenn man Breitensuche auf die Landkarte anwendet und in Hannover startet. Dieser Baum hat die Höhe 4. Daher hat die Breitensuche in diesem Fall 4 [[Iteration|Iterationsschritte]].]]
|}
Der Index des [[Iteration|Iterationsschritts]] in der [[while-Schleife]] (siehe unten) entspricht dabei dem [[Weg (Graphentheorie)|Knotenabstand]] des aktuell durchlaufenen [[Knoten (Graphentheorie)|Knotens]] vom Startknoten. Dieser Index müsste, um zum Beispiel auf der Konsole ausgegeben zu werden, in einer [[Variable (Programmierung)|Variablen]] gespeichert werden.

Im Beispiel mit den Städten (siehe oben) gibt es 4 Iterationsschritte:

* '''Iterationsschritt 0''': Hannover (Knotenabstand 0)
* '''Iterationsschritt 1''': Frankfurt, Hamburg, Berlin (Knotenabstand 1)
* '''Iterationsschritt 2''': Zürich, Stuttgart, Mannheim, Wien (Knotenabstand 2)
* '''Iterationsschritt 3''': München, Dresden (Knotenabstand 3)

Der [[Weg (Graphentheorie)|Knotenabstand]] bezieht sich immer auf den Startknoten. Im links dargestellten ungerichteten Graphen ist es Hannover. Bei [[Gerichteter Graph|gerichteten Graphen]] ist der [[Weg (Graphentheorie)|Knotenabstand]] zwischen zwei ''verschiedenen'' Knoten nicht ''unbedingt'' symmetrisch.

In einem [[Gerichteter Graph|gerichteten Graphen]] könnte zum Beispiel der Knotenabstand von Hannover nach Mannheim ebenfalls 2 sein. Der Knotenabstand von Mannheim nach Hannover jedoch könnte gleich 1 sein, wenn es eine Kante (direkte Verbindung) von Mannheim nach Hannover gäbe. Er könnte auch gleich 2, gleich 3 oder größer sein.

Der Knotenabstand und die Anzahl der Iterationsschritte ist nur für [[Zusammenhängender Graph|zusammenhängende]] [[Graph (Graphentheorie)|Graphen]] definiert und hängt vom Startknoten ab. Für nicht zusammenhängende Graphen ist der Knotenabstand und die Anzahl der Iterationsschritte nur innerhalb jeder [[Zusammenhang (Graphentheorie)|Zusammenhangskomponente]] definiert.

'''Hinweis''': Der in der Abbildung links oben mit den Städten gezeigte [[Graph (Graphentheorie)|Graph]] ist ein ''ungerichteter'' Graph. Die Reihenfolge der durchlaufenen [[Knoten (Graphentheorie)|Knoten]] ''kann'' sich ändern, wenn stattdessen ein anderer Startknoten oder ein [[gerichteter Graph]] genommen wird, der ''nicht'' symmetrisch ist.

== Algorithmus ==
# Bestimme den [[Knoten (Graphentheorie)|Knoten]], an dem die Suche beginnen soll, markiere ihn als gesehen und speichere ihn in einer [[Warteschlange (Datenstruktur)|Warteschlange]] ab.
# Entnimm einen Knoten vom Beginn der Warteschlange.
#* Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere „gefunden“ zurück.
#* Anderenfalls hänge alle bisher unmarkierten Nachfolger dieses Knotens ans Ende der Warteschlange an und markiere sie als gesehen.
# Wenn die Warteschlange leer ist, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere „nicht gefunden“ zurück.
# Wiederhole Schritt 2.

Nachstehend formulierte [[Algorithmus|Algorithmen]] sind als [[Pseudocode]] zu verstehen und geben aus Gründen der Lesbarkeit nur an, ob der Zielknoten gefunden wurde. Weitere, in Anwendungsfällen wichtige Informationen – wie z. B. die aktuelle Pfadtiefe oder der bisherige Suchweg – könnten zusätzlich eingefügt werden.

[[Rekursion|Rekursiv]] formuliert:
BFS(''start_node'', ''goal_node'')
'''return''' BFS'({''start_node''}, ∅, ''goal_node'');

BFS'(''fringe'', ''gesehen'', ''goal_node'')
'''if'''(''fringe'' == ∅)
// Knoten nicht gefunden
'''return''' false;
'''if''' (''goal_node'' ∈ ''fringe'')
'''return''' true;
'''return''' BFS'({''child'' | ''x'' ∈ ''fringe'', ''child'' ∈ nachfolger(''x'')} \ ''gesehen'', ''gesehen'' ∪ ''fringe'', ''goal_node'');

Als [[Schleife (Programmierung)|Schleife]] formuliert:
BFS(''start_node'', ''goal_node'')
erzeuge eine leere Warteschlange ''queue''
''queue''.enqueue(''start_node'');
markiere ''start_node'' als ''gesehen''
'''while''' ''queue'' ist nicht leer
''node'' = ''queue''.dequeue();
'''if''' ''node'' == ''goal_node''
'''return''' true;
'''foreach''' ''child'' '''in''' nachfolger(''node'')
'''if''' ''child'' ist nicht markiert als ''gesehen''
''queue''.enqueue(''child'');
markiere ''child'' als ''gesehen''
'''return''' false;

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C-Sharp|C#]] zeigt die Implementierung der Breitensuche für einen [[Gerichteter Graph|gerichteten Graphen]]. Der gerichtete Graph wird als [[Klasse (Objektorientierung)|Klasse]] ''DirectedGraph'' deklariert. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''Main'' verwendet, die die Liste der markierten Knoten auf der Konsole ausgibt.<ref name=":0">GeeksforGeeks: [https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/ Breadth First Search or BFS for a Graph]</ref><syntaxhighlight lang="c#">
using System;
using System.Collections.Generic;

// Deklariert die Klasse für die Knoten des Graphen
class Node
{
public int index;
public string value;
public List<Node> adjacentNodes = new List<Node>(); // Liste der Nachbarknoten
}

// Deklariert die Klasse für den gerichteten Graphen
class DirectedGraph
{
// Diese Methode verbindet die Knoten startNode und targetNode miteinander.
public void ConnectNodes(Node startNode, Node targetNode)
{
startNode.adjacentNodes.Add(targetNode);
}
}

class Program
{
// Diese Methode gibt die Liste der Knoten in der Form A, B, C, ... als Text zurück.
public static string ToString(List<Node> traversedNodes)
{
string text = "";
for (int i = 0; i < traversedNodes.Count; i++) // for-Schleife, die die Knoten durchläuft
{
text += traversedNodes[i].value + ", ";
}
text = text.Substring(0, text.Length - 2);
return text;
}

// Diese Methode durchläuft die Knoten des gerichteten Graphen mit einer Breitensuche
public static List<Node> BreadthFirstSearch(Node startNode)
{
List<Node> traversedNodes = new List<Node>(); // Liste der Knoten für die Breitensuche
traversedNodes.Add(startNode); // Fügt den Startenknoten der Liste hinzu
HashSet<Node> visitedNodes = new HashSet<Node>(); // Menge der markierten Knoten
visitedNodes.Add(startNode); // Fügt den Startenknoten der Menge der markierten Knoten hinzu
Queue<Node> queue = new Queue<Node>(); // Warteschlange für die Breitensuche
queue.Enqueue(startNode); // Fügt den Startenknoten der Warteschlange hinzu
while (queue.Count > 0) // So lange die Warteschlange nicht leer ist
{
startNode = queue.Dequeue(); // Entfernt den ersten Knoten aus der Warteschlange
foreach (Node node in startNode.adjacentNodes) // foreach-Schleife, die alle benachbarten Knoten des Knotens durchläuft
{
if (!visitedNodes.Contains(node)) // Wenn der Knoten noch nicht markiert wurde
{
traversedNodes.Add(node); // Fügt den Knoten der Liste hinzu
visitedNodes.Add(node); // Markiert den Knoten
queue.Enqueue(node); // Fügt den Knoten der Warteschlange für die Breitensuche hinzu
}
}
}
return traversedNodes; // Gibt die Liste der Knoten zurück
}

// Hauptmethode, die das Programm ausführt
public static void Main(string[] args)
{
// Deklariert und initialisiert 4 Knoten
Node node1 = new Node{index = 0, value = "A"};
Node node2 = new Node{index = 1, value = "B"};
Node node3 = new Node{index = 2, value = "C"};
Node node4 = new Node{index = 3, value = "D"};

// Erzeugt einen gerichteten Graphen
DirectedGraph directedGraph = new DirectedGraph();

// Verbindet Knoten des Graphen miteinander
directedGraph.ConnectNodes(node1, node2);
directedGraph.ConnectNodes(node1, node3);
directedGraph.ConnectNodes(node2, node3);
directedGraph.ConnectNodes(node3, node1);
directedGraph.ConnectNodes(node3, node4);
directedGraph.ConnectNodes(node4, node4);

List<Node> traversedNodes = BreadthFirstSearch(node3); // Aufruf der Methode
Console.WriteLine(ToString(traversedNodes)); // Ausgabe auf der Konsole

Console.ReadLine();
}
}
</syntaxhighlight>'''Hinweise''': Für die Nachbarknoten wurde eine [[Liste (Datenstruktur)|Liste]] als [[Datentyp]] verwendet, damit die Reihenfolge der durchlaufenen [[Knoten (Graphentheorie)|Knoten]] eindeutig ist und die Knoten in allen Ebenen von links nach rechts durchlaufen werden. Für den Datentyp [[Menge (Datenstruktur)|Menge]] zum Beispiel muss das nicht der der Fall sein. Statt dem ''HashSet'' ([[Menge (Datenstruktur)|Menge]]) ''visitedNodes'' kann auch eine Liste oder ein Array vom Typ ''bool'' ([[Boolesche Variable]]) verwendet werden, wie im Einzelnachweis gezeigt.<ref name=":0" />

Der in der Abbildung links oben mit den Städten gezeigte [[Graph (Graphentheorie)|Graph]] ist ein ''ungerichteter'' Graph. Die Reihenfolge der durchlaufenen [[Knoten (Graphentheorie)|Knoten]] ''kann'' sich ändern, wenn stattdessen ein anderer Startknoten oder ein [[gerichteter Graph]] genommen wird, der ''nicht'' symmetrisch ist.

== Eigenschaften ==
Bezeichne <math> |V| </math> die Anzahl der [[Knoten (Graphentheorie)|Knoten]] und <math> |E| </math> die Anzahl der [[Kante (Graphentheorie)|Kanten]] im Graphen. [[Speicherplatz|Speicherplatzverbrauch]] und [[Laufzeit (Informatik)|Laufzeit]] des [[Algorithmus]] sind in [[Landau-Symbole|Landau-Notation]] angegeben.

=== Speicherplatzverbrauch ===
Da alle bisher entdeckten [[Knoten (Graphentheorie)|Knoten]] gespeichert werden, beträgt der [[Platzkomplexität|Speicherplatzverbrauch]] von Breitensuche <math>\mathcal{O}(|V|)</math>. Die Breitensuche ist für Verfahren, bei denen die Knoten erst während der Breitensuche generiert werden (z. B. das [[Branch-and-Bound|Branch-&-Bound-Verfahren]]), aufgrund des großen Platzverbrauches meist ungeeignet. Ein der Breitensuche ähnliches Verfahren, das jedoch meist mit deutlich weniger Speicher auskommt, ist die [[iterative Tiefensuche]].

=== Laufzeit ===
Da im ungünstigsten Fall alle möglichen [[Pfad (Graphentheorie)|Pfade]] zu allen möglichen [[Knoten (Graphentheorie)|Knoten]] betrachtet werden müssen, beträgt die [[Zeitkomplexität|Laufzeit]] der Breitensuche <math>\mathcal{O}(|V| + |E|)</math><ref>{{Literatur |Autor=Winfried Hochstättler |Titel=Algorithmische Mathematik |Verlag=Springer |Ort=Heidelberg, u. a. |Datum=2010 |ISBN=978-3-642-05421-1 |Seiten=56–58}}</ref>. Beachte, dass <math>\mathcal{O}(|E|)</math> zwischen <math>\mathcal{O}(1)</math> und <math>\mathcal{O}(|V|^2)</math> variieren kann, abhängig davon, wie dünn der [[Graph (Graphentheorie)|Graph]] ist.

Wenn die Anzahl der Knoten im Graphen im Voraus bekannt ist und zusätzliche [[Datenstruktur|Datenstrukturen]] verwendet werden, um zu bestimmen, welche Knoten bereits zur [[Warteschlange (Datenstruktur)|Warteschlange]] hinzugefügt wurden, kann die [[Platzkomplexität]] als <math>\mathcal{O}(|V|)</math> ausgedrückt werden. Dies gilt zusätzlich zu dem für das Graphen selbst erforderlichen Speicherplatz, der abhängig von der von einer Implementierung des Algorithmus verwendeten Graphendarstellung variieren kann.

=== Vollständigkeit ===
Wenn in jedem [[Knoten (Graphentheorie)|Knoten]] nur endlich viele Alternativen existieren, ist die Breitensuche vollständig. Dies bedeutet, dass, wenn eine Lösung existiert, diese auch gefunden wird. Dies ist unabhängig davon, ob der zugrunde liegende [[Graph (Graphentheorie)|Graph]] endlich ist oder nicht. Sollte jedoch keine Lösung existieren, so [[Divergieren|divergiert]] die Breitensuche bei einem unendlichen Graphen.

Bei der Analyse von [[Algorithmus|Algorithmen]] wird angenommen, dass die Eingabe für die Breitensuche ein [[endlicher Graph]] ist, der explizit als [[Adjazenzliste]] oder ähnlich dargestellt wird. Bei der Anwendung von [[Graph (Graphentheorie)|Graph]]-[[Traversierung|Traversierungen]] in der [[Künstliche Intelligenz|künstlichen Intelligenz]] kann die Eingabe jedoch eine implizite Darstellung eines unendlichen Graphen sein. In diesem Zusammenhang wird ein [[Suchverfahren]] als vollständig beschrieben, wenn garantiert wird, dass ein Zielzustand gefunden wird, falls einer existiert. Die Breitensuche ist abgeschlossen, die [[Tiefensuche]] jedoch nicht. Bei Anwendung auf unendlich viele Graphen, die implizit dargestellt werden, findet die Breitensuche schließlich den Zielzustand, aber die Tiefensuche kann in Teilen des Graphen verloren gehen, die keinen Zielzustand haben und niemals zurückkehren.<ref>Coppin, B. (2004). Artificial intelligence illuminated. Jones & Bartlett Learning. pp. 79–80.</ref>

=== Optimalität ===
Jede durch Breitensuche gefundene Lösung hat den kürzesten Abstand zum Wurzelknoten. Führt man [[Kantengewicht]]e ein, so muss das Ergebnis, welches am nächsten zum Startknoten liegt, nicht notwendigerweise auch das Ergebnis mit den geringsten Pfadkosten sein. Dieses Problem umgeht man, indem man die Breitensuche zur uniformen Kostensuche erweitert. Sind jedoch alle Kantengewichte äquivalent, so ist jede durch Breitensuche gefundene Lösung optimal, da in diesem Fall die Lösung, die am nächsten zum Ausgangsknoten liegt, auch die Lösung mit den geringsten Kosten ist. Ob existierende Lösungen überhaupt gefunden werden hängt mit Endlichkeitseigenschaften des [[Suchbaum|Suchbaums]] zusammen (siehe Vollständigkeit).

Die ''uniforme Kostensuche'' ({{enS|uniform-cost search}}) ist eine Erweiterung der Breitensuche für Graphen mit gewichteten Kanten. Der [[Algorithmus]] besucht Knoten in Reihenfolge aufsteigender Pfadkosten vom Wurzelknoten und wird deshalb üblicherweise mit einer [[Vorrangwarteschlange]] implementiert, in der alle noch nicht besuchten Nachbarn bereits besuchter Knoten mit der Pfadlänge als Schlüssel verwaltet werden. Die Optimalität ist nur für nicht-negative Kantengewichte garantiert.

== Anwendung ==
Die Breitensuche kann für viele Fragestellungen in der [[Graphentheorie]] verwendet werden. Einige sind:

* Finde alle Knoten innerhalb einer Zusammenhangskomponente
* Prüfe, ob der gegebene Graph [[Bipartiter Graph|paar]] ist und finde ggf. eine zulässige [[Färbung (Graphentheorie)|2-Färbung]] seiner Knoten<ref>Dieter Jungnickel: ''Graphen, Netzwerke und Algorithmen.'' BI Wissenschaftsverlag, 3. Auflage 1994, ISBN 3-411-14263-4, S. 95–100</ref>
* Finde zwischen zwei Knoten u und w einen [[Kürzester Pfad|kürzesten Pfad]] (ungewichtete Kanten)
* Kürzeste-Kreise-Problem

== Siehe auch ==
* [[Beschränkte Tiefensuche]]
* [[parallele Breitensuche]]

== Literatur ==
* Thomas H. Cormen, Charles Leiserson, [[Ronald L. Rivest]], Clifford Stein: ''Introduction to Algorithms.'' MIT Press, 2nd edition 2001, ISBN 0-262-53196-8
* Sven Oliver Krumke, Hartmut Noltemeier: ''Graphentheoretische Konzepte und Algorithmen''. 3. Auflage. Springer Vieweg, 2012, ISBN 978-3-8348-1849-2

== Weblinks ==
{{Commonscat|Breadth-first search|Breitensuche}}
{{Wikibooks|Algorithmensammlung: Graphentheorie: Breitensuche|Breitensuche|suffix=Implementierungen in der Algorithmensammlung}}

{{Gesprochene Version
|datei=De-Breitensuche-article.ogg
|länge=06:03 min
|größe=8,6 MB
|exzellent=nein
}}

== Einzelnachweise ==
<references />

[[Kategorie:Graphsuchalgorithmus]]

Breitensuche - Versionsgeschichte

imported>Horst Gräbner: Änderungen von ~2025-40186-31 (Diskussion) auf die letzte Version von Invisigoth67 zurückgesetzt