language-agnostic - 测试总可达性的最佳方法

Question

我有一组节点，每个节点都连接到至少一个其他节点。我想知道连接是否使得每个节点都可以相互访问。例如：

1--2
   |
3--4

相对：

1--2

3--4

我相信这种可达性测试可以根据精确覆盖问题进行预测，但是我似乎无法思考如何做到这一点。有没有人有关于如何做到这一点的任何指针、文档、网站等？例子将非常有价值。

更新：我的无知出卖了我，因为这种测试似乎有更有效的算法。如果你有，请指点我。

Answer 1

• 从任意节点开始进行深度/广度优先遍历
• 计算访问节点的数量（当然，不要访问任何节点两次！）
• 将计数的数字与总数进行比较

Answer 2

还有一种快速（但相当复杂）的算法用于动态维护连通性（即在边缘插入/删除下），如本文所示：Poly-logarithmic Deterministicfully-dynamicalgorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

基本思想是维护生成树。简单的情况是插入一条边，并删除一条非生成树边。问题是在删除生成树边时，因为现在不能保证连通性 - 我们必须有效地搜索替代路线来连接损坏的部分，否则图形会断开连接。