Bsp. 6.5 und 6.6

[Sensei]

Muss man da eigentlich einfach nur den Kruskal oder Prim Algo hernehmen und die Gewichtsortierung am Anfang umdrehen, sodass die schwersten Kanten zuerst kommen, oder?

Die Laufzeit is dann gleich wie bei Kruskal/Prim --> im konkreten Fall is sicher Kruskal besser, weil der von Kanten abhängt und wir hier einen dünnen Graphen haben. Laufzeit also theta(|e|log|e|).

oder irre ich mich da grundlegend?

[Bug]

Ich habs mittels Kruskal gemacht, weiss allerdings auch nicht ob das genügt

[locutus]

Wenn ich mir die Angabe ansehe, dann ist dort nichts anderes gefragt, als ein Maximaler Spanning Tree. Das bedeutet, wenn man statt den niederwertigen die hochwertigen Kanten selektiert, dann kann man sowohl Kruskal als auch Prim verwenden, da beide den gleichen enstprechenden Spanning Tree liefern.

[tschurlo]

So, von der Idee her, sind wir uns anscheinend bereits einig. Jetzt zur konkreten Beantwortung:


ad 5) Also ich hab mir auch den Kruskal hergenommen, Implementierung mit Union Find; Aenderung: Kanten absteigend statt aufsteigend sortieren -> Sortierung bestimmt auch die Laufzeit n*log(n); ansonsten Algorithmus so wie im Skriptum; Datentyp kann man vielleicht noch sagen, dass man DDM (dyn. disj. Menge) dafuer braucht und die in Form eines Arrays realisieren kann

ad 6) jetzt zum Bsp am Zettel: also zuerst Kanten absteigend sortieren und nacheinander aufnehmen, aufpassen, dass dabei kein Kreis entsteht.
-> Gewicht: 468 wenn ich mich nicht verzaehlt habe.

Einverstanden?

PS: Cool! 500 Posts! Zumindest im Forum hab ich mein Bakk bereits :D

[wolti]

Hallo,

Ich habe auch ein Gewicht von 468. Du dürftest dich also nicht verzählt haben.

Grüße,
Wolti

[tschurlo]

Supi, wenn mir wolti recht gibt, dann nehm ich stark an, dass es wirklich stimmt! :verycool:

[Sensei]

Habs auch so. Nach dreimaligem nachzählen. Hatte tlw. Abweichungen von 60 Zählerchen :D

[Plastiktiger]

Komm auch drauf. Scheinbar verzählen wir uns gleich. hatte auch zuerst 404....

[Petzi]

beim Kruskal Algo. vom Skriptum, muss man dann aber aufpassen, dass die Kanten eh absteigend sortiert sind, da das Kantengewicht maximal sein soll

also statt in Zeile 2: sortiere Kanten: w(e1) <= w(e2) <= ... <= w(em);
müsste man dann schreiben: w(e1) > w(e2) > ... > w(em);

alle einverstanden??

[tschurlo]

Ja, hab ich schon ein paar Postings weiter oben geschrieben:
ad 5) Also ich hab mir auch den Kruskal hergenommen, Implementierung mit Union Find; Aenderung: Kanten absteigend statt aufsteigend sortieren
Aber ich denke, du kannst ruhig >= anstatt > schreiben, denn es kann ja ebenso vorkommen, dass du mehrere Kanten mit gleichem Gewicht hast.

lg

[Petzi]

aja, stimmt
steht schon weiter oben

hab ich wohl überlesen http://hades.gothic.at/iforum/images/smilies/coolsmile.gif


beim Gewicht hab ich auch 468 rausbekommen

[Millencolin]

komisch ich hab nach 5mal eintippen immer 465 bekommen !

[Millencolin]

77
55
54
36
29
28
26
25
24
23
23
22
14
11
9
9
----
465 ????

[Millencolin]

