6.2 Isolated Vertex Detection

Isolated vertices are detected during a depth-first traversal of a graph. The detection scheme is based on the observation that an isolated vertex processed by dfs increases the depth-first number by exactly one. Algorithm 10 implements this observation in the main loop of a depth-first traversal (Algorithm 8). It assumes the buffer $v$ provides communication with the vertex list.

Algorithm 10: Isolated Vertex Detection

dfn=0

k=

first(

V

)

while

k\neq eol

if evaluate(

\gamma,v

) is

unvisited

depth=0

i=dfn

dfs(

v

)

dfn

i+1

isolated vertex

k=

next(

V,k

)

Since the isolated vertex test is an O(1) operation, it does not increase the complexity of a depth-first traversal.