# 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.

$dfn=0$ |

$k=$first($V$) |

while $k\neq eol$ |

if evaluate($\gamma,v$) is $unvisited$ |

$depth=0$ |

$i=dfn$ |

dfs($v$) |

if $dfn$ is $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.