MINIMUM SPANNING TREE
What is Spanning Tree?
A spanning tree is a subset of Graph A, which has all the vertices covered with minimum possible number of edges. If there are ’n’ number of vertices than ‘n-1’ is the number of edges connected to form spanning tree. Spanning tree should not be in the form of cycle, it should be always disconnected.
A tree has one path joins any two vertices. A spanning tree of a graph is a tree that:
· Contains all the original graph’s vertices.
· Reaches out to (spans) all vertices.
· It is acyclic. In other words, the graph doesn’t have any nodes which loop back to itself.
We can say that every connected and undirected graph A has at least one spanning tree .A complete undirected graph can have n^(n-2) number of spanning trees, where ’n’ represents number of vertices.
From the given figure , we can verify the number of spanning trees using the formula. Number of vertices in Graph A is 3, so number of spanning trees would be n^n-2=3^3–2=3.
What is Minimum Spanning Tree?
The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees.
Finding Minimum Spanning Trees
In order to find Minimum Spanning Tree, you can construct all the possible Spanning Tree and the tree having least cost will be the Minimum Spanning Tree. But this is a lengthy process so we need to apply some Greedy technique to find the MST and in order to do so, there are two algorithms or techniques that are used:
1.Kruskal’s Algorithm.
2. Prim’s Algorithm.
Kruskal’s Algorithm:
Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree. Kruskal’s algorithm follows greedy approach as in each iteration it finds an edge which has least weight and add it to the growing spanning tree.
Algorithm:
· Sort the edges of the graph based on their cost.
- Add the edge having the least cost until all vertices are connected.
- Add only those edges which are not forming any cycles.
At each iteration we will select the edge with low cost. So starting with lowest cost first that is the edges with cost 1 on it. After that we will select the second lowest cost that is edge with cost 2. Next we will choose the edge with cost 3, edge with weight 3, which connects the two disjoint pieces of the graph. Now we are not supposed to connect the edge with cost 4 as it would be a cycle. So we will connect the fifth lowest cost that is 5. Now other two edges when connected will form cycles so we have to ignore them. At last we have to calculate the Minimum Spanning Tree that is (1+2+3+5)=11.
Time complexity
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
In this type of Greedy approach, we first select the shortest edge from the given graph and after that, we will select that shortest edge which is connected to the already present nodes of the Spanning Tree that you are making.
Algorithm:
- Maintain two disjoint sets i.e. one for those edges that are present in the Spanning Tree and other set contains the edges that are not present in the Spanning Tree.
- Select the edge that is not present in the set of edges that are already present in the Spanning Tree. Also, the selected edge should be connected to any of the nodes or vertices that are present in the Spanning Tree.
- While adding edges to the Spanning Tree, always verify for cycles present in the Spanning Tree i.e. if the addition of some edge results in a cycle in the Spanning Tree, then ignore adding that edge in the Spanning Tree.
We will start with an arbitrary node and mark it. In each iteration we will mark a new vertex that is adjacent to the one that we have already marked. Now we will select the cheapest edge and mark the vertex. So we will simply choose the edge with cost 1. In the next iteration we have three options, edges with weight 2, 3 and 4. So, we will select the edge with cost 2 and mark the vertex. Now again we have three options, edges with cost 3, 4 and 5. But we can’t choose edge with cost 3 as it is creating a cycle. So we will select the edge with weight 4 and we end up with the minimum spanning tree of total cost (1+2+4)=7.
Time complexity
The time complexity of the Prim’s Algorithm is O((V+E)logV) because each vertex is inserted in the priority queue only once and insertion in priority queue take logarithmic time.
Applications of Minimum Spanning Tree
Minimum spanning trees have direct applications in the design of networks, including computer networks, telecommunication networks, transportation networks, water supply networks and electrical grids.
Other applications are:
· Taxonomy.
· Constructing trees for broadcasting in computer networks.
· Image registration and segmentation.
· Curvilinear feature extraction in computer vision.
· Handwriting recognition of mathematical expressions.
· Circuit design is implementing efficient multiple constant multiplications, as used in finite impulse response filters.
· Regionalization of socio-geographic areas, the grouping of areas into homogeneous, contiguous regions.