Things to be discussed here.
That's all for this article, in the next session we will be discussing Prim's Algorithm and problems related to it and for now practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).
If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.
Thank You
With 💙 by Learn DSA
- Spanning Tree
- Minimum Spanning Tree ( MST )
- Kruskal's Algorithm
- Practice Problem
Before discussing MST, we will first take look into "Spanning Tree".
Spanning Tree
A spanning tree of a graph is a graph that consists of all nodes of the graph and some of the edges of the graph so that there exists a path between any two nodes. Spanning trees are connected and acyclic like a tree. For example, take a look at the below picture, where (a) is the original graph (b) and (c) are some of its spanning trees.
Observation:
- If we denote graph by G = (V, E ) then G' = ( V, E' ) will be spanning tree if and only if E' = V - 1 so that the graph formed be acyclic and connected. E' is a subset of E and if E=V-1 then E' = E.
- There will at least 1 spanning tree for the given graph.
Minimum Spanning Tree
Minimum spanning trees are those spanning trees whose edge weight is a minimum of all spanning trees. For example, let us suppose we a graph with 5 spanning trees having the sum of edge weights 9,9,10,11,12 then, in this case, we will get 2 MST's
- More than two MSTs are possible when all the edge weights are not distinct.
- If all the edge weights are distinct then we will get a Unique MST.
Similarly, if we take a maximum weight spanning tree then we will get Maximum Spanning Tree.
Now we will be exploring two algorithms to find MST.
- Kruskal's Algorithm
- Prim's Algorithm ( To be discussed in the next article )
Both of these are the greedy algorithms and the same algorithm can be used for finding Maximum Spanning Tree by taking maximum edge weights instead of the minimum. So let us start with Kruskal's Algorithm.
Kruskal's Algorithm
Kruskal's Algorithm implements the greedy technique to builds the spanning tree by adding edges one by one into a growing spanning tree. In each iteration, it finds an edge that has the least weight and adds it to the growing spanning tree.
Algorithm Steps:
- Store the graph as an edge list.
- Sort the graph edges with respect to their weights.
- Start adding edges to the MST from the edge with the smallest weight until the edge of the largest weight.
- Only add those edge which doesn't form a cycle, i.e. edges which connect only disconnected components.
Okay, now the question arises that how we will check if the 2 vertices are connected or not? The simple answer would be to traverse the graph and check whether the we can reach from the first node to the second node using DFS.
- But this will increase the time complexity as for every edge we traverse the whole graph.
- For one traversal DFS cost is O( V + E ).
- So the total cost would be O( E*( V + E ) ).
Okay, cool. we will not be using this algorithm for checking cycle as it takes lots of time, which we don't have. The best solution to check the presence of the cycle is to use "Disjoint Sets".
Disjoint Sets ( Union Find ): Disjoint sets are sets whose intersection is the empty set so it means that they don't have any element in common.
- Using Disjoint Sets in Kruskal's algorithm we get a time complexity of O ( ElogV )
Please go through below explanatory video from Youtube to understand Disjoint Sets and it's an application in Kruskal's Algorithm.
What are Disjoint Sets?
Using Disjoint Sets in Kruskal's Algorithm
Implementation in C++
Applications:
- In electronic circuit design to minimize the wire length.
- To find routing path in networks
- Airplane network routes.
- Network Design etc.
Practice Problem
That's all for this article, in the next session we will be discussing Prim's Algorithm and problems related to it and for now practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).
If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.
Thank You
With 💙 by Learn DSA