algorithm - 科门摔跤手的竞争 BFS

Question

在 Cormen 问题 22.2.6 中，我们遇到了摔跤手问题。它说有N个摔跤手，即N个节点和r对竞争，即边缘，我们需要将摔跤手分成好人和坏人，这样就没有两个好人是对手。

给出的解决方案是

根据需要执行尽可能多的 BFS 以访问所有顶点。将所有距离为偶数的摔跤手指定为好人，将所有距离为奇数的摔跤手指定为坏人。然后检查每个边缘以验证它是否介于好人和坏人之间。该解决方案需要 O(n + r ) 时间用于 BFS，O(n) 时间将每个摔跤手指定为好人或坏人，以及 O(r) 时间来检查边缘，即 O(n + r)整体时间。

我对解决方案有几个问题

根据需要执行尽可能多的 BFS 以访问所有顶点。-> 每次都从不同的节点开始？但是他们每次都会给我们相同的生成树吗？

BFS 无法访问的节点怎么办？

Answer 1

是的，正如@nm 已经提到的那样。您可能会得到一个G可能未连接的图表。例如考虑这个图

您有 2 个连接的组件。如果仅从您运行 BFS（或 DFS），node1您将永远不会发现node3, node4, node5. 因此，通过从每个节点执行 BFS，您将发现所有连接的组件。这也回答了您的问题，即从每个节点执行 BFS 不会产生相同的生成树。因此，复杂性是O(n + e)针对 n 个节点和 e 个边。

---

注意 - 此图可能不适合您的问题陈述，因为您提到了 N 个节点和 r 对，即任何连接组件中都没有奇数节点。此图像用于解释连接组件。