Maintain white, gray and black colors for undiscovered, active and completed vertices. A single traversal clock records DFS discovery and finishing times:
for v in V: color[v] = white; parent[v] = none
time = 0
visit(u):
time = time+1; d[u] = time; color[u] = gray
for v in adjacency[u]:
if color[v] == white:
parent[v] = u
visit(v)
color[u] = black; time = time+1; f[u] = time
for u in V:
if color[u] == white: visit(u)The outer loop makes a depth-first search forest even when the directed graph is disconnected. Each vertex is entered once and each directed adjacency entry is inspected once. Thus an adjacency list representation gives time and auxiliary storage, including the worst-case recursive stack. Sorting neighbors to impose a particular visit order would be additional work.
Articles by others on the same topic
There are currently no matching articles.