Introduction
A spanning tree is a subgraph of a graph that is a tree. By tree, we mean if N denotes the number of vertices in a graph then the number of edges in the spanning tree is equal to N - 1. A graph can have more than one minimum spanning tree. A minimum spanning tree for a weighted graph is the one that contains edges in such a way that the sum of edges comes out to be as minimum as possible.
There are majorly two algorithms used to determine the minimum spanning tree of a graph. These algorithms are described below in detail:
Prim’s algorithm
Prim’s algorithm is a greedy algorithm that is used to determine the minimum spanning tree (MST). This algorithm begins with an empty spanning tree. One set contains the vertices which are not part of the minimum spanning tree yet and the other set contains the vertices which are already part of the minimum spanning tree.
In each step, the edges that connect two sets are selected, and such an edge is selected out of these edges that has the minimum weight. After choosing the ideal edge, the edge is completely shifted to the MST set.
Implementation
Below is the step by step process to implement Prim’s algorithm:
1. Make a set and let’s call it mst. This keeps the record of the vertices already included in MST.
2. Now for all the vertices in the graph assign a key value. Mark all the key values as INFINITE.
3. For the first vertex to be picked, assign the key value as 0.
4. In the mst set do the following operations:
- Select a vertex V which is not a part of the MST set and has the minimum key value.
- Include this vertex V in the MST.
- Now update the key value for all the direct neighbor vertices
5. At the end you will get the minimum spanning tree of the graph.
Kruskal’s algorithm for MST
Like Prim’s algorithm, Kruskal algorithm is also a greedy algorithm. Kruskal's algorithm is based upon sorting.
Implementation
Below is the step by step process for the kruskal’s algorithm:
1. The very first step is to sort the edges of the graph in ascending order of the weight.
2. Now select the smallest edge. Check whether there exists a cycle by including the current edge in the minimum spanning tree. If including this edge in the spanning tree doesn’t create any cycle then include this edge otherwise discard this edge.
3. Keep traversing the edges in the sorted order and repeat step 2.
4. At the end you will get the minimum spanning tree of the given graph.
Both Prim’s and Kruskal algorithms are used to determine the minimum spanning tree of a graph, yet both differ from each other on certain points. Some of the major differences between them are discussed below:
Differences
Conclusion
In this article, we discussed Prim’s and Kruskal’s algorithms. Although both are greedy algorithms, they have many key differences between them. We believe that you must have enjoyed this tutorial.