# Algorithm: Minimum Spanning Tree

This blog is about a very common algorithm applied on a connected undirected graph. So the algorithm is known as minimum spanning tree. In this blog we will talk about what it is, how to find it, its applications, which algorithm is better. Lets get familiarised with background before getting into further specifics.

## So what is a graph?

Graph is broadly distributed in Directed graph and Undirected graph.

# What is a Spanning Tree?

Spanning tree is the subset of graph. Say u have a graph G(V,E) then your spanning tree will contain the same number of vertices ( in this case V) but the minimum number of edges (in this case edges will be ≤ E).

# Certain Properties of spanning tree..

•All possible spamming trees have same no. of edges and vertices

•Don’t have cycles

•Minimally connected

•Adding any edge will create cycle

•Spanning trees edges are equal to (no. of vertices)-1

## Why do we need MST?

Say, you have started a new telecommunications company and you have towers that spread across a large area. Now you want to connect those towers from each other so that the data can be passed. Connecting different towers involve in different costs. So now the problem is that you have to minimize the cost. How will you do that?

So, here the solution would be finding a MST because if its not a spanning tree, you can remove a connection and then also it would be still be connected. So to minimise the cost, it has to be a spanning tree with minimum total cost.

# How can we find MST in a graph?

1. Kruskal’s Algorithm
2. Prim’s Algorithm

Lets first start understanding Kruskal’s Algorithm….

# Kruskal's Algorithm:

So the steps to get a MST from Kruskal’s Algorithm are as follows:

1. Sort the edges in ascending order (in reference to edge’s weight).
2. Start by adding edges one by one from least to most weighted.
3. If adding any edge creates a cycle skip that edge and go to the next.

As we can see in Fig 4 we were given a weighted graph with 7 vertices. Hence the resulting minimum spanning tree would be of 6 edges (|E|=|V - 1|= 7-1 = 6). In this examples these r the following steps:

Step 2: Choose the edge with the least weight, if there are more than 1, choose anyone.

Step 3: Choose the next shortest edge that doesn’t create a cycle and add it

Step 4: Repeat until you have a spanning tree.

## Kruskal’s Algorithm Pseudocode

The most widely recognized approach to track down this out is an algorithm called Union Find. The Union-Find algorithm divides vertices into clusters, allowing us to determine if two vertices belong to the same cluster and thus if adding an edge would result in a loop.

## Complexity of Kruskal's Algorithm

Both of these are comparable as E ≤ V*V, hence log(E) ≤ 2*log(V).

# Prim’s Algorithm:

So the steps to get a MST from Prim’s Algorithm are as follows:

1. Make a set of vertices that are used in MST.
2. Make a list of edges that connect vertices in the set to vertices that aren’t in the set.
3. Select a vertex and add it to the set.
4. To the list generated in step 2, add all the edges that contain a vertex.
5. Choose the smallest weighted edge and search to see if one of the vertex is missing from the set. Remove edge from list and repeat the process if both of them are in the set.
6. Change the list of edges by adding the vertices to the set.
7. Proceed until no vertices are left in the sequence.

As we can see in Fig 6we were given a weighted graph with 7 vertices. Hence the resulting minimum spanning tree would be of 6 edges (|E|=|V — 1|= 7–1 = 6). In this examples these r the following steps:

Step 2: Choose a vertex

Step 3: Choose the shortest edge from this vertex and add it

Step 4: Choose the nearest vertex not yet in the solution

Step 5: Choose the nearest edge not yet in the solution, if there are multiple choices, choose one at random.

Step 6: Repeat until you have a spanning tree.