Algorithmensammlung: Graphentheorie: Tiefensuche
Aus Wikibooks
Algorithmensammlung: Graphentheorie
-
- Algorithmus von Kruskal
- Algorithmus von Prim
- Breitensuche (BFS - breadth first search)
- Dijkstra-Algorithmus
- Tiefensuche (DFS - depth first search)
[Bearbeiten] Tiefensuche
Die Tiefensuche ist ein Suchverfahren zum Auffinden von Knoten in Graphen. Es geht dabei zunächst in die Tiefe, durchsucht also die verschiedenen adjazenten Knoten um den Startknoten zu mitunter sehr unterschiedlichen Zeitpunkten.
Für nähere Informationen siehe auch 
Tiefensuche.
[Bearbeiten] Python
def tiefensuche(adj, start, suche, besucht=[]): # adj ist die Adjazenzliste {knoten: [kanten]} # start ist der Knoten, um die Suche zu beginnen # suche ist der gesuchte Knoten if start == suche: return True if adj[start]: for knoten in filter(lambda x: x not in besucht, adj[start]): besucht.append(knoten) if tiefensuche(adj, knoten, suche, besucht): return True return False
