Algo mit Namen "tree cutting" gesucht.
-
Hallo Forum,
ich suche einen Algorithmus mit Namen "tree cutting". Er soll angeblich einen gewichteten Graphen minimieren. Habt Ihr eine Beschreibung?
Ich habe bereits diesen Algo gefunden:
http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal
Sieht recht einfach aus. Mit einem guten Sortierer vermutlich schon verdammt schnell.Was gibt es sonst noch für Algos die sich mit dem Problem befassen?
-
Minimal Spanning Tree - Dijkstra
-
Den Algo kenne ich. Mein Problem liegt so: Versuche n Knoten so zu verbinden das das akkumulierte Gewicht der einzelnen Kanten minimal ist.
Der Algo soll später auch erweitert werden: Manchmal ist es effizienter den Graphen in Teilgraphen zerfallen zu lassen. Wenn zb das Gewicht einer Kante einen bestimmten Betrag übersteigt und beide Teilgraphen eine gewisse Größe haben.