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 provides communication with the vertex list.
first() |
while |
if evaluate() is |
dfs() |
if is |
isolated vertex |
next() |
Since the isolated vertex test is an O(1) operation, it does not increase the complexity of a depth-first traversal.