Minimum Spanning Tree(MST)
What is a Spanning Tree?
So, first of all, let’s go through the definition that what is a spanning tree is? the Given undirected and connected graph G=(v, e), a spanning tree of the graph G is a tree that spans G (that is, it includes every vertex of G) and is a sub graph of G (every edge in the tree related to G)
What is a Minimum Spanning Tree?
Basically cost of the spanning tree is the sum of the weight of all the edge in the tree. There can be many spanning trees. The minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.
a spanning tree has a direct application in the design of a network . It is used in algorithm approx the traveling salesman problem, multi-terminal minimum cut problem and minimum- cost weighted perfect matching. Other practical applications such as:
- Cluster Analysis
- Handwriting recognition
- 3.Image segmentation
There are two famous algorithms for finding the Minimum Spanning Tree:
- Kruskal’s Algorithm
So, Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree.The Kruskal’s algorithm follows a greedy approach as in each iteration it finds an edge that has the least weight and adds it to the growing spanning tree.
Algorithm Steps are the following:
1.Sort the graph edges with concerning their weights.
2.Starting from the first edge then adding edges to the MST from the edge with the smallest weight until the edge of the largest weight.
3.Only add edges that don’t form a cycle, edges that connect only disconnected components.
So now the question is how to check if 2 vertices are connected or not?
This problem could be done using DFS which starts from the first vertex, then check if the second vertex is visited or not. But then Dfs will make time complexity large as it has an order of O(v + e) where V is the number of vertices, E is the number of edges. So the best solution is “Disjoint Sets”: Disjoint sets are sets whose intersection is the empty set so it means that they don’t have any element in common.
Consider the following example:
Now In the Kruskal’s algorithm, at each iteration, we will select the edge with the lowest weight. So, we will start with the lowest weighted edge first i.e., the edges with weight 1. After this, we will select the second-lowest weighted edge i.e., edge with weight 2. Notice these two edges are disjointed.
The next edge will be the third-lowest weighted edge i.e., edge with weight 3, which connects the two disjoint pieces of the graph. we are not allowed to pick the edge with weight 4, which will create a cycle and we can’t have any cycles. So we will select the fifth-lowest weighted edge i.e., edge with weight 5. Now the other two edges will create cycles so we will ignore them. In the end, we end up with a minimum spanning tree with total cost 11 ( = 1 + 2 + 3 + 5).
Implementation:
Time Complexity:
In Kruskal’s algorithm, the most time-consuming operation is sorting because the total complexity of the Disjoint-Set operations will be O(ElogV), which is the overall Time Complexity of the algorithm.
Prim’s Algorithm
Prim’s Algorithm also uses the Greedy approach to find the minimum spanning tree. In Prim’s Algorithm, we grow the spanning tree from a starting position. Unlike an edge in Kruskal’s, we add a vertex to the growing spanning tree in Prim’s.
Algorithm Steps:
1. Maintain two disjoint sets of vertices. One containing vertices that are in the growing spanning tree and others that are not in the growing spanning tree.
2. Select the cheapest vertex that is connected to the growing spanning tree and is not in the growing spanning tree and add it into the growing spanning tree. This can be done using Priority Queues. Insert the vertices, that are connected to the growing spanning tree, into the Priority Queue.
3. Check for cycles. To do that, mark the nodes which have been already selected and insert only those nodes in the Priority Queue that are not marked.
Consider the example below:
In Prim’s Algorithm, we will start with an arbitrary node (it doesn’t matter which one) and mark it. In every iteration, we will mark a new vertex that will be adjacent to the one that we have already marked. Here As a greedy algorithm prim’s algorithm will select the cheapest edges and then mark the vertex. Now we will choose the edges with a weight of 1. now here In the next iteration, we have three options, edges with weight 2, 3 and 4. So now we will select the edges with a weight of 2 and mark the vertex. Now again here we have a three-option i.e, edges with weight 3, 4 and 5. But we can not choose any edges with a weight of 3 as it is creating a cycle.
Now we will select the edges with a weight of 4 and we end up with the minimum spanning tree of the total cost will be 7 (= 1 + 2 +4) at the last iteration.
Implementation:
Time Complexity of the algorithm:
The time complexity of the particular algorithm is O(( v +e)log v) because of each vertex is inserted in the priority queue only once and insertion in priority queue takes logarithmic time.
This information is contributed by:
- Vaibhav Ravindra Vairagade (54)
- Amruta D. Potdar (41)
- Ashwini S. Perewar (39)
- Nikhil D. Nayade (35)
- Sneha Y. More (33)