Algorithmensammlung: Graphentheorie: Algorithmus von Kruskal

Algorithmensammlung: Graphentheorie

Algorithmus von Kruskal

Bearbeiten

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

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

# Getestet mit Python 3.3
def kruskal(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 = []
    zshgKomponenten = []
 
    sortierteKanten = sorted(kanten, key=lambda x: x[2])
    while len(tKnoten) != len(knoten) or len(zshgKomponenten) != 1:
        # Günstigste Kante nehmen
        kante = sortierteKanten.pop(0)
        # Die Kanten, die einen Kreis bilden würden,
        # entfernen. Dafür Zusammenhangskomponenten merken
        zshgKompA = list(filter(lambda x: kante[0] in x, zshgKomponenten))
        zshgKompB = list(filter(lambda x: kante[1] in x, zshgKomponenten))
        if zshgKompA and zshgKompB and zshgKompA == zshgKompB:
            continue
        elif zshgKompA and zshgKompB and zshgKompA != zshgKompB:
            zshgKomponenten.remove(zshgKompA[0])
            zshgKomponenten.remove(zshgKompB[0])
            zshgKomponenten.append(zshgKompA[0] + zshgKompB[0])
        elif zshgKompB:
            zshgKompB[0] += [ kante[0] ]
        elif zshgKompA:
            zshgKompA[0] += [ kante[1] ]
        else:
            zshgKomponenten += [ [ kante[0], kante[1] ] ]
        # Kante in Baum aufnehmen
        if kante[0] not in tKnoten: tKnoten += [ kante[0] ]
        if kante[1] not in tKnoten: tKnoten += [ kante[1] ]
        tKanten += [ kante ]
 
        # Zu Lernzwecken:
        # print(zshgKomponenten)
 
    return (tKnoten, tKanten)
 
if __name__ == "__main__":
    print(kruskal([1,2,3,4,5], [
        (1,2,1),
        (2,3,50),
        (3,4,2),
        (4,5,1)]))