Monday 10 July 2017

Finding connected Components using DFS in C++


Contents :
  1. Pre-requisites
  2. Understanding connected components.
  3. Implementing DFS to find number of connected components.

  1. Pre-requisites : Depth First Search
  2. Understanding connected components :
    Here we can see a graph G , consisting of 7 nodes and 5 edges.
    We can reach to any of the nodes in set {2, 3, 4} from node 1 as these nodes are connected directly or indirectly to each other. So {1, 2, 3, 4} make one connected component we can reach from any one node to any other node in this set. Similarly {5, 6} and {7} make other connected components of this graph G.
    Implementation Idea :
    connectedComponents = 0
    for node from 1 to n:
       if node is not visited :
          dfs(node)
          connectedComponents++
    We check every node from 1 to n and if that node is not visited earlier then mark all the nodes as visited which are connected to it(either directly or indirectly) using depth first search, so that when we come to that node in our for loop we can skip it. Keep incrementing the connectedComponent variable.
  3. Implementing DFS to find number of connected components: Thank you for reading this post.
    The End !

No comments:

Post a Comment

Featured Posts

Euler Totient Function

Hello Coders, I am writing this blogpost after a very long time. I am really sorry for that. :( This blogpost is related to a mathemat...