6.1 Connected Components of a Graph

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

Algorithm 9: Extract the Connected Components of a Graph

k=

first(

V

)

while

k\neq eol

map(

\gamma,v,unvisited

)

k=

next(

V,k

)

dfn=0

k=

first(

C

)

while

k\neq eol

if evaluate(

\gamma,v

) is

unvisited

depth=0

dfs(

v

)

k=

next(

C,k

)