Connect every vertex with minimum total edge weight
A minimum spanning tree applies to a connected, undirected weighted graph and contains V-1 edges without cycles. It minimizes total selected edge weight, not the shortest path from one chosen source.
Kruskal sorts edges globally, adding an edge only when its endpoints belong to different components. Prim grows one connected tree by repeatedly choosing the lightest edge crossing its boundary. Both rely on a cut-property argument: a minimum-weight edge crossing an appropriate cut is safe for some MST.
For edges A–B:1, B–C:2, A–C:4, both methods choose weights one and two for total three. Negative edge weights are allowed; disconnected graphs produce a minimum spanning forest if the implementation visits every component.
Exercise
Trace both methods on the same graph and record why each selected edge is safe. Add equal-weight edges and observe that multiple different MSTs may have the same total.
Check: a graph's MST does not necessarily preserve shortest paths between every pair. State whether self-loops and parallel edges are allowed in your representation.