Algorithmensammlung: Graphentheorie: Breitensuche

Algorithmensammlung: Graphentheorie

• Algorithmus von Kruskal
• Algorithmus von Prim
• Breitensuche (BFS - breadth first search)
• Dijkstra-Algorithmus
• Tiefensuche (DFS - depth first search)

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.

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