algorithm - 单连通图中的特例

Question

我正在尝试编写一种算法来确定给定图是否单连通。作业定义说单连通图是指两个节点之间至多有一条简单路径。

我在这里看到很多回答说对每个节点使用DFS-visit，如果有一个黑色节点被访问过，这意味着有两条简单的路径。因此，给定的图不是简单连接的。

我重写了 DFS 算法来实现它，但问题是它可以解决所有给定的图，除了一种特殊情况。我已经考虑过两个节点之间有多个边缘的情况，但它不起作用。

所以我的问题是，是否有任何特殊情况无法通过对每个节点使用 DFS-visit 来解决？

def dsf(self, source):
    source.color = 'g'
    for node in source.next:
        if node.color == 'w':
            if not self.dsf(node):
                return False
        elif node.color == 'b':
            return False
    source.color = 'b'
    return True

如果dsf遇到黑色节点，则返回False并终止函数。

def singly(self):
    for node in self.nodes:
        if not self.dsf(node):
            return False
        self.__clear()
    return True

然后使用此函数检查图中的每个节点。 Self.__clear 可以将所有节点的颜色重置为白色。

除一种特殊情况外，该算法适用于所有情况。

Answer 1

有没有特殊情况不能通过对每个节点使用DFS-visit来解决？

不行，dfs必须完美解决你的问题。

继续尝试查找错误。这code可能会帮助你。它计算无向图中的所有连通分量。