Algorithmensammlung: Graphentheorie: Breitensuche
Aus Wikibooks
Algorithmensammlung: Graphentheorie
-
- Algorithmus von Kruskal
- Algorithmus von Prim
- Breitensuche (BFS - breadth first search)
- Dijkstra-Algorithmus
- Tiefensuche (DFS - depth first search)
[Bearbeiten] Breitensuche
Die Breitensuche ist ein Suchverfahren zum Auffinden von Knoten in Graphen. Es durchsucht dabei dem Startknoten näher gelegene Knoten vor weiter entfernten. Folglich lässt es sich, wenn man den bei der Suche gegangenen Weg speichert, auch zum Auffinden kürzester Pfade verwenden.
Für nähere Informationen siehe auch 
Breitensuche.
[Bearbeiten] Python
def breitensuche(adj, start, suche): # adj ist die Adjazenzliste {knoten: [kanten]} # start ist der Index des Knoten, in dem die Suche beginnt # suche ist der gesuchte Knoten queue = [ start ] besucht = [] while len(queue) > 0: aktiverKnoten = queue.pop(0) besucht.append(aktiverKnoten) if adj[aktiverKnoten]: for andererKnoten in adj[aktiverKnoten]: if andererKnoten in besucht: continue if andererKnoten == suche: # Knoten gefunden return True queue.append(andererKnoten) return False
