What is a spanning tree?

A spanning tree is a sub-graph of a connected, undirected graph. It has all the vertices of a graph with the minimum possible number of edges. If a vertex is skipped, then it will not be a spanning tree. The edges of a spanning tree may or may not have weights.

Properties of a spanning tree

A spanning tree has the following features:

There can be multiple minimum spanning trees of the same weight having the minimum number of edges.
If all edge weights of a graph are equal, then every spanning tree of the graph will be minimum.
If every edge has a different weight, then only one minimum spanning tree exists.
A connected graph can have multiple spanning trees.
A disconnected graph cannot have a spanning tree.
The spanning tree is acyclic.
If a complete graph has n vertices, the spanning tree will have n-1 edges.
If a single new edge is added to the spanning tree, it will lose its property of acyclicity.
If a single edge is removed from a spanning tree, the tree will lose its connectivity property.

Minimum spanning tree

A minimum spanning tree (MST) or minimum weight spanning tree is a spanning tree that connects every vertex with the minimum total cost. In brief, it is a spanning tree whose sum of weighted edges is the least. Like spanning trees, a graph can have multiple minimum spanning trees. For instance, consider the following graph:

Here, figure 1 shows a weighted graph, and figure 2 shows one of the possible minimum spanning trees. The sum of the minimum weight edges of the spanning tree in figure 2 is 10.

A minimum spanning tree is used for the following:

Finding paths in a map.
Designing networks like water supply networks.
To measure traffic load.

Minimum spanning tree algorithms

There are two methods (algorithms) to construct a minimum spanning tree.

Kruskal’s minimum spanning tree
Prim’s minimum spanning tree

Both algorithms are based on the greedy approach.

Kruskal’s minimum spanning tree algorithm

Kruskal’s algorithm is used to determine a minimum spanning tree for a weighted undirected graph. The algorithm adds the next edge that does not form a cycle in the MST at every step.

Algorithm

Sort the edges of the graph G in the order of increasing (non-decreasing) weight.
Sequentially add each minimum weight edge that does not form a cycle until n-1 edges are used.
Exit the algorithm.

Pseudocode

All MST algorithms need to check if a cycle is formed after adding a new edge to the graph. The best way to find out if a cycle is formed or not is using the Union-Find algorithm. This algorithm divides vertices into clusters to check if the vertices belong to the same cluster. Eventually, this helps identify if a loop is created or not.

Kruskal’s MST algorithm follows the same method. Following is the pseudocode for Kruskal’s minimum spanning algorithm.

MST-KRUSKAL(G,w)

A = ∅

for each vertex v ∈ V [G]

do MAKE-SET (v)

sort edges of E into increasing order by weight w

do if FIND-SET (u) ≠ FIND-SET(v):

Then A = A ∪ {(u, v)}

UNION(u, v)

return A

Example

Consider the following graph:

Now, by using Kruskal’s algorithm to find the minimum spanning tree for the graph, the solution will be as follows:

Solution after step 1 of kruskal algorithm example

Step 1: Kruskal’s algorithm selects the edge having the least weight at every stage. Here, the least-weighted edge is AE with weight 1. So, the algorithm will select that edge.

Solution after step 2 of kruskal algorithm example

Step 2: The next least-weighted edge is CD with weight 2.

Solution after step 3 of kruskal algorithm example

Step 3: The next least-weighted edge is AC with weight 3. So, the algorithm will pick the edge AC and add it to the tree.

Minimum spanning tree of kruskal algorithm example

Step 4: Finally, the next least-weighted edge is AD with weight 4, but it creates a cycle. So, the algorithm will pick the edge AB with weight 5 and add it to the tree. Now all nodes are visited. Hence, the algorithm will terminate. The total cost of the spanning tree will be 1+2+3+5 = 11.

Prim’s minimum spanning algorithm

Prim’s minimum spanning tree algorithm is also a greedy algorithm. Unlike Kruskal’s algorithm, Prim’s MST algorithm considers each node a single tree and continues adding new nodes to the spanning tree from a given graph.

The algorithm takes a graph as an input and determines the subset edges of the graph such that they satisfy the following conditions:

Form a tree that has all the vertices in the graph.
The sum of weights is the minimum among all possible trees that can be formed from the graph.

After selecting an edge, it proceeds to the other endpoint of the edge.

In other words, the algorithm finds a subset of edges that create a tree comprising of all vertices and the total weight of all the edges is minimum. It is a greedy algorithm because it begins with one vertex and selects the least weighted connection from the graph and adds it to the tree, at each step.