TRAKLA2 - Prim‘s algorithm

Prim‘s algorithm

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions 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. In this exercise you can only click edges, i.e., apply the algorithm by adding edges to the spanning tree in correct order. The color of the spanning tree is red. Hint: You can adjust the layout of the graph by changing the font size.
MST-Prim 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)