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