寻找一个顶点，其移除将断开两个其他

Question

我试图做一个算法，在O（V + E）时间运行一个无向图G =（V，E），给定两个顶点a和b，找到一个顶点c，它的移除将导致a和b彼此断开连接。作为其中的一部分，我试图说如果从a到b的最短路径的长度大于V/2，那么G必须对a和b有'c'。

我可以直观地看到，看一张图，为什么从a到b的长度大于v/2时，必须有a和b的阻塞点。我想这是因为如果长度小于或等于v/2，那么a和b可能会相互连接而没有另一个顶点？

对于算法，我想过用Dijkstra算法找出a和b之间的最短路径，然后选择一个顶点沿该路径，将其取下，并检查是否路径是一样的。这是要走这条路还是有更好的方法？

Answer 1

由于是无向图的话，顶点c存在当且仅当c是brigde，这意味着，从a到b，反之亦然所有路径，都必须要经过c，

所以您不需要使用Dijkstra，只需使用简单的宽度优先搜索，然后尝试BFS找到的路径上的所有顶点，如果删除导致a和b断开连接，则它将是c。