algorithm - 在大图中找到神经痛点2的算法

Question

假设我有一个大的任意连接顶点图，如下所示。假设这些是网络连接。一些连接（红色）比其他连接更容易损坏。如果两个红色连接失败，则许多点与剩余岛屿的成员不再连接。

怎样才能找到这些神经连接？

是否有现有的算法？

Answer 1

您想知道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) 一样糟糕，这可能令人望而却步。

Answer 2

就在我的脑海中，我想说你需要看看流网络：http ://en.wikipedia.org/wiki/Flow_network 。