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

# 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