Aufwand Union-Find-Struktur

H

herzog

Mitglied
Hallo!
ist jetzt keine Hausaufgabe, sondern Klausurvorbereitung und zwar zum Thema Datenstrukturen und Algorithmen.

Java: 
public class UFS {
	protected UFSNode[] nodes;
	
	public UFS(int k){
		nodes = new UFSNode[k];
		for(int i = 0; i<k; i++){
			nodes[i] = new UFSNode(i);
		}
	}
	

	public int find(int index){
		return nodes[index].getRoot().nummer;
	}
	
	public void union(int indexa, int indexb){
		int a = find(indexa);
		int b = find(indexb);
		if(a != b){
			if(nodes[a].getKinder() >= nodes[b].getKinder()){
				nodes[b].setSucc(nodes[a]);
				nodes[a].setKinder(nodes[a].getKinder() + nodes[b].getKinder() + 1);
			}else{
				nodes[a].setSucc(nodes[b]);
				nodes[b].setKinder(nodes[a].getKinder() + nodes[b].getKinder() + 1);
			}
		}
	}
	
	public String toString(){
		String result = "";
		for(int i = 0; i < nodes.length; i++){
			result += i + ": Wurzel " + find(i) + ", direkter Vorgänger: " + nodes[i].succ.nummer + ", Kinder " + nodes[i].getKinder() + "\n";
		}
		return result;
	}
}

Java: 
public class UFSNode {
	protected UFSNode succ;
	protected int nummer;
	protected int kinder;
	
	public UFSNode(int i){
		nummer = i;
		kinder = 0;
		succ = this;
	}
	
	public void setSucc(UFSNode n){
		this.succ = n;
	}
	
	public void setKinder(int i){
		kinder = i;
	}
	
	public int getKinder(){
		return kinder;
	}
	
	public UFSNode getRoot(){
		if(this.succ == this){
			return this;
		}else if(this.succ == this.succ.succ){
			return this.succ;
		}else{
			UFSNode n = this.succ.getRoot();
			this.succ.setKinder(this.succ.getKinder() - 1);
			this.succ = n;
			n.setKinder(n.getKinder() + 1);
			return n;
		}
	}
}

Ich habe versucht eine Wegkompression mit einzubauen, indem ich bei find die Knoten direkt unter die Wurzel hänge und durch das Mitzählen der Kinder habe ich versucht Union-By-Size zu implementieren. Das ganze ist für Kruskal gedacht, darum weiß ich vorher wieviele Knoten es werden und kann diese einfach von 0 bis n-1 in das Array packen.
Ergibt aus meiner Sicht bisher zumindest sehr viel Sinn das ganze ;)

Jetzt geht es um den Aufwand für union und find. ich würde sagen, dass der Aufwand für union = Aufwand für find ist, da ich am Anfang von Union die find-methode zwei mal Aufrufen muss um an die Wurzeln zu kommen. Der Rest läuft dann mit konstantem Aufwand.
Den Aufwand für find würde ich jetzt als O(1) beschreiben, weil bei Union und find durch die Wegkompression immer direkt unter die Wurzel gehängt werden und dadurch der Zugriff in konstanter Laufzeit möglich ist.

Nun ist meine Frage, ob dies so richtig ist? Vielen Dank!
 
M

Marcinek

Gast
Hi,

kannst du auch die Aufgabenstellung einmal posten?

Irgentwie ergibt das für mich keinen Sinn. Wieso kann den einfach alles an die Wurzel gehangen werden?

Ok habe das mal hier

Union-Find-Struktur ? Wikipedia

nachgelesen. Demnach ist deine find( ) Methode noch nicht komplex genug. Diese hat Laufzeiten von O(n). Ist auch logisch , da ich von unten anch oben die Wurzel suchen muss. Deine Implementierung geht von einem Baum der Tiefe 2 aus.

Gruß,

Martin
 
Zuletzt bearbeitet von einem Moderator:
H

herzog

