DFS to find connected components in an undirected graph

To solve the following problem.

Statement

Find connected components in an undirected graph

Given a graph how can we find a mapping from it’s vertices to the connected components of .

Link to original

We can use the following DFS algorithm.

DFS(G)
  input: G = (V,E) in adjacency list representation
  output: Vertices labelled by connected components
    connected_component = 0
    for all v in V, set visited(v) = False
    for all v in V
      if not visited(v) then
        connected_component++
        explore(v)
    return connected_component_number (defined in explore)

Explore(z)
  input: vertex z
  output: side effect, it defines the connected component_number on some vertices and marks them as visited.
    connected_component_number(z) = connected_component
    visited(z) = True
    for all (z, w) in E
      if not visited(w)
        Explore(w)

As we run through every vertex once and then every edge twice we have .