ups bin grad draufgekommen das ich eine kante übersehen hab:
richtig is es so:
77
55
54
36
29
28
26
25
24
23
23
22
14
12
11
9
---
468 ;)

[Unic0der]

ad Beispiel 6)

Ich würde bei diesem Beispiel die Laufzeit wie folgt erklären:

Die Laufzeit ist bei mir: Theta (n*log n)
Sie ist im wesentlichen vom sortieren der Kanten bestimmt (z.B. n*log n habe ich deshalb, weil ich zum Sortieren der Kanten Quicksort eingesetzt habe). Das eigentliche erstellen des MST mittels der Union-Find Datenstruktur fällt somit Laufzeitmäßig nicht ins Gewicht.

Ist das so halbwegs korrekt erklärt?
Wenn nicht bitte ich euch um Korrektur bzw. Erklärung wie's richtig geht.

Zur Nr. 5 hätte ich auch noch ne Frage)

Ich habe anscheinend vergessen, wie dieser Kruskal-Pseudocode nun funktioniert. Mir ist nicht ganz klar was auf S und auf T abgelegt wird (siehe Skript). Könntet ihr mir das bitte kurz erklären ?!


Ciao, MacOS X

[Sebi]

in S stehen die ganzen "sets" drinnen, die du mit makeset erzeugst und dann mit union verbindest.

Und in T legst du alle Kanten ab, die dir deine Lösung bilden, d.h. die deinen spanning tree bilden... also jede kante die du dazunimmst kommst nach T

Sollte ich mich mal wieder unverständlich ausgedrpckt haben, stehts im Scriptum auf Seite 124und 125.

Wobei auf 125 bei dieser Abbildung wo sie den Algorithmus durchgehen das S die Spalte "Komponenten(Bäume)" ist, und imm wenn bei Hinzunahme zu T ein Hackerl ist die Kante (mittlere Spalte) eben in T hineingetan wird.

lg
sebi

[Unic0der]

Hat jemand kurz Zeit meine Fragen von weiter oben zu beantworten ? ;)

[Flowyes]

@MacOS X: So, schauen wir mal ob ich was konkretes brauchbares sagen kann. Also deine erste Antwort mit der Laufzeit stimmt jedenfalls, Sortierung bestimmt hier das ganze mehr oder weniger, unter n*log(n) geht's deshalb nie, aber besser wäre vielleicht zu sagen: O(|E|*log(|E|)). Union-find kannst vergessen wie du sagst...

Und zum Kruskal: Du sortierst alle Kanten nach Gewicht.(Zeile 2) Dann für alle Knoten makeset() aufrufen ---> jetzt zeigt jeder Knoten auf sich selber und offensichtlich enthält S |V| Elemente.
Wenn du jetzt eine Kante hast, bei der die beiden Endknoten nicht in der selben Menge liegen, nimmst du diese Kante in T und machst du diese zu einer Menge. (Anfangen natürlich bei der Kante mit dem niedrigsten Gewicht usw...) Solange bis nur mehr eine Menge bleibt. Das war's im Grunde. Deswegen 'bis nur eine Menge bleibt' denn wenn's 2 Mengen gibt, dann haben wir noch keinen Baum, weil nicht zusammenhängend...

[Unic0der]

jup, danke jetzt hab ichs verstanden. Die Übung kann kommen :D ...

[locutus]

zuerst Kanten absteigend sortieren und nacheinander aufnehmen, aufpassen, dass dabei kein Kreis entsteht

Wenn man im Kruskal-Algorithmus die sortierten Kanten von hinten nach vorne (|E| ... 1) abarbeitet, dann kann man auch weiterhin aufsteigend sortieren.

Oder man multipliziert alle Kantengewichte mit -1, bildet den MST ganz normal mit Kruskal oder Prim und multipliziert die Summe wiederum mit -1. Dann braucht man den Algorithmus gar nicht modifizieren. :ausheck: