Home /
Expert Answers /
Computer Science /
question-12-consider-the-following-pseudocode-for-kruskal-39-s-algorithm-void-graph-kruskal-int-pa584
(Solved): QUESTION 12 Consider the following pseudocode for Kruskal's algorithm: void Graph::kruskal() { int ...
QUESTION 12 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 = vset) { accepted_edges++; ds.unionSets(uset, vset); } } Why is it not possible for pq to run out of elements before the while loop terminates? O The pseudocode is incorrect. It should check !pq.isEmpty() in the while condition. pq is initialized with all edges E of a graph G=(V, E). The while loop builds a minimum spanning tree MST of G. Since MST is a subset of G, it will never have more edges than G. pq is initialized with all edges E of a graph G=(V, E). The while loop builds a minimum spanning tree MST of G. Since MST is a subset of G, it will always have an equal number of edges as G. O pq is initialized with all edges E of a graph G=(V, E). The while loop builds a minimum spanning tree MST of G. Since MST is a subset of G, it will never have fewer edges than G.