Zum Inhalt springen

Algorithmensammlung: Graphentheorie: Algorithmus von Prim

Aus Wikibooks

Algorithmensammlung: Graphentheorie

Algorithmus von Prim

[Bearbeiten]

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

[Bearbeiten]
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