Minimum Spanning Tree (MST)

code data_structures algorithms ✅ Certified by Educator: 6900d5c4553aea4e9e099d78
Practice Quiz →
Figure: Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) is the smallest set of connections needed to link every vertex in a graph so that the entire graph can be traversed. It uses only what’s necessary—no extra links, no loops. An MST always contains V − 1 edges, meaning if a graph has 10 vertices, you only need 9 edges to connect all of them. The idea is to keep everything reachable while using the minimum number of connections possible.

Figure: Kruskal MST Game: Be Greedy, Avoid Cycles

Build a Minimum Spanning Tree (MST). Each edge has a weight (cost). Drag edges into the MST zone using a greedy strategy: always try to take cheaper edges first, but never create a cycle (a closed loop). If adding an edge would complete a loop, you must skip it—this is exactly how Kruskal’s algorithm works: sort edges by weight, add the lightest edges that don’t form a cycle, and stop once all vertices are connected.

💬 Click on the content to Ask AI
graph_theory graph tree spanning_tree spanning_subgraph weighted_graph undirected_graph connected_graph combinatorial_optimization matroid