迭代DFS中的边缘分类

Question

使用递归的DFS将节点标记为未访问、已发现或已完成（或白、灰、黑），可以根据三类（后边缘、树/前边缘、交叉边缘）对边缘进行分类。

我们是否也可以使用算法的迭代版本（参照深度优先搜索）对边缘进行分类？

procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do
9                  S.push(w)

Answer 1

假设您在递归版本中工作。则可修改如下：

DFS(G,v):
    v.discovered = True
    for all edges from v to w in G.adjacentEdges(v) do
    if not w.discovered then
        recursively call DFS(G,w)
    v.finished = True

使用括号的思想，众所周知：

>

如果一条边通向一个未被发现的顶点，那么它就是一条树边。

所以现在唯一的问题就是让它迭代。唯一的区别是，我们现在需要操作以前递归为我们做的事情。假设每个顶点的numactivechildren设置为0，而parent设置为nil。迭代版本如下所示：

DFS-iterative(G,v):
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if not v.discovered do
            v.discovered = True
            for all edges from v to w in G.adjacentEdges(v) do
                if w.discovered do
                    w.parent.numActiveChildren = w.parent.numActiveChildren - 1
                v.numActiveChildren = v.numActiveChildren + 1
                w.parent = v
                S.push(w)

            while v != Nil and v.numActiveChildren = 0 do
                v.finished = True
                v = v.parent
                if v != Nil do
                    v.numActiveChildren = v.numActiveChildren - 1