Kruskal

Moderator: Effiziente Graphenalgorithmen

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Kruskal

Beitrag von zimpfer »

Ich hänge hier seit Stunden beim Kruskal...
Ich nutze Java und JUNG.
Ich habe jetzt die Kanten nach Gewicht sortiert und alle Knoten als einen DelegateForest von DelegateTrees initialisiert. (Für jeden Knoten ein Tree-Objekt)

Danach gehe ich die sortierten Kanten durch, aber ich weiß nicht genau, wie ich dann testen soll, ob die beiden Knoten dieser Kante in der selben Zusammenhangskomponente sind...

Das Prinzip ist mir klar:
Um es in log(n) zu machen, baue ich einen möglichst ausgeglichenen Baum auf.
Ich betrachte die aktuelle Kante, nehme beide Knoten u und v und teste ob beide Knoten die selbe Wurzel haben:
-Wenn sie die selbe Wurzel haben: Kante wird nicht zum MST hinzugefügt und ich schaue mir die nächste Kante an.
-Wenn sie unterschiedliche Wurzeln haben: Ich hänge den kleineren Baum an den größeren (addChild(..) oder ähnliches) und füge die Kante zum MST hinzu


Ich hänge nun aber fest beim Test, ob beide Knoten die selbe Wurzel haben. Im der DelegateTree-Klasse gibt es eine getRoot(), allerdings weiß ich nicht, wie ich rausfinden soll, zu welchen Trees die betrachteten Knoten gehören...

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Kruskal

Beitrag von MisterD123 »

ich hab einfach ne liste gemacht und füg die kanten in die liste ein wenn ich sie "blau markiere".


und ansonsten .. node1.getRoot() == node2.getRoot() oder alternativ node1.getRoot().equals(node2.getRoot()) (so in der richtung)?

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Re: Kruskal

Beitrag von zimpfer »

MisterD123 hat geschrieben:ich hab einfach ne liste gemacht und füg die kanten in die liste ein wenn ich sie "blau markiere".


und ansonsten .. node1.getRoot() == node2.getRoot() oder alternativ node1.getRoot().equals(node2.getRoot()) (so in der richtung)?

Das ist mir schon klar.
Das Problem bei mir ist, dass ich die sortierten Kanten durchgehe und ich dabei nicht weiß, wie ich die beiden Knoten dem jeweiligen Tree zuordne, in dem sie sind (außer jeden Tree einzeln zu testen)...
Ich initialisiere jeden Knoten als einzelnen Tree und füge diesen Tree zu einem Forest hinzu.
Wenn ich nun eine Kante testen will, hole ich mir beide Knoten (integers) und dann weiß ich nicht, wie ich herausfinden soll, zu welchem Tree der Knoten gehört (was ich wissen muss, um getRoot() ausführen zu können)

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Kruskal

Beitrag von yourmaninamsterdam »

Vorsicht bei der log(n)-Sache. Die Gesamtlaufzeit soll m log(n) nicht überschreiten. Folglich muss das gesamte Verschmelzen in log(n) ablaufen. Wie irgendwann inder Vorlesung erwähnt, besteht die Idee hier darin, die Anzahl der Verschmelzungen soweit zu beschränken, dass Knoten höchstens log(n) Mal die Komponente wechseln. Ob zwei Knoten in einer Komponente sind oder nicht, muss also mit deutlich weniger Aufwand ermittelt werden als log(n).

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Kruskal

Beitrag von MisterD123 »

zimpfer hat geschrieben:
MisterD123 hat geschrieben:ich hab einfach ne liste gemacht und füg die kanten in die liste ein wenn ich sie "blau markiere".


und ansonsten .. node1.getRoot() == node2.getRoot() oder alternativ node1.getRoot().equals(node2.getRoot()) (so in der richtung)?

Das ist mir schon klar.
Das Problem bei mir ist, dass ich die sortierten Kanten durchgehe und ich dabei nicht weiß, wie ich die beiden Knoten dem jeweiligen Tree zuordne, in dem sie sind (außer jeden Tree einzeln zu testen)...
Ich initialisiere jeden Knoten als einzelnen Tree und füge diesen Tree zu einem Forest hinzu.
Wenn ich nun eine Kante testen will, hole ich mir beide Knoten (integers) und dann weiß ich nicht, wie ich herausfinden soll, zu welchem Tree der Knoten gehört (was ich wissen muss, um getRoot() ausführen zu können)
HashMap<Vertex, Tree<Vertex, Edge>>? einfach sobald du nen baum erstellst und nem knoten zuordnest den knoten mit dem baum zusammen in ne hashmap schreiben.

oder dem knoten nen entsprechenden optionalen pointer verpassen, aber dann musst du ne klasse benutzen für die knoten, die noch dazu dann nur speziell für deinen algo gut ist.

Antworten

Zurück zu „Effiziente Graphenalgorithmen“