Differences between revisions 1 and 4 (spanning 3 versions)
⇤ ← Revision 1 as of 2004-10-27 17:09:22 →
Size: 1033
Editor: yakko
Comment:
← Revision 4 as of 2020-01-26 18:59:04 → ⇥
Size: 1028
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 6: Line 6:
   1. for each u∈V O(V)
   2. key[u]=∞  O(1)		    1. for each u in V          O(V)
   2. key[u]=infinity; O(1)
Line 11: Line 11:
   6. While Q!=∅   O(V)    6. While Q!=empty set; O(V)
Line 13: Line 13:
   8. for each v∈Adj[u] 2E times =O(E) We analyze this seperate
   9. if v&#8712;Q and w(u,v)<key[v] O(1)		    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)
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

   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)