algorithm - 迭代 DFS 中的边缘分类

Question

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

我们是否也可以使用算法的迭代版本对边缘进行分类(参见Depth-First Search)？

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)

此版本仅使用两个类别，未访问的和已发现的。在所有相邻节点都被插入堆栈后，我们可以将节点标记为完成，但它不会给出预期的结果。

编辑(澄清):问题是，我们是否可以修改上面给出的 DFS 迭代版本，以便将边分类为树/前向边、交叉边和后向边，就像通常对递归版本所做的那样节点标签/颜色的优点？

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

使用bracketing的想法，众所周知:

• 如果一条边通向未被发现的顶点，则该边是树边。

• 如果一条边通向已发现且未完成的顶点，则该边是向后边

• 边缘是交叉边缘或前向边缘。

所以现在唯一的问题是让它迭代。唯一的区别是我们现在需要操纵递归之前为我们所做的事情。假设每个顶点的 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