Prim‘s algorithm

Hide text Hide pseudo-code

Apply the algorithm to the following weighted graph (represented as an adjacency list beside the graphical representation) to construct the minimum spanning tree of the graph. The spanning tree is already initialized with the root vertex A, and thus does not containt the edge (A.father, A).

Some additional problems.

MST-Prim(G,root) // G = (V,E,W)
  1   for each u in V
  2           do u.priority = MAX_VALUE
  3                u.unvisited = TRUE
  4                u.father = NULL
  5   root.priority = 0 // root in V
  6   Q.Insert(root); // Priority Queue Q
  7   while Q not empty
  8           do u = DeleteMin(Q)
  9                u.unvisited = FALSE
10                add edge (u.father, u) into the spanning tree
11                for each (u,v) in E
12                           do if v.unvisited and W(u,v) < v.priority
13                                   then v.father = u
14                                            v.priority = W(u,v)
15                                            Q.InsertOrUpdate(v)



  Created Wed Jun 20 16:00:43 EEST 2007 - Powered by SVG-hut