问在大型图中寻找神经痛point2的算法

EN

您对Edge Connectivity感到疑惑。在你的例子中，你似乎只关心图的两条边是连通的，对于这种情况可能有特定的算法，但我不确定。下面是一个我认为应该有效的简单算法：

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

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