Which algorithm builds a Minimum Spanning Tree by repeatedly adding the smallest edge that connects two components?

Which algorithm builds a Minimum Spanning Tree by repeatedly adding the smallest edge that connects two components?

• A. Kruskal's algorithm
• B. Prim's algorithm
• C. Dijkstra's algorithm
• D. BFS

Answer: (A)

The process described matches Kruskal's algorithm. It builds a minimum spanning tree by looking at edges in order of increasing weight and adding an edge only if it connects two distinct components, i.e., it doesn’t form a cycle. A union-find (disjoint-set) structure tracks which vertices belong to which components, so each time a smallest edge links two separate components, we merge them and include that edge. This continues until all vertices are connected, giving a spanning tree with the minimum possible total weight. Prim's algorithm, in contrast, grows a single tree by repeatedly adding the smallest edge that connects the current tree to a new vertex. Dijkstra's algorithm finds shortest paths from a source to all vertices, not a minimum spanning tree. BFS is a graph traversal that explores in layers and does not account for edge weights.

The process described matches Kruskal's algorithm. It builds a minimum spanning tree by looking at edges in order of increasing weight and adding an edge only if it connects two distinct components, i.e., it doesn’t form a cycle. A union-find (disjoint-set) structure tracks which vertices belong to which components, so each time a smallest edge links two separate components, we merge them and include that edge. This continues until all vertices are connected, giving a spanning tree with the minimum possible total weight.

Prim's algorithm, in contrast, grows a single tree by repeatedly adding the smallest edge that connects the current tree to a new vertex. Dijkstra's algorithm finds shortest paths from a source to all vertices, not a minimum spanning tree. BFS is a graph traversal that explores in layers and does not account for edge weights.