Home /
Expert Answers /
Computer Science /
consider-the-following-pseudocode-for-kruskal-39-s-algorithm-void-graph-kruskal-int-accepted-edg-pa709
(Solved): Consider the following pseudocode for Kruskal's algorithm: void Graph: kruskal() { int accepted_edg ...
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 SetType "vset= ds.find(e->getTarget()); // Vertex v if (uset I vset) ( accepted edges++; ds unionSets(uset. vset); As discussed during class, why is it not necessary to reference the priority queue (pa) 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-I edges. pq.deleteMin() will always succeed, i.e., return the minimum element in the queue, even if the queue is empty. The pseudocode is incorrect. It should check Ipq.isEmpty() in the while condition.
Expert Answer
Solution;- The pseudocode is incorrect. It should check if pq.isEmpty() in the