在大图中查找神经痛点 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) 一样糟糕，这可能会让人望而却步。