Preskočiť na obsah

Primov algoritmus: Rozdiel medzi revíziami

Pridané 2 bajty ,  pred 11 rokmi
preklepy
(preklepy)
** Pridaj ''v'' do V', pridaj (u,v) do E'
* Výstup: T(V',E') je minimálna kostra grafu
 
 
== Časová zložitost ==
{| class="wikitable"
! Dátová štruktúra s ohodnotením hrán !! Celková časová zložitosť
|-
| matica susednosti || O(n<sup>2</sup>)
|-
| [[binárna halda]] a ''zoznam susedov'' || O((n + m) log(n)) = n log(n)
|-
| [[Leonardo Pisano Fibonacci|Fibonacciho]] [[Halda (dátová štruktúra)|halda]] a ''zoznam susedov'' || O(m + n log(n))
|}
 
Jednoduchá implementácia s reprezentáciou grafu pomocou matice susednosti a prehľadávaním poľa ohodnotení má časovú zložitosť ''O(n<sup>2</sup>)''. S použitím binárnej haldy a zoznamu susedov dosiahneme zložitosť ''O(m log n)'', kde m je počet hrán a n je počet vrcholov. S použitím sofistikovanej Fibonacciho haldy zložitosť znížime až na ''O(m + n log n)'', čo je výhodné najmä pri grafoch, kde ''m'' je <math>\Omega(n log n)</math>.
 
== Príklad ==
|}
 
== Časová zložitost ==
{| class="wikitable"
! Dátová štruktúra s ohodnotením hrán !! Celková časová zložitosť
|-
| matica susednosti || O(n<sup>2</sup>)
|-
| [[binárna halda]] a ''zoznam susedov'' || O((n + m) log(n)) = n log(n)
|-
| [[Leonardo Pisano Fibonacci|Fibonacciho]] [[Halda (dátová štruktúra)|halda]] a ''zoznam susedov'' || O(m + n log(n))
|}
 
Jednoduchá implementácia s reprezentáciou grafu pomocou matice susednosti a prehľadávaním poľa ohodnotení má časovú zložitosť ''O(n<sup>2</sup>)''. S použitím binárnej haldy a zoznamu susedov dosiahneme zložitosť ''O(m log n)'', kde m je počet hrán a n je počet vrcholov. S použitím sofistikovanej Fibonacciho haldy zložitosť znížime až na ''O(m + n log n)'', čo je výhodné najmä pri grafoch, kde ''m'' je <math>\Omega(n log n)</math>.
 
 
47

úprav