Minimum Spanning Tree
Minimum Spanning Tree
Let us deduce the problem of finding minimum spanning tree from a given graph, for that we need to know how tree is different from a graph and what minimum spanning tree actually is...
So let us go by the definition, A graph is set of nodes and edges where as a tree is a set of nodes and vertices with no cycles, so the only thing in which a tree differs is on the fact that tree's does not contains cycles.
If tree does not contain cycles, then it basically means that, we need to remove the cycles to convert a graph into a tree and so if we want a minimum spanning tree then we need to remove the edges forming a cycle with larger weight , i.e we only keep the edges with minimum weight , in the graph and keep including the edges which does not form a cycle, until all the edges are considered. So this method is basically Kruskals Method for finding Minimum Spanning Tree.
Tap on the black frame below to see what Minimum Spanning Tree actually is:
So to find a minimum spanning tree , we have to follow some simple steps which are stated as follows:
1 . Sort the edges in a graph according to their weights
2. Pick edges in ascending order
3. Check if the selected edge forms a cycle if so then discard the edge else include it in minimum spanning tree.
4. Repeat step 2 & 3 for all the remaining edges.
Thats it, after following these steps what remains is minimum spanning tree , so now the only abstract thing in the description which remains is how do we check whether a cycle is formed if we include the edge.
The thing is, we solve the above problem by applying Union Find method, whose some of the good resources are :
1. Geek For Geeks ( Great for understanding how we detect cycles using Union Find Method )
2. William Fiset ( Great for understanding how union and find method works )
Even though they are explained in quite a bit detail in the above links , I will try to explain the same in this post too , but in an abstract form.
So union-find is a kind of method in which by using union method, we simply join two sets and by using find method we can find the root of the given set, its like we create small graphs or sets with a central element which can be found using find method and if we want to join two sets we can simply use the union method.
Suppose there are 5 nodes : 0 , 1 , 2 , 3 and 4. and we want to perform the operations as follows:
1. union(0,1)
2. union(2,3)
3. union(3,1)
4. union(2,4)
Initially :
0 1 2 3 4
-1 -1 -1 -1 -1
after union(0,1)
0 1 2 3 4
1 -1 -1 -1 -1
after union(2,3)
0 1 2 3 4
1 -1 -1 2 -1
after union(3,1)
0 1 2 3 4
1 3 -1 2 -1
after union(2,4)
0 1 2 3 4
1 3 -1 2 2
So after looking at the above image , we can see what's happening and how different disjoint sets are getting merged into one by the use of union function, and at each stage we can also see what actually is the output of the find function so, now using union and find we can devise a simple but effective algorithm for finding whether a given graph contains a cycle? So for that we first create an empty union structure for N nodes in the graph (like in a). After that we pick an edge as in step two of the kruskals algorithm and then we see the start and end vertices of the edge and check if the find returns different values (same is allowed only if it is -1 i.e Self loop ) which tells that they are disjoint so no cycle is formed after inclusion of the edge but if the condition is not true , then we know that after including the edge, it will add a cycle in the tree so we simply discard the edge.
If tree does not contain cycles, then it basically means that, we need to remove the cycles to convert a graph into a tree and so if we want a minimum spanning tree then we need to remove the edges forming a cycle with larger weight , i.e we only keep the edges with minimum weight , in the graph and keep including the edges which does not form a cycle, until all the edges are considered. So this method is basically Kruskals Method for finding Minimum Spanning Tree.
Tap on the black frame below to see what Minimum Spanning Tree actually is:
So to find a minimum spanning tree , we have to follow some simple steps which are stated as follows:
1 . Sort the edges in a graph according to their weights
2. Pick edges in ascending order
3. Check if the selected edge forms a cycle if so then discard the edge else include it in minimum spanning tree.
4. Repeat step 2 & 3 for all the remaining edges.
Thats it, after following these steps what remains is minimum spanning tree , so now the only abstract thing in the description which remains is how do we check whether a cycle is formed if we include the edge.
 |
The thing is, we solve the above problem by applying Union Find method, whose some of the good resources are :
1. Geek For Geeks ( Great for understanding how we detect cycles using Union Find Method )
2. William Fiset ( Great for understanding how union and find method works )
Even though they are explained in quite a bit detail in the above links , I will try to explain the same in this post too , but in an abstract form.
So union-find is a kind of method in which by using union method, we simply join two sets and by using find method we can find the root of the given set, its like we create small graphs or sets with a central element which can be found using find method and if we want to join two sets we can simply use the union method.
Suppose there are 5 nodes : 0 , 1 , 2 , 3 and 4. and we want to perform the operations as follows:
1. union(0,1)
2. union(2,3)
3. union(3,1)
4. union(2,4)
Initially :
0 1 2 3 4
-1 -1 -1 -1 -1
after union(0,1)
0 1 2 3 4
1 -1 -1 -1 -1
after union(2,3)
0 1 2 3 4
1 -1 -1 2 -1
after union(3,1)
0 1 2 3 4
1 3 -1 2 -1
after union(2,4)
0 1 2 3 4
1 3 -1 2 2
So after looking at the above image , we can see what's happening and how different disjoint sets are getting merged into one by the use of union function, and at each stage we can also see what actually is the output of the find function so, now using union and find we can devise a simple but effective algorithm for finding whether a given graph contains a cycle? So for that we first create an empty union structure for N nodes in the graph (like in a). After that we pick an edge as in step two of the kruskals algorithm and then we see the start and end vertices of the edge and check if the find returns different values (same is allowed only if it is -1 i.e Self loop ) which tells that they are disjoint so no cycle is formed after inclusion of the edge but if the condition is not true , then we know that after including the edge, it will add a cycle in the tree so we simply discard the edge.
