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

Algorithm 10: Isolated Vertex Detection
d f n = 0 dfn=0
k = k= first( V V )
while  k e o l k\neq eol
   if evaluate( γ , v \gamma,v ) is u n v i s i t e d unvisited
       d e p t h = 0 depth=0
       i = d f n i=dfn
      dfs( v v )
      if  d f n dfn  is  i + 1 i+1
         isolated vertex
    k = k= next( V , k V,k )

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