假设我们有一个 n 节点、m 边的无向图 G = (V; E) 并且我们有两个不同的节点 称为 s 和 t。假设 s 和 t 之间的距离严格大于 n/2 .表明那里 是不同于 s 和 t 的节点 v，因此从 s 到 t 的每条路径都经过 v。 给出一个运行时间为 O(n + m) 的算法来找到这样一个顶点。你不必 证明你的算法是正确的，但你必须证明存在像 v 这样的顶点。
我想不出这个过去的论文问题的确切答案，帮帮我!
最佳答案
假设在 s 和 t 之间有两条路径，它们不共享一个节点。由于 s 和 t 之间的距离 > n/2，因此每条路径在 s 和 t 之间有 >= n/2 个节点。这意味着图有 >= n+2 个节点，这是矛盾的。
对于算法来说，找到任何路径就足够了，而不是在不使用路径节点的情况下查看连接到一侧的子图在哪里完成。更多详情:
- 如果 s 只连接到一个节点而不是我们正在寻找的那个节点。
- 如果不是，从s做BFS
- 找到路径s-t
- 在不使用从路径 s-t 的节点出发的边的情况下找到连接到 s 的节点
- 路径s-t上最后一个处于连通部分的节点就是我们要找的节点。
关于algorithm - 无向图算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19173736/