证明:使用单个位来存放每个节点的颜色已经足够,这一点可以通过证明如下事实来得到:如果将DFS-VISIT的第2行删除,DFS给出的结果相同。
DFS(G){
for u in G.V
u.color = white
u.p = NIL
time = 0
for u in G.V
if u == white
DFS-VISIt(G,u)
}
DFS-VISIT(G,u){
time ++
u.d = time
u.color = gray
for v in G.Adj[u]
if v.color == white
v.p = u
DFS-VISIT(G,v)
u.color = black
time ++
u.f = time
} 