Algorithmensammlung: Graphentheorie: Breitensuche
Zur Navigation springen
Zur Suche springen
Algorithmensammlung: Graphentheorie
- Algorithmus von Kruskal
- Algorithmus von Prim
- Breitensuche (BFS - breadth first search)
- Dijkstra-Algorithmus
- Tiefensuche (DFS - depth first search)
Breitensuche[Bearbeiten]
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.
Python[Bearbeiten]
# Getestet mit Python 3.5, sollte aber unter allen Python-3.x-Versionen laufen
import queue as q
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 = q.Queue()
queue.put(start)
besucht = []
while queue.qsize() > 0:
aktiverKnoten = queue.get()
besucht.append(aktiverKnoten)
for andererKnoten in adj[aktiverKnoten]:
if andererKnoten in besucht:
continue
if andererKnoten == suche:
# Knoten gefunden
return True
queue.put(andererKnoten)
return False