Minimum Spanning Tree (MST) Graph Problem

Problem: Given a weighted, connected, undirected graph, find a Minimum Spanning Tree - a subset of edges connecting all vertices with minimum total edge weight and no cycles.

Constraints: Up to 10^4-10^5 vertices/edges.

Example: Graph with edges (A-B,1),(B-C,2),(A-C,3) -> MST picks (A-B) and (B-C), total weight 3, skipping the redundant (A-C).

Approach: Two standard algorithms: Kruskal's - sort all edges by weight, greedily add an edge if it doesn't form a cycle (checked via Union-Find/DSU with path compression), until n-1 edges are added, O(E log E). Prim's - grow the tree from an arbitrary start vertex, repeatedly adding the cheapest edge connecting the tree to a new vertex (using a min-priority-queue), O(E log V). Kruskal's is often simpler when edges are given as a flat list; Prim's can be more natural for dense adjacency-matrix graphs.