Mitglied
hi,
also es gibt keine richtige Aufgabenstellung, ich habe nur für mich als Klausurvorbereitung den Algorithmus von Kruskal (minimaler Spannbaum) programmiert. Dafür braucht man eine Union-find-Struktur um zu erkennen, ob ein Zyklus gebildet wird. Haben zwei Knoten die gleiche Wurzel würde sich ein Zyklus bilden und daher darf die Kante nicht gewählt werden.
So könnte es ungefähr aussehen:
Java: 
	public static void main(String[] args) {
		Graph g = new Graph(7);
		g.addEdge(1, 2, 3);
		g.addEdge(1, 5, 4);
		g.addEdge(2, 3, 6);
		g.addEdge(2, 4, 5);
		g.addEdge(3, 4, 5);
		g.addEdge(3, 5, 7);
		g.addEdge(4, 5, 7);
		g.addEdge(4, 6, 5);
		g.addEdge(5, 6, 6);
		g.addEdge(5, 0, 10);
		g.addEdge(6, 0, 1);
		System.out.println(g);
		Graph r = Kruskal.kruskal(g);
		System.out.println(r);
	}
public static Graph kruskal(Graph g){
		int nodes = g.getNumberOfNodes();
		Graph r = new Graph(nodes);
		
		Heap<Edge> h = new Heap<Edge>();
		
		UFS ufs = new UFS(nodes);
		
		for(int i = 0; i < nodes; i++){
			List<GNode> l = g.getList(i);
			int j = 0;
			while(j < l.size()){
				h.add(new Edge(i, l.get(j).getNode(), l.get(j).getGewicht()));
				j++;
			}
		}
		
		h.repair();
		
		int counter = 0;
		while(counter < nodes-1){
			Edge e = h.getMax();
			if(ufs.find(e.getFirst()) != ufs.find(e.getSecond())){
				r.addEdge(e.getFirst(), e.getSecond(), e.getGewicht());
				ufs.union(e.getFirst(), e.getSecond());
				counter++;
			}
		}
		return r;
	}

laut unserer Vorlesung wurde gesagt, kruskal ist in O(m + log (n)) machbar, wobei m := Anzahl der Kanten und n := Anzahl der Knoten.
O(m) braucht der Aufbau des Heaps und O(log n) das herunternehmen des Maximums, da danach der Heap wieder repariert werden muss.

Nun fragte ich mich welchen Aufwand die Union-Find-Struktur noch verursacht, da dies in der Vorlesung nicht explizit angesprochen wurde. Ich vermutete wie oben beschrieben find = union = O(1), aber laut Wikipedia müsste find nur in O(log n) gehen, was meine Theorie stark wiederlegen würde. Nun fragte ich mich, ob ich es einfach andere Voraussetzungen angenommen habe und es darum schneller möglich ist oder ob ich es einfach falsch sehe oder mein Vertrauen in Wikipedia zu groß ist? ;)


edit:
Also warum ist die Methode nicht komplex genug? Mir fällt jetzt nichts ein, was nicht gehen würde ;)
und O(n) kann sie doch eigentlich nicht haben. Es ist unmöglich, dass alle Knoten hintereinander hängen und man alle bis zur Wurzel durchlaufen muss. Bei jedem union wird find aufgerufen, also die Knoten direkt unter die Wurzel gehängt. Es sind also maximal 2 schritte nötig. Das ist doch super ;)
 
Zuletzt bearbeitet:
M

Marcinek

Gast
Ja aber welcher Baum hat den eine Tiefe von 2?

Das ist ein Spezialfall.

Für diesen "Baum"

a => b => c => d

würde doch dein Algo nix mehr machen.

Die Wurzel von d ist a

Deine getRoot() methode muss alle vorgänger betrachten und nicht nur zwei.

Wenn Root, dann würde ich succ auf null setzen und nicht auf sich selber, da du hier sonst leicht verwirrende abfragen hast.

Ich habe mir das mal hier angeschaut: Graphical Union-Find Structure

Ich bin mir sicher, dass da noch einiges fehlt. O(1) ist das nicht.

Gruß,
 
Zuletzt bearbeitet von einem Moderator:
H

herzog

Mitglied
aber in der Methode getRoot wird in der Zeile
Java: 
UFSNode n = this.succ.getRoot();
die Wurzel des Vorgängers geholt. Also würde der Algorithmus die Wurzel von c und dann die Wurzel von b und damit a an d zurückgeben. Er würde also schon die richtige Wurzel finden.


Wie sollte denn so ein Baum wie du ihn gezeichnet hast entstehen? Ich meine durch die find aufrufe (die auch bei union ausgeführt werden) werden doch immer alle Knoten unter die Wurzel gehängt. Wie sollte es dann zu einer n-Elemente langen Kette und damit zu dem Aufwand O(n) kommen?
 
M

Marcinek

Gast
ups klar ;) ist ein rekuriver Aufruf.

Dann aber O(n) und nicht O(1).

wodurch dein find() ebenfalls O(n) ist und union 2 x O(n), wass dann auch O(n ) ist.

