我希望能够找到一种非递归的方法来确定根节点是否为关键连接点。通过递归的方法，我们可以递归地查找根节点的非连接子节点数量。但是我没有找到一种不使用递归的方法来实现这一点。
非递归DFS求解割点问题
4
- tariq zafar
2
这个网站是用来解答编程问题的，这听起来更像是一个理论问题。 - Marco A.
我只想得到上述问题的算法。 - tariq zafar
1个回答
2
我能够编写一个我认为可能有效的算法。它如下：
我们有任意顶点的四种状态：未访问、访问中、已访问和重新访问。我们保持一个父数组和一个计数未连接子项的数组。
1. 我们从根开始不断向栈中添加顶点，但不弹出父元素。例如，我们有将根1连接到2、3、6和7，那么我们将1推入栈中，但不弹出它。相反，我们将其他子项放在其顶部。我们还为每个元素维护父项。例如，2、3、6、7的父项为1。
2. 如果某些元素处于未访问状态，则我们将堆栈上的节点标记为访问中。
3. 如果在任何节点的邻接列表遍历期间发现某个元素处于访问中状态，则仅当此元素不是其父项时，我们将其状态更改为重新访问。例如，以上所有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。
4. 现在，如果我们遇到任何元素，在其邻接列表中没有未访问的元素，则如果此元素的状态为VISITING状态（不是REVISITING），我们将其父项的子元素总数加1（初始化为0）。如果它是REVISITING状态，我们忽略将1添加到其父项的子级编号中。同时，我们弹出该元素并将其状态更改为已访问。
5. 逐步弹出元素，我们到达根的子项（连接或唯一）。我们通过第4步检查计算根节点的唯一未连接子项数。如果大于1，则根是关节点。
虽然这个算法似乎有些复杂，但它似乎有效。欢迎提出任何建议或问题。
我们有任意顶点的四种状态：未访问、访问中、已访问和重新访问。我们保持一个父数组和一个计数未连接子项的数组。
1. 我们从根开始不断向栈中添加顶点，但不弹出父元素。例如，我们有将根1连接到2、3、6和7，那么我们将1推入栈中，但不弹出它。相反，我们将其他子项放在其顶部。我们还为每个元素维护父项。例如，2、3、6、7的父项为1。
2. 如果某些元素处于未访问状态，则我们将堆栈上的节点标记为访问中。
3. 如果在任何节点的邻接列表遍历期间发现某个元素处于访问中状态，则仅当此元素不是其父项时，我们将其状态更改为重新访问。例如，以上所有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。
4. 现在，如果我们遇到任何元素，在其邻接列表中没有未访问的元素，则如果此元素的状态为VISITING状态（不是REVISITING），我们将其父项的子元素总数加1（初始化为0）。如果它是REVISITING状态，我们忽略将1添加到其父项的子级编号中。同时，我们弹出该元素并将其状态更改为已访问。
5. 逐步弹出元素，我们到达根的子项（连接或唯一）。我们通过第4步检查计算根节点的唯一未连接子项数。如果大于1，则根是关节点。
虽然这个算法似乎有些复杂，但它似乎有效。欢迎提出任何建议或问题。
- tariq zafar
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接