6.1 Connected Components of a Graph

If CGVGC(G)\subset V(G), a similar procedure (Algorithm 9) extracts a set of components from GG whose roots are defined by CGC(G). It assumes that CGC(G) and VGV(G) are maintained in simple lists (Section 3.3 examines the list data type).

Algorithm 9: Extract the Connected Components of a Graph
k=k=first(VV)
while keolk\neq eol
   map(γ,v,unvisited\gamma,v,unvisited)
   k=k=next(V,kV,k)
dfn=0dfn=0
k=k=first(CC)
while keolk\neq eol
   if evaluate(γ,v\gamma,v) is unvisitedunvisited
      depth=0depth=0
      dfs(vv)
   k=k=next(C,kC,k)