Find connected components in a graph [closed]

by

Use depth-first search (DFS) to mark all individual connected components as visited:

dfs(node u)
  for each node v connected to u :
    if v is not visited :
      visited[v] = true
      dfs(v)


for each node u:
  if u is not visited :
    visited[u] = true
    connected_component += 1
    dfs(u)

The best way is to use this straightforward method which is linear time O(n).
Since you asked about the union-find algorithm:

for each node parent[node] = node  

for each node u :
   for each node v connected to u :  
       if findset(u)!=findset(v) :
           union(u,v)  

**I assume you know about how findset and union works **  
for each node if (parent[node] == node)  
    connected_component += 1

More Related Contents:

  1. Cycles in an Undirected Graph
  2. Millions of 3D points: How to find the 10 of them closest to a given point?
  3. Graph auto-layout algorithm
  4. Finding all the shortest paths between two nodes in unweighted undirected graph
  5. Algorithm for “nice” grid line intervals on a graph
  6. How to implement depth first search for graph with a non-recursive approach
  7. Longest acyclic path in a directed unweighted graph
  8. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  9. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  10. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  11. Enumerating all paths in a directed acyclic graph
  12. How does Dijkstra’s Algorithm and A-Star compare?
  13. Find cycle of shortest length in a directed graph with positive weights
  14. graph – Dijkstra for The Single-Source Longest Path
  15. Planar Graph Layouts
  16. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  17. Bridges in a connected graph
  18. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  19. Finding connected components of adjacency matrix graph
  20. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  21. Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)
  22. Find a pair of elements from an array whose sum equals a given number
  23. How do you calculate the average of a set of circular data? [closed]
  24. Algorithm to check similarity of colors
  25. Finding maximum for every window of size k in an array
  26. Generate all unique substrings for given string
  27. How to check if line segment intersects a rectangle?
  28. How to compare two shapes?
  29. Fastest primality test
  30. Sort Four Points in Clockwise Order

Leave a Comment