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.