使用基于堆栈的 DFS 在有向图中进行循环检测

Question

以下算法在堆栈溢出异常后失败。请告诉我如何在有向图中更正它以进行循环检测，或者如果可能的话有人可以提供基于堆栈而不是递归的算法。

public boolean hasCycle(Graphnode<T> n) {

    n.setMark(IN_PROGRESS);

    for (Graphnode<T> m : n.getSuccessors()) {
        if (m.getMark() == IN_PROGRESS) {
            return true;
        }

        if (m.getMark() != DONE) {
            if (hasCycle(m)) {
                return true;
              }
        }
    }

    n.setMark(DONE);

    return false;
}

谢谢， 维克兰特

Answer 1

我已经很久没有做这种事情了，但是你的代码看起来很奇怪。 您的第一个 if 条件是：

if (m.getMark() == IN_PROGRESS) {

return true;
}

我认为应该是这样的：

if (m.getMark() == IN_DONE) {

return true;
}

如果不是，m.getMark() == IN_PROGRESS 和 m.getMark() != DONE 有什么区别？你的第二个 if 条件永远不会被触发。

注意：如果你通过 SO 你会发现许多算法使用 DFS 或堆栈...