Some popular interview problems on MST
1. | Find the Minimum Cost to Connect All Cities | Practice |
2. | Detect Cycle in an Undirected Graph | Practice |
3. | Bridge in a Graph | Practice |
4. | Minimum Product Spanning Tree | Practice |
5. | Maximum Spanning Tree using Kruskal’s Algorithm | Practice |
6. | Second Minimum Spanning Tree | Practice |
7. | Steiner Tree | Practice |
8. | Find the weight of the minimum spanning tree | Practice |
9. | Second Best Minimum Spanning Tree | Practice |
10. | Minimum spanning tree cost of given Graphs | Practice |
What is Minimum Spanning Tree (MST)
A minimum spanning tree (MST) is defined as a spanning tree that has the minimum weight among all the possible spanning trees
A spanning tree is defined as a tree-like subgraph of a connected, undirected graph that includes all the vertices of the graph. Or, to say in Layman’s words, it is a subset of the edges of the graph that forms a tree (acyclic) where every node of the graph is a part of the tree.
The minimum spanning tree has all the properties of a spanning tree with an added constraint of having the minimum possible weights among all possible spanning trees. Like a spanning tree, there can also be many possible MSTs for a graph.