Find Minimum Spanning Tree

Minimum Spanning Tree

Minimum spanning tree (or minimum weight spanning tree) in a connected weighted undirected graph is a spanning tree of that graph which has a minimum possible weight. The weight of a tree means a sum of the edges’ weights.

In other words, minimum spanning tree is a subgraph which contains all the vertexes of the original graph, while the sum of the arcs’ weights is minimal.

Algorithm usage examples

With the help of the searching algorithm of a minimum spanning tree, one can calculate minimal road construction or network costs.

Searching algorithm

We use Prim’s algorithm for searching.

How to use

1. Create a graph.
2. Choose “Algorithms” in the menu bar then “Find minimum spanning tree”.