Algorithmensammlung: Graphentheorie: Algorithmus von Kruskal

Algorithmensammlung: Graphentheorie

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