What is a Minimum Spanning Tree (MST)?

Difficulty: 5/10

Kruskal's algorithm, Prim's algorithm, dynamic MST

Minimum Spanning Tree

A Minimum Spanning Tree is a spanning tree of a connected, weighted, undirected graph whose total edge weight is minimum among all spanning trees. It connects all vertices without cycles and contains exactly V-1 edges. Standard algorithms are Kruskal and Prim.

javascript

1
MST applies to weighted undirected graphs.
2
It contains every vertex.
3
It contains exactly V-1 edges.
4
It has no cycles.
5
Kruskal and Prim are standard MST algorithms.

Scenario Questions

0-2 years experience

Follow-up Questions