测试总可达性的最佳方法

Question

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

1--2
   |
3--4

相对：

1--2

3--4

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

更新： 我的无知背叛了我，因为对于这种测试来说似乎有更有效的算法。如果你有的话，请指点我。

Answer 1

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

Answer 2

还有一种快速（但相当复杂）的算法用于动态维护连接（即在边缘插入/删除下），如本文所示： 用于连通性、最小生成树、2边和双连通性的多对数确定性全动态算法

基本思想是维护生成树。简单的情况是插入边和删除非生成树边。问题是在删除生成树边缘时，因为现在无法保证连接性 - 我们必须有效地搜索替代路径来连接损坏的部分，否则图将断开连接。