Graph Theory Problem Solving - Session 10 ( Introduction to Minimum Spanning Tree and Kruskal's Algorithm )

Things to be discussed here.
  • 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 CODELABS3277

Comments

  1. Can you please tell me how is your implementation of union function correct instead of following the rank method.

    ReplyDelete
  2. I mean is there any proof of this because everywhere I have seen the rank of a subtree method but your method looks hella easy

    ReplyDelete
    Replies
    1. Yes, there is a proof that this greedy algorithm selects optimal edges. Can you explain me the difference between union find and union find using rank.

      Delete
    2. According to what I know is that in rank we try to optimize the joining of the different component depending on the height of components so that query could be made faster.

      Delete
    3. Yeah thanks
      I got your point
      But just a suggestion please tell us that there are better methods than this in your upcoming posts
      Like in this there was this rank method.
      If you could just mention better methods ,it would be great.
      Appreciate your work

      Delete

Post a Comment