Minimum spanning tree

The minimum spanning tree (or the minimum spanning tree) in a connected weighted undirected graph is the spanning tree of this graph, having the minimum possible weight, where the weight of the tree is the sum of the weights of the edges included in it.

Example

An example of a minimum spanning tree in a graph. The numbers on the edges indicate the weight of the edges.

The task of finding the minimum spanning tree is often found in a similar formulation: for example, there are towns that need to be connected by roads so that you can get from any city to any other (directly or through other cities). It is allowed to build roads between given pairs of cities and the cost of building each such road is known. It is required to decide which roads need to be built in order to minimize the total cost of construction.

This task can be formulated in terms of graph theory as the problem of finding the minimum spanning tree in a graph whose vertices represent cities, edges are pairs of cities, between which a straight road can be made, and the edge weight is equal to the cost of building the corresponding road.

Algorithms
There are several algorithms for finding the minimum spanning tree. Some of the most famous ones are listed below:

Prima's algorithm;
The Kraskal algorithm (or the Kruskal algorithm);
Boruvki algorithm.
Related tasks
The problem of finding the minimum spanning tree is similar to the Steiner tree problem. It contains several points on a plane and it is required to lay a path graph between them so as to minimize the sum of the path lengths. The main difference from the minimum spanning tree problem is that it is allowed to add additional branch points in order to further reduce the sum of edge lengths. The Steiner tree problem is NP-complete.

See also

• Kruskal algorithm