Question

Which algorithm is commonly used to find a minimum spanning tree?

• A. Prim's
• B. Dijkstra
• C. Binary search
• D. DFS

Hint:

To remember: Prim's grows a tree from a vertex, while Kruskal's sorts all edges first and builds a forest that eventually merges into a single tree.

Answer 1

The Correct Option is A

Concept: A Minimum Spanning Tree (MST) is a subset of edges of a connected, undirected, weighted graph that connects all vertices with the minimum possible total edge weight.
• Standard Algorithms: Prim's Algorithm and Kruskal's Algorithm are the two primary methods.
• Greedy Nature: Both algorithms use a greedy strategy to select the next best edge to include.

Step 1: Understanding Prim's approach.
Prim's starts from an arbitrary seed vertex and grows the tree one edge at a time. It always selects the smallest weight edge that connects a vertex in the tree to one outside.

Step 2: Differentiating from Dijkstra.
Dijkstra's algorithm (B) finds the shortest path from a source to all nodes. While similar to Prim's, its goal is distance minimization, not total edge weight minimization.

Step 3: Eliminating search and traversal.
Binary search (C) is for finding elements in sorted lists. DFS (D) is a graph traversal technique, not an optimization algorithm for MST.