Thread: Prim's algorithm

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    50

    Prim's algorithm

    Code:
    Prim(G, w, s)
    //Input: undirected connected weighted graph G = (V,E) in adj list representation,
    source vertex s in V
    //Output: p[1..|V|], representing the set of edges composing an MST of G
    01 for each v in V
    02 color(v) <- WHITE
    03 key(v) <- infinity
    04 p(v) <- NIL
    05 Q <- empty list // Q keyed by key[v]
    06 color(s) <- GRAY
    07 Insert(Q, s)
    08 key(s) <- 0
    09 while Q != empty
    10 u <- Extract-Min(Q)
    11 for v in Adj[u]
    12 if color(v) = WHITE
    13 then color(v) <- GRAY
    14 Insert(Q,v)
    15 key(v) <- w(u,v)
    16 p(v) <- u
    17 elseif color(v) = GRAY
    18 then if key(v) > w(u,v)
    19 then key(v) <- w(u,v)
    20 p(v) <- u
    21 color(v) <- BLACK
    22 return(p)
    I need to find the big O for the above algorithm. How do i start?

    Please help me.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Appropriate container for prim's algorithm
    By Elysia in forum C++ Programming
    Replies: 6
    Last Post: 05-10-2010, 01:20 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. prims algorithm
    By condorx in forum C Programming
    Replies: 0
    Last Post: 11-09-2003, 06:20 AM