Seite 1 von 1

Fehler im Video Kruskal

Verfasst: 9. Aug 2013 15:06
von DenK
Hallo,
ich glaube ich habe einen Fehler in der asymptotischen Komplexität entdeckt, bzw. ist es im Wiki richtig. Die Komplexität ist statt der im video gesagten (n * T(n)+ m * log(m)) wohl eher (m* T(n)+ m * log(m)).

Die Uniteoperation muss ja genau |V|-1 mal durchgeführt werden und ist daher genau gleich Anzahl der Kanten.

Ich hoffe das ist richtig, sonst wäre ich für eine kurze Erklärung sehr dankbar.

Re: Fehler im Video Kruskal

Verfasst: 12. Aug 2013 19:21
von Prof. Karsten Weihe
DenK hat geschrieben: Die Uniteoperation muss ja genau |V|-1 mal durchgeführt werden und ist daher genau gleich Anzahl der Kanten.
Ja, gleich Anzahl der Kanten im Baum. Aber \(m\) ist die Anzahl der Kanten im Eingabegraphen.

KW

Re: Fehler im Video Kruskal

Verfasst: 12. Aug 2013 19:57
von DenK
Danke!

Das bedeutet dass (n * T(n) + m * log(m)) richtig ist? Dann müsste das im Wiki geändert werden, denn die unite-Operation wird ja auf jedenfall n-mal ausgeführt und nicht m-mal. Viele Kanten fallen ja durch die find-Operation mit konstanter Laufzeit schon raus.

Re: Fehler im Video Kruskal

Verfasst: 13. Aug 2013 07:30
von Prof. Karsten Weihe
Hmh, der Witz ist: Beides ist richtig. 8)

Mehr als n-mal geht nicht, weil die Grundmenge nur aus n Elementen besteht.

Mehr als m-mal geht ebenfalls nicht, weil es nur m Iterationen gibt.

KW

Re: Fehler im Video Kruskal

Verfasst: 13. Aug 2013 08:28
von DenK
Ok, alles klar danke! Wenn beides richtig ist gibt es weniger Möglichkeiten Fehler zu machen, auch gut :)

Re: Fehler im Video Kruskal

Verfasst: 14. Aug 2013 18:45
von stef
Hallo,
ich hätte da auch noch mal eine Frage zu dem Video.
Auf der Folie wo der Min Spanning Tree zu sehen ist sagt Hr. Weihe das die größte Kantenlänge 13 ist.
Aber ich seh auf der Folie nur die längste Kantenlänge zwischen v1 und v6 mit 12? Oder wird die Kantenlänge mit 13 irgendwie berechnet?

Wenn die 12 richtig ist wäre ja dann auch die Berechnung für dem Max Spanning Tree mit der 12 oder?

Viele Grüße

Re: Fehler im Video Kruskal

Verfasst: 19. Sep 2013 18:11
von AnnaW
Darüber bin ich gerade auch gestolpert. 12 sollte schon richtig sein, oder?

Viele Grüße

Anna