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?

Fig 1: 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).

Fig 2: Undirected graph and corresponding spanning trees

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

What is a MST?

Fig 3:Graph and corresponding spanning trees and MST

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.
Fig 4: Kruskal’s Algorithm

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 1: Start with a weighted graph.

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.

Fig 5: Kruskal’s Algorithm Pseudocode

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.
Fig 6: Prim’s algorithm

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 1: Start with a weighted graph.

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.

Prim’s Algorithm Pseudocode

Fig 7: Prim’s Algorithm Pseudocode

Time complexity of Prim’s Algorithm

Which is better Prim’s or Kruskal’s algorithm?

But, Kruskal is easy to implement when compared to Prim’s. So, now the question arises, when is it appropriate to use Prim’s? The answer is in case of dense graphs. In the case of dense graphs, the number of edges are high. So, creating the minimum spanning tree while focusing on vertices are better than doing it with edges as it is very difficult to tackle all the edges while it would be easy to just focus on near by edges of a particular vertice.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store