Minimum Spanning Tree and Greedy Algorithms

Have you ever thought about how exactly we find the shortest path in a grid? Or how we find the most cost-effective path in a graph? If you have then you have come to the right place for an answer.

Before learning about minimum spanning trees, we should take a look at Spanning trees.

What is a Spanning Tree?

A Spanning tree is an acyclic subgraph of a connected graph. Suppose we have a graph G(V, E) where the number of vertices and edges are denoted by V and E respectively then the Spanning tree from this graph is denoted as G’(V’, E’) where

• the number of vertices of the graph and spanning tree remains the same

V=V`

• And the number of edges of a spanning tree is a subset of the number of edges of a graph.

E`=|V| — 1

Let us take an example of a graph G(V, E) :

Spanning Trees

Minimum Spanning Tree (MST)

Minimum spanning tree, an extension of a spanning tree where the cost is minimum among all the spanning trees. The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be multiple minimum spanning trees for a graph.

Example: A minimum spanning tree for a connected graph. The weights on edges are shown, and the edges in a minimum spanning tree are shaded.

MST for a connected graph

We see an undirected graph has been changed to a spanning tree graph by making an acyclic graph whose vertices are all connected.

In the case of MST, we select the least weighted edge and take care that no cycle is formed.

We see a substantial difference between the costs of spanning trees and MST which helps us conclude that the MST is more efficient and cost-effective than the spanning tree.

This was an example with a small number of edges but what happens when we have a lot of edges. For that, we would require more efficient methods to find the MST. This is where Greedy Algorithms (Prim’s and Kruskal’s Algorithm) come in.

1. Kruskal’s Algorithm

In this greedy algorithm, the least weighted edges are added one after the other in the growing spanning tree such that no cycle gets created. We use it to find the subset of edges by which we can traverse every vertex of the graph.

We see that it starts off with the least weighted edge and then moves in a non-decreasing way. It selects the next least weighted edge and checks for no cycle formation. This step is repeated until we have (V-1) edges.

Functionality:

Kruskal’s algorithm is widely used for sparse graphs where we don’t have lots of edges. It is ideal for a good disjoint set data structure and a good sort function. It can be used in LAN Networks, TV networks, etc.

Steps to find MST using Kruskal’s algorithm:

1. Sort the graph edges in non-decreasing order.
2. Start adding the least weighted edges to the MST only if a cycle is not formed.
3. Continue with step 2 until we get (V-1) edges in the spanning tree.

Implementation of Kruskal’s Algorithm:

2. Prim’s Algorithm

In this method, we pick a position or node and start adding on the vertices in the growing MST. It finds a subset of edges that includes every vertex of the graph such that the total weights of the edges calculated are minimized.

In Prim’s Algorithm, we will start with an arbitrary node and select it. In each step, we will select a new vertex that is adjacent to the one that we have marked. Now, Prim’s algorithm will select the cheapest edge and select the vertex.

Functionality:

Prim’s algorithm is used to solve various complex mathematical problems like Travelling salesman problems, Game Development, etc. It is an efficient way of finding MST of a dense graph. In addition, Prim’s algorithm is faster as compared to Kruskal’s algorithm.

Steps to find MST using this algorithm:

In Simple Terms

1. Pick any vertex and that will be the starting point of your MST.

2. Select the least weighted edge going out of the vertex to any other connected vertex. See to it that no cycles are created in the process.

3. Repeat the above steps until all the vertices are connected such that no cycle is formed.

Algorithm

Step 1: We select the source node first.

Step 2: We then assume all nodes weigh infinity except the source node as shown in the image above.

Step 3: Next step would be to select the least weighted node and assign its value equal to 0.

Step 4: Make a set of MST to keep track of all the processed nodes.

Step 5: Either relax or Compute all the adjacent edges.

Step 5.1: Whenever the cost of the adjacent edge is lower than infinity, update the cost of the edge.

Step 5.2: Select the adjacent edge which costs comparatively lower than the other.

Step 6: Till the set MST includes all the vertices, repeat the above steps from 2 to 6.

Implementation of Prim’s Algorithm:

We have covered the Minimum Spanning tree and the Greedy algorithm’s in this blog. I hope this blog helps you understand the basics clearly and answers all your queries!!