Minimum Spanning Tree — Prim’s and Kruskal’s algorithm

Think about a scenario where a telecommunications company laying cable in your neighborhood, which is a pretty newly constructed one. If it is constrained to bury the cable only along certain paths (for example say along roads), then there would be a graph representing where points are connected by those paths. Some of those paths might be expensive because they are longer or buried deeper, these obstacles can represent the weights on the graph. So, what can be done over here to come with an effective solution?

Well, a spanning tree for that graph would be a subset of those paths that has no cycles but still connects to every house, there might be several spanning trees possible. A minimum spanning tree would be one with the minimum total cost, thus would represent the least expensive path for laying the cable. There arise questions on the topic for today, what is a spanning tree? How could one be generated? So without further ado, let’s jump into the actual topic at hand.

What is a spanning tree?

What is a spanning tree? The spanning tree of a graph is a subgraph that forms a tree and contains (or spans) all vertices of the graph. So, if the given graph G has n vertices, we’re looking for a subgraph of G which

1. has n vertices
2. has n - 1 edge
3. is connected

Note

The graph itself must be connected to obtain its spanning tree.

What is a minimum spanning tree?

Given a graph, you can find it has,

|E|C|V|- 1 - cycles

where E is the number of edges, V number of vertices and C is the combination.

So, given a weighted graph, the cost of the spanning tree is the sum of the weights of all the edges in the tree. The minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There can also be many minimum spanning trees but the cost of those spanning trees remains the same.

Prims’s Algorithm

Prim’s algorithm is a greedy algorithm used in solving for the MST for a given weighted graph. The idea of the algorithm is pretty simple, start with an arbitrary vertex and greedily grow the tree by adding the minimum possible weighted edge from the tree to another vertex which is adjacent to any of the vertex in the tree, until we end up with V - 1 edge (as we know at this point, an MST contains V vertices and V - 1 edge).

Algorithm

1. Initialize the minimum spanning tree with a vertex chosen at random.
2. Find all the edges that connect the tree to new adjacent vertices, find the minimum among them and add it to the tree.
3. Repeat step 2 until we get a minimum spanning tree.

Pseudo Code

Code

Okay now let’s implement the code for the algorithm by taking the below-weighted graph as an example. I will be using an adjacency matrix representation over here.

Kruskal’s Algorithm

Once again, Kruskal’s algorithm is also a greedy algorithm used to solve for MSTs. The goal of both Prim’s and Kruskal’s algorithms is the same, and the strategy is also the same, a greedy approach. But they differ in the strategy to solve the problem.

In Kruskal’s algorithm, we build spanning-tree greedily by adding edges one by one into the growing spanning tree, while doing so we check for cycle formation because here we’re not worried about picking the vertex adjacent to any of the vertex present in the tree.

Note

That may lead you to another peculiar point what about if the graph is disconnected, yeah Kruskal's algorithm does work on it as we’re not worried about adjacent vertices but we will end up a forest (disconnected components). We’ll discuss the differences between Prim’s and Kruskal’s algorithms after looking into Kruskal’s algorithm.

Algorithm

1. Sort all the edges in the ascending order of weight.
2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then remove the edge.
3. Keep adding edges until we reach all vertices i.e., get a minimum spanning tree.

Pseudo Code

Code

Okay now let’s implement the code for the algorithm by taking the below-weighted graph as an example. I will be using an adjacency list representation over here.

At the end of the day, both algorithms may produce different minimum spanning trees but the weight of the minimum spanning tree remains the same. Here is the output for both of the codes discussed today:

Note

I will be using the terms - dense and sparse graph in the upcoming section. So, I wanted to clarify or give an idea on, what is the difference between them. A dense graph is a graph in which the number of edges is close to the maximal number of edges. Whereas, a sparse graph is a graph in which the number of edges is close to the minimal number of edges. A sparse graph can be a disconnected graph. Still confused take a look at the pictures given below:

examples of sparse and dense graph

Differences between Prim’s and Kruskal’s algorithm

1. As we discussed early on, Prim’s algorithm can only generate a connected graph component thus it works only on a connected graph. Whereas Kruskal’s algorithm can generate forest ( disconnected components), it can work on disconnected graphs.
2. When to use Prim’s and when to use Kruskal’s? Due to each algorithm's nature, we can say that Prim’s algorithm runs faster in dense graphs whereas Kruskal’s algorithm runs faster in a sparse graph. Why is it so? Prim’s algorithm runs better in a dense graph as it only compares a limited number of edges per loop, whereas Kruskal’s algorithm starts by sorting all edges in the list when going through them again to check if the edge is part of MST or not. While both algorithms have similar running times, the number of edges in the graph should be the main component when you are deciding between the algorithms. More edges compared to vertices, use Prim’s otherwise go with Kruskal’s.

So, where to go from here?

Borůvka’s algorithm is another greedy algorithm used for finding the minimum spanning tree in a graph, or a minimum spanning forest in the case of a disconnected graph.

You can explore applications of minimum spanning tree-like 1) network design, 2) approximation algorithms for NP-hard problems, 3) Cluster analysis, etc.,

References

1. https://www.youtube.com/watch?v=4ZlRH0eK-qQ
2. https://d3gt.com/unit.html?spanning-tree
3. https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/
4. https://stackoverflow.com/questions/53475447/understanding-when-to-use-prim-or-kruskal-for-minimum-spanning-tree
5. https://www.geeksforgeeks.org/difference-between-prims-and-kruskals-algorithm-for-mst/
6. https://en.wikipedia.org/wiki/Prim%27s_algorithm
7. https://personal.utdallas.edu/~besp/teaching/mst-applications.pdf
8. http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/prim2.html

My Github Repository

1. https://github.com/Sethuram52001/DSA