Questions: Minimum Spanning Trees: Kruskal's and Prim's Algorithms

Question 1

After running Kruskal's algorithm on a connected weighted graph, you notice it selected an edge that was NOT the globally lightest edge in the graph. Which statement best explains why this is still correct?

• A. Kruskal's algorithm makes mistakes and may not produce a true MST
• B. The cut property guarantees the cheapest edge crossing any partition must be in some MST, so skipping an edge due to cycle detection is always safe
• C. Any spanning tree is an MST if it uses V-1 edges
• D. The globally lightest edge was included earlier, so this selection is a replacement

Answer: (B)

Kruskal's skips an edge only when adding it would form a cycle — meaning both endpoints are already in the same component. The cut property guarantees that the cheapest edge crossing a valid cut (between two distinct components) is always safe to include. Skipping a cycle-forming edge doesn't violate this because that edge doesn't cross any relevant cut. The key is that Kruskal's considers every candidate edge in sorted order; the cut property justifies each acceptance.

Question 2

Prim's algorithm and Dijkstra's algorithm look structurally similar — both use a priority queue and greedily select the minimum-cost next step. What is the key difference in what they are minimizing?

• A. Prim's minimizes total path distance from the source; Dijkstra's minimizes tree weight
• B. Prim's minimizes the weight of the single edge connecting a new vertex to the growing tree; Dijkstra's minimizes the cumulative path cost from the source
• C. Prim's works on undirected graphs; Dijkstra's requires directed graphs
• D. There is no meaningful difference — they produce the same result on the same graph

Answer: (B)

Dijkstra's stores cumulative distance from the source and updates nodes when a shorter total path is found. Prim's stores only the cost of the single cheapest edge connecting each unvisited node to the current tree — it ignores cumulative distance entirely. They can produce very different results: a cheap edge into a node that is far from the source is ideal for Prim's but irrelevant to Dijkstra's if a shorter cumulative path already exists.

Question 3

An MST guarantees the shortest path between nearly every pair of vertices in the graph.

• T. True
• F. False

Answer: False

An MST minimizes the total weight of all edges used to connect the graph, but it does not guarantee shortest paths between pairs of vertices. The shortest path between two nodes may use edges not in the MST. MST optimizes a different objective — minimum total spanning weight — which is useful for network infrastructure but unrelated to point-to-point routing.

Question 4

Kruskal's algorithm can produce a minimum spanning forest (rather than a single tree) if applied to a disconnected graph.

• T. True
• F. False

Answer: True

A spanning forest is the natural extension of spanning trees to disconnected graphs — it contains one spanning tree per connected component. Kruskal's works identically whether the graph is connected or not: it adds the globally cheapest non-cycle-forming edge at each step, and the union-find structure naturally partitions into components. At termination, if the graph has k components, you have k trees. Prim's, by contrast, grows from a single starting vertex and will only find the MST of its connected component.

Question 5

Explain why both Kruskal's and Prim's algorithms are guaranteed to produce a minimum spanning tree, despite using completely different strategies.

Model answer: Both algorithms are correct because they both respect the cut property: the lightest edge crossing any partition of vertices into two non-empty sets must belong to some MST. Kruskal's processes edges globally in sorted order, accepting each edge that doesn't form a cycle — each accepted edge is the lightest crossing the cut between its two endpoint components. Prim's grows the tree locally, always adding the cheapest edge from the current tree to a new vertex — this edge is the lightest crossing the cut between tree and non-tree vertices. In both cases, each greedy choice is justified by the cut property, ensuring the final result is globally optimal.

The cut property converts a greedy intuition ('take the cheapest thing available') into a provable guarantee. Without it, we couldn't know that locally cheap choices would sum to a globally optimal tree. The two algorithms exploit different cuts: Kruskal finds cuts between components, Prim finds cuts between the tree and the rest.