Minimum Spanning Trees: Kruskal vs Prim’s Quiz Quiz

Explore the differences and similarities between Kruskal’s and Prim’s algorithms for finding minimum spanning trees. This quiz highlights core concepts, algorithm steps, and common pitfalls relevant to graph theory and MST construction, helping learners strengthen their understanding of these essential algorithms.

1. Kruskal’s Algorithm: Edge Selection

   When using Kruskal’s algorithm on a connected weighted graph, which criterion is used to select the next edge to be added to the minimum spanning tree?

   1. The edge that completes a cycle
   2. The edge closest to the starting vertex
   3. The edge with the highest degree node
   4. The edge with the smallest weight that connects two different components

   Explanation: Kruskal’s algorithm always selects the edge with the smallest weight that connects two separate components, merging them without forming a cycle. The option about proximity to the starting vertex describes an aspect of Prim’s algorithm rather than Kruskal’s. Selecting the edge with the highest degree node is unrelated to either algorithm. The option about completing cycles is incorrect because Kruskal’s specifically avoids creating cycles at every step.

2. Prim’s Algorithm: Initialization

   In Prim’s algorithm, what is the expected outcome after the first iteration given a weighted undirected graph with more than one vertex?

   1. All edges with the smallest weight are added at once
   2. One vertex and one edge are included in the spanning tree
   3. Every vertex is visited at least once
   4. The entire minimum spanning tree is completed

   Explanation: After the first iteration of Prim’s algorithm, a single starting vertex and its minimum weight edge are in the spanning tree. Not all minimum edges are added at once—this happens sequentially. The algorithm does not visit all vertices or complete the MST in the first step; these processes occur incrementally as the algorithm runs.

3. Cycle Avoidance in Both Algorithms

   Which technique is commonly used to ensure that cycles do not form when adding edges during Kruskal’s algorithm?

   1. Prim’s priority queue
   2. Depth-first search tree
   3. Sorting vertices alphabetically
   4. Disjoint-set data structure

   Explanation: Kruskal’s algorithm often employs the disjoint-set (union-find) data structure to quickly check if adding an edge will create a cycle. Depth-first search trees are mainly for traversal or detection, not for Kruskal’s union operations. Sorting vertices alphabetically is irrelevant to cycles. Prim’s uses a priority queue, but that's not a cycle avoidance technique for Kruskal’s.

4. Algorithm Suitability for Dense Graphs

   Which algorithm is generally more efficient for finding an MST in a dense graph, and why?

   1. Kruskal’s algorithm, due to faster edge sorting
   2. Prim’s algorithm, since it updates the nearest neighbor quickly
   3. Kruskal’s algorithm, because it skips most edges
   4. Both are equally efficient on dense graphs

   Explanation: Prim’s algorithm is typically better suited for dense graphs because it focuses on expanding from connected nodes and uses data structures like heaps or priority queues that efficiently update the nearest connecting edge. Kruskal’s main advantage is with sparse graphs where the sorting step dominates. Both being equally efficient is incorrect, and Kruskal’s does not inherently skip most edges in dense graphs.

5. Distinctive Starting Point Feature

   Which of the following best describes a key difference in how Kruskal’s and Prim’s algorithms begin constructing a minimum spanning tree?

   1. Kruskal’s requires choosing a starting vertex, but Prim’s does not
   2. Prim’s starts from an arbitrary vertex, while Kruskal’s starts with edge selection only
   3. Prim’s examines all edges at once, Kruskal’s considers one at a time
   4. Both always require starting from the smallest edge

   Explanation: Prim’s algorithm requires a starting vertex and then expands from there, whereas Kruskal’s algorithm begins by selecting the minimum weight edge, independent of any starting vertex. Kruskal’s does not require an initial vertex, so that distractor is incorrect. Prim’s does not examine all edges at once, and both algorithms do not always start with the smallest edge—Prim’s depends on the starting vertex.