Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed. Submit your homework via Blackboard as one PDF or Word document.
(25) [Prim’s MST algorithm: tracing] Run the Prim’s algorithm shown below (implemented using a priority queue) against the graph shown below. Assume the node 5 is picked as the start node, that is, s = 5. At the end of the While loop in each iteration, show the content of the cut S, the content of the MST T, and the content of the priority queue Q. Specifically, show the content of S as a set of nodes, the content of T as a set of edges, and the content of Q as a set of ordered pairs of a node number v and a priority key π(v). (For ease of grading, list the priority queue elements in an increasing order of the node number.) For example, their contents before the 1st iteration is S = { }, T = { }, and Q = {(1, ∞), (2, ∞), (3, ∞), (4, ∞), (5, 0), (6, ∞), (7, ∞), (8, ∞)}.
Prim(G, s) {
Initialize Q of V with π(v) for each node v in V.
Pick an arbitrary node as the start node s.
S { }, T { }, π(s) 0.
while (Q is not empty)
v = ExtractMin(Q).
Add v to S.
if v ≠ s then add the edge (pred(v),v) to T. // pred ≡ “predecessor” for each edge e=(v, w) such that w ∉ S
if (ce < π(w)) {
π(w) = ce, pred(w) = v.
ChangeKey(Q, w, π(w)).
}
}
endwhile
}
(25) [Kruskal’s MST algorithm: tracing] Run the Kruskal’s MST algorithm shown below on the graph shown below using disjoint sets data structure represented as a forest. Show the forest data structure representing disjoint sets after the initialization of singleton sets (represented as single-node trees) and after considering each edge (to either add it or discard it). If the disjoint sets do not change in any step, you do not need to show the forest structure. In addition, show the final minimum spanning tree (by making the included edges thicker or red). Use the union-by-size heuristic when doing union of two sets.
Kruskal(G, c) { // c: set of edge weights
Sort edges in an increasing order of weight c to e1,e2,...,em.
T
MakeUnionFind(V).
for each edge ei in the sorted order
Identify the two end nodes (u,v) of ei.
root1 = Find(u). root2 = Find(v).
if (root1 ≠ root2) {
T {ei} Union(root1, root2).
}
}
return T
}
Last modified: October 3, 2019
