Differences between revisions 2 and 5 (spanning 3 versions)
⇤ ← Revision 2 as of 2004-10-27 17:11:13 →
Size: 1031
Editor: yakko
Comment:
← Revision 5 as of 2020-01-26 18:59:34 → ⇥
Size: 1026
Editor: scot
Comment:
Deletions are marked like this. Additions are marked like this.
Line 3: Line 3:
    MST-Prims(G(V,E),w(e∈E),r) // G-graph, w-weight function, r is where we start MST-Prims$$(G(V,E),w(e \in E),r)$$ // G-graph, w-weight function, r is where we start
Line 18: Line 18:
    Running Time:
    O(V+VlogV+ElogV), which reduces to:
Line 21: Line 19:
 O(ElogV)

    However this can be increased by using a fibonacci heap where Extract-Min in O(log v) and Decrease-Key in O(1), thus we can reduce line 11, and get a running time of

 O(E+VlogV)
 Running Time: , which reduces to: However this can be increased by using a fibonacci heap where Extract-Min in $$O(log v)$$ and Decrease-Key in $$O(1)$$, thus we can reduce line 11, and get a running time of $$O(E+VlogV)$$.

Prim's Algorithm

MST-Prims // G-graph, w-weight function, r is where we start 

   1. for each u in V                           O(V)
   2.   key[u]=infinity;                                O(1)
   3.   p[u]=Nil                                        O(1)
   4. key[r]=0 //decrease key                   O(1)
   5. Insert V into Q //a min priority queue    O(V)
   6. While Q!=empty set;                       O(V)
   7.   u=Extract-Min(Q)                                O(logV)
   8.   for each v Adj[u]                       2E times =O(E) We analyze this seperate
   9.      if v in Q and w(u,v)<key[v]          O(1)
   10.         p[v]=u                                   O(1)
   11.         key[v]=w(u,v) //decrease key operation   O(logV)

Running Time: , which reduces to: However this can be increased by using a fibonacci heap where Extract-Min in and Decrease-Key in , thus we can reduce line 11, and get a running time of .

PrimAlgorithm (last edited 2020-01-26 18:59:34 by scot)