graph - 通过非递归 DFS 的连接点

Question

我想找到某种方法来通过非递归方法找到 root 是否是一个连接点。通过递归方法，我们可以递归地找到根的非连接子节点的数量。但是我没有找到没有递归的方法。

Answer 1

我能够编写一种我认为可能有效的算法。它是这样的:

我们有任何顶点的四种状态。未访问，访问，访问，重新访问。我们保留了一个爸爸数组和一个保存未连接 child 数量的数组。

我们继续从根开始向堆栈添加顶点，但我们不弹出父元素。例如，我们将根 1 连接到 2、3、6、7，然后我们将 1 压入堆栈但不弹出它。相反，我们将其他 child 推到了上面。而且我们为每个元素维护爸爸。例如，2,3,6,7 有 1 作为他们的父亲。

如果它们未被访问，我们将堆栈上的节点标记为访问。

如果在任何节点邻接列表的遍历过程中我们发现某个元素处于访问状态，我们将其状态设为 REVISITING，但前提是该元素不是它的父亲。例如，首先，2、3、6、7 都处于访问状态。现在如果 7 的邻接表是 1, 3, 5, 10, 8, 12 那么因为 1 是它的父亲所以我们不改变 1 的状态。我们去 3 并看到它的状态为 VISITING 而它不是 7 的父亲，我们做其状态为 REVISITING。现在堆栈从下到上依次为 1, 2, 3, 6, 7, 5, 10, 8, 12。

现在，如果我们遇到任何在其邻接列表中没有 UNVISITED 元素的元素，如果该元素的状态是 VISITING 状态(不是 REVISITING)，我们将其父亲的 child 的总数加 1(初始化为 0)。如果它处于 REVISITING 状态，我们将忽略在其父亲的 child 编号上加 1。此外，我们将该元素从堆栈中弹出并使其状态为 VISITED。

逐渐弹出元素，我们到达 root 的 child (连接的或唯一的)。我们通过第 4 步检查以计算根的唯一未连接子节点的数量。如果它大于 1，则 root 是一个关节点。

这个算法看起来有点复杂，但似乎有效。欢迎任何建议或问题。