Which of the following algorithms is not used for finding a Minimum Spanning…

Concept

A Minimum Spanning Tree (MST) of a connected, weighted, undirected graph is a subset of edges that connects all vertices with the minimum possible total edge weight and contains no cycle. MST algorithms grow or prune a single tree/forest using a cut or cycle rule. This is a fundamentally different problem from the shortest-path problem, which finds the minimum-weight path between vertices and may use negative-weight edges.

Application

Classify each offered algorithm by the problem it solves:

• Kruskal's Algorithm: builds the MST by adding the globally cheapest edge that does not form a cycle (greedy on sorted edges) - an MST algorithm.

• Prim's Algorithm: grows the MST from a start vertex, repeatedly adding the cheapest edge leaving the current tree - an MST algorithm.

• Boruvka's Algorithm: repeatedly adds, for every component, its cheapest outgoing edge, merging components in parallel rounds - an MST algorithm.

• Reverse-Delete Algorithm: starts from the full edge set and deletes the most expensive edges whose removal keeps the graph connected - an MST algorithm.

• Bellman-Ford Algorithm: computes single-source shortest paths and can handle negative edge weights - a SHORTEST-PATH algorithm, not an MST algorithm.

Four of the five listed methods construct a minimum spanning tree; the remaining one solves the shortest-path problem. Hence the algorithm not used for finding an MST is Bellman-Ford.

Cross-check

MST algorithms output a set of edges forming a tree spanning all vertices; their correctness rests on the cut property (the cheapest edge crossing any cut is safe) or the cycle property (a strictly heaviest edge on any cycle is unsafe). Bellman-Ford instead outputs a shortest-path distance/predecessor table from one source and is the standard choice when negative weights are present - confirming it belongs to the shortest-path family, not the MST family.