Algorithmensammlung: Graphentheorie: Algorithmus von Prim

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 xor 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