Home /
Expert Answers /
Advanced Physics /
consider-the-following-pseudocode-for-kruskal-39-s-algorithm-void-graph-kruskal-int-accepted-ed-pa356
(Solved): Consider the following pseudocode for Kruskal's algorithm: void Graph: kruskal() { int accepted_ed ...
Consider the following pseudocode for Kruskal's algorithm: void Graph: kruskal() { int accepted_edges = 0; DisjointSet ds(num_vertices_); PriorityQueue pq; pq BuildQueue (GetAllEdges()); while (accepted_edges < num_vertices_ - 1) { e = pq.deleteMin(); // Edge e = (u, v) SetType *uset = ds.find(e->getSource()); // Vertex u Set Type *vset = ds.find(e->getTarget()); // Vertex v if (uset != vset) { accepted_edges++; ds.unionSets(uset, vset); } As discussed during class, why is it not necessary to reference the priority queue (pq) in the while loop condition? The priority queue is implicitly referenced in the while loop condition. A spanning tree of a graph G=(V,E) only needs VI - 1 edges. The pseudocode is incorrect. It should check !pq.isEmpty() in the while condition. pq.deleteMin() will always succeed, i.e., return the minimum element in the queue, even if the queue is empty.
Expert Answer
Ans :- option 4 is correct pq is deletemin is always succeed or. Returns the minimum elements in the queue,even if queue is empty. kruskal's algorithm uses a greedy approach to find the minimum