Algorithmensammlung: Graphentheorie: Algorithmus von Prim

Algorithmensammlung: Graphentheorie

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

Algorithmus von Prim

Der Algorithmus von Prim ist ein Algorithmus zum Auffinden minimaler Spannbäume in einem zusammenhängenden, ungerichteten, kantengewichtetem Graphen.

Für nähere Informationen siehe  Algorithmus von Prim.

Python

def prim(knoten, kanten):
    # knoten ist eine Liste von Knoten
    # kanten ist eine Liste von 3-Tupeln:
    #   (knoten1, knoten2, kosten)
    # Gibt ein Tupel ( knoten, kanten ) im selben
    # Format zurück
    
    tKnoten = [ knoten[0] ]
    tKanten = []

    while len(tKnoten) != len(knoten):
        akzeptableKanten = filter(lambda x: (x[0] in tKnoten) ^ (x[1] in tKnoten), kanten)
        sortierteKanten = sorted(akzeptableKanten, key=lambda x: x[2])
        tKanten += sortierteKanten[0]
        tKnoten += [ sortierteKanten[0][1 if sortierteKanten[0][0] in tKnoten else 0] ]
    
    return tKnoten, tKanten