基于栈的CLRS风格带父节点与时间戳的DFS非递归实现探讨

Cormen、Leiserson、Rivest和Stein所著的《算法导论》（CLRS）第22.3节给出了递归版深度优先搜索（DFS）实现。该实现为每个节点u添加了父节点属性u.parent，以及分别表示首次访问时间的u.d和完成处理时间的u.f时间戳，算法时间复杂度为O(|V| + |E|)。

其伪代码如下：

DFS(G)
    for each vertex u in G.V
        u.color = WHITE
        u.parent = NIL
    time = 0
    for each vertex u in G.V
        if u.color == WHITE
            DFS-VISIT(G, u)

DFS-VISIT(G, u)
    time = time + 1
    u.d = time
    u.color = GRAY
    for each v in G.Adj[u]
        if v.color == WHITE
            v.parent = u
            DFS-VISIT(G, v)
    u.color = BLACK
    time = time + 1
    u.f = time

（注：修正了原伪代码中的两处笔误：ui.color改为u.color，vertext改为vertex）

习题22.3-7要求设计一个基于栈的非递归DFS算法。我最初采用类似walkccc给出的方案，但该方案的*O(|V| + |E|)时间复杂度存在争议；其他声称达到O(|V| + |E|)*复杂度的方案，要么无法生成符合要求的深度优先树（父节点设置不符合规则），要么存在v.f时间戳设置过早的问题。

我尝试通过字典栈记录节点的下一个未访问邻居的方式，优化了walkccc的方案，使其满足时间复杂度要求，但仍希望找到更简洁的实现方案，特此探讨CLRS可能期望的解法。

内容的提问来源于stack exchange，提问作者tarski