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 vv provides communication with the vertex list.

Algorithm 10: Isolated Vertex Detection
dfn=0dfn=0
k=k=first(VV)
while keolk\neq eol
   if evaluate(γ,v\gamma,v) is unvisitedunvisited
      depth=0depth=0
      i=dfni=dfn
      dfs(vv)
      if dfndfn is i+1i+1
         isolated vertex
   k=k=next(V,kV,k)

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