Und so steht es auch in der wiki
 
H

herzog

Mitglied
Dann aber O(n) und nicht O(1).
Zum Vergrößern anklicken....

Aber warum nur? Graphical Union-Find Structure das ist echt gut und ich habe mir das mal angeschaut. Wenn ich das mit Union by Rank und Pfadkompression mache, sieht man, dass es nur Bäume mit der Höhe von 2 geben kann. Mehr gibt es einfach nicht. Warum sollte dann das find O(log n) sein und nicht O(1) weil es doch quasi konstant ist?

Und warum ist meine Implementierung dann mit O(n)? über die Rekursion werden ja auch maximal 2 weitere Knoten angesprochen. Danach habe ich da auch Pfadkompression drin und es kann einfach keine Kette von n Elementen entstehen. Also auch kein Aufwand von O(n).

Könntest du noch einmal genauer erklären wie du auf O(n) kommst? Weil die Begründung über die Rekursion sehe ich wie oben geschrieben so nicht.
 
M

Marcinek

Gast
1 make set
2 make set
3 make set
4 make set

3, 4 union
1,2 union
1, 4 union

Du erhälst einen Baum der Tiefe 2.

Damit benötigt deine Rekursion min. 2 Schritte

Demnach kann es zu beginn einen entarteten baum geben, wo du alle Knoten durchlaufen musst und somit ist es O(n).

Wäre es O(1) dann kann man die rekursion auch wegmachen. Jedoch würde für das o.g. Szenario dein Algo nicht funktionieren. q.e.d.
 
H

herzog

Mitglied
ok und wenn ich den code von (ist in dem getRoot() der Klasse UFSNode letzter else-Teil):
Java: 
UFSNode n = this.succ.getRoot();
this.succ.setKinder(this.succ.getKinder() - 1);
this.succ = n;
n.setKinder(n.getKinder() + 1);
return n;

in

Java: 
this.succ.setKinder(this.succ.getKinder() - 1);
this.succ = this.succ.succ;
this.succ.setKinder(this.succ.getKinder() + 1);
return this.succ;

ändern würde? Dabei gehe ich davon aus, dass es nie einen Baum geben wird der eine Höhe größer 2 hat, was auch korrekt ist (wie ich es sehe). Ich habe keine Rekursion mehr drin. Würdest du trotzdem sagen, dass der Aufwand noch O(n) ist? Das ganze hängt doch nicht mehr von n ab. es können doch beliebig viele Knoten darein kommen und die Anzahl der Schritte ändert sich nicht.
 
M

Marcinek

Gast
Also mir ist der Algo jetzt nur aus dem wikipedia artikel bekannt. Und den habe ich nicht vollständig gelesen ;D

Wenn du den Algo so änderst, dann gehst du von einem bestimmten Baumart aus. Kann man machen ist dann aber nicht mehr allgemeingültig. (siehe oben). Und ja in diesem Fall wäre es eine Laufzeit von O(1).

Die Rekursion ist wie eine schleife. Sie ist in erster Line abhängig von der Tiefe des Baumes.

Wenn ich eine Tiefe von k habe und n Knoten und es ein enarter Baum k=n ist, dann habe ich einen WorstCase von O(n). Daher im Fall der Rekursion O(n)

Erstmal ist das korrekt aber man kann das bestimmt besser aproximieren. Man müsste dafür mehr ins Detail gehen aber es kämen noch O(log(n)) in Frage.
 
H

herzog

Mitglied
ok dann vielen Dank an dieser Stelle und ich gehe mal davon aus, dass der original Algo länger braucht und ich hier speziell was gemacht habe und darum auf O(1) komme ;)
 
H

herzog

Mitglied
Also in dem Algo von Kruskal (minimaler Spannbaum) brauch so eine Struktur um zu erkennen, ob eine Kante die du einfügen möchtest einen Zyklus bildet. Dann wird sie nämlich nicht eingefügt, weil es sonst kein Spannbaum mehr wird. Ein Zyklus würde dann entstehen wenn zwei Knoten die verbunden werden sollen in der Union-find Struktur die gleiche Wurzel haben.

Wofür man es sonst noch gebrauchen kann, keine Ahnung ;)
 
B

b1zarRe

Bekanntes Mitglied
Okay, danke dir... hatte das neulich im Studium und auch gecheckt, wie man es machen muss... aber irgendwie nie wofür es da ist :D
 

Aktuelle Jobs

Neue Themen


Oben