Algorithmensammlung: Graphentheorie: Algorithmus von Kruskal

Algorithmus von Kruskal
Algorithmus von Prim
Breitensuche (BFS - breadth first search)
Dijkstra-Algorithmus
Tiefensuche (DFS - depth first search)

Algorithmus von Kruskal

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

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