Kruskal: Guter Kreisfrei Algo gesucht.

Hallo Forum,

ich möchte den Kruskal Algo implementieren. Also einen minimal spannenden Baum aus einem Graphen erstellen. Dieser Algo soll eine Laufzeit von #Kanten*Log(#Knoten) haben.

Die Kanten sind von den Gewichten her sortiert. Ich gehe in einer For Schleife von der kleinsten Gewichtung los. Habt Ihr eine Idee wie nun in log(#Knoten) Zeit feststellen kann ob im Graph ein Kreis ist?

Wie es momentan aussieht: Jeder Knoten hat eine Eingenschaft intCluster. Zu anfangs ist dort die Knotennummer gespeichert. -> Jeder Knoten ist einzeln in einem extra Cluster. Wenn nun eine Kante hinzugefügt wird, wird überprüft ob die intCluster Zahl unterschiedlich ist. -> Wann ja, befinden sich die Knoten nicht im selben Cluster und durch die Kante entsteht kein Kreis. Als letztes wird der eine Cluster dem anderen hinzugefügt.
Hier liegt nun mein Problem: Wenn ich die Cluster vereinige muß ich eine Schleife machen die durch alle Knoten durchgeht und die intCluster Eingenschaft des einen Knoten durch den des anderen ersetzt. Damit wäre die Laufzeit aber #Kanten*#Knoten

Kennt Ihr einen besseren Kreisfrei Algo?

Philip

CStoll

http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal

Du könntest ja eine Hilfsstruktur aufbauen, in der du umgekehrt alle Knoten jedes Clusters aufsammelst.

Hast Recht.

Vielen Dank