Graph Connectivity Testing

excerpt: The BFS and DFS lead to graph connectivity testing with only minor modifications. tags: graph-connectivity

The [BFS]({% post_url 2021-04-21-breadth-first-traversal %}) and [DFS]({% post_url 2021-04-20-depth-first-traversal %}) traversal visits all the nodes that are reachable from the start node. For an undirected graph, that means it visits every node in the graph if the graph is connected.

Connectivity

The algorithm to determine whether an undirected graph is connected:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def connected?(node)
  # Traverse the graph starting from the given node
  traverse(node)
  
  # Check if any node has not been visited
  for node in nodes
    if !visited[node]
      return false
    end
  end
  
  return true
end

The connected? method uses the traverse method discussed in an earlier article and then checks if there are any node that has not been visited. This method can be extended to find all the connected components in a graph. Simply use the traversal method repeatedly until all the nodes are visited.