Minimum Spanning Trees (Prim's Algorithm)

Question 1

What is a Minimum Spanning Tree (MST)?

Answer 1

A subset of a graph’s edges that connects all vertices with no cycles and minimum total edge weight.

Question 2

How does Prim’s Algorithm work?

Answer 2

Starts from any node, grows the MST by adding the smallest edge connecting a visited and unvisited node.

Question 3

What data structure optimizes Prim’s Algorithm?

Answer 3

A priority queue (e.g. min-heap) to efficiently get the minimum-weight edge.

Question 4

What is the time complexity of Prim’s Algorithm?

Answer 4

O((V + E) log V) with a min-heap and adjacency list.