algorithm - 在大图中找到神经性Point2的算法

假设我有一个连接顶点的大型任意图，如下所示。假设这些是网络连接。一些连接（红色）比其他连接更容易损坏如果两个红色连接失败，则许多点不再与其余岛屿的成员连接。
怎样才能找到这些神经痛的联系？
有一个现有的算法吗？

最佳答案

你想知道Edge Connectivity在您的例子中，您似乎只关心图是2边连接的，对于这种情况可能有特定的算法，但我不确定。下面是一个简单的算法，我认为它应该有效：

For all edges, E, in your graph, G:
  Remove E from G.
  Find any path, P, from src(E) to dst(E).
  Remove all edges in P from G.
  Find a path from src(E) to dst(E),
    if none exists then E is one of your important edges.

这不是很快，但是，它需要O（E*（E+V）），如果你的图是平面的，那么这也不是太糟，因为O（E）==O（V），所以它需要时间O（V^2）如果你的图有更多的连接，那么这可能和O（V^4）一样糟糕，这可能是禁止的。

关于algorithm - 在大图中找到神经性Point2的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11654120/