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.

Python Bearbeiten

# 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)]))