Algorithmensammlung: Graphentheorie: Algorithmus von Prim

Algorithmensammlung: Graphentheorie

Algorithmus von PrimBearbeiten

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.

PythonBearbeiten

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