查找图中的所有边，如果删除这些边，将断开一对顶点
Find all edges in a graph which if removed, would disconnect a pair of vertices
我有一个无向图 G(V, E)。我试图解决的问题分为两部分：
第 1 部分：给定图和图中的一对顶点，找到包含在这对节点之间的所有路径中的边。
第 2 部分：给定图，找到所有这样的边，使得每条边都存在于图中任意两个顶点之间的所有路径上。
第 2 部分的示例：
让图有节点 {a, b, c, d, e, f, g}.
设边为：
{a, b},
{b, c},
{c, a},
{c, d},
{d, e},
{e, f}
{f, g},
{g, e}
对于这个图，{c, d} 和 {d, e} 应该是返回的边。
如何才能高效地做到这一点？
有一种算法可以找到 "bridges"，如果我们删除它，我们称桥为一条边，该图被分成两个不相交的图。您正在寻找的边缘是桥梁。
第 1 部分。现在您知道什么是桥，您只需要找到一对节点之间的路径，并且该路径中的所有顶点也是第 1 部分的解决方案。
第 2 部分。解决方案是图中的所有桥
如果一条边E在从顶点A到顶点B的路径上，但从A到B也有一条路径不包含E，则E在环中。
如果E在一个环中，并且E在一条从A到B的路径上，那么有一条从A到B通过环中其他边的路径不包括E。
因此，您在第 2 部分中寻找的边是不在循环中但也在从 A 到 B 的路径上的边。
然后回答你的问题：
1) 使用Hopcroft/Tarjan算法找出图中所有的双连通分量（圈）。参见 https://en.wikipedia.org/wiki/Biconnected_component
2) 将每个双连通分量折叠为单个顶点（更准确地说，组合由循环中的边连接的任何 2 个顶点，直到 运行 超出这些边）。这样就会创建一个tree对应的block cut tree（上面也有描述link）。包含 A 的组件将是新图中的 A，对于 B 也是如此。
3) 由于生成的图是一棵树，因此从 A 到 B 它只有 一条 路径。用 DFS 找到它。该路径上的边缘是第 2 部分的答案。
4) (3) 中的边，以及与这些边相邻的每个双连通组件中的边，是第 1 部分的答案。
是的，听起来有点像@EmmanuelAC 的回答试图指向这个方向。
我有一个无向图 G(V, E)。我试图解决的问题分为两部分：
第 1 部分：给定图和图中的一对顶点，找到包含在这对节点之间的所有路径中的边。
第 2 部分：给定图，找到所有这样的边，使得每条边都存在于图中任意两个顶点之间的所有路径上。
第 2 部分的示例：
让图有节点 {a, b, c, d, e, f, g}.
设边为：
{a, b},
{b, c},
{c, a},
{c, d},
{d, e},
{e, f}
{f, g},
{g, e}
对于这个图，{c, d} 和 {d, e} 应该是返回的边。
如何才能高效地做到这一点？
有一种算法可以找到 "bridges"，如果我们删除它，我们称桥为一条边，该图被分成两个不相交的图。您正在寻找的边缘是桥梁。
第 1 部分。现在您知道什么是桥，您只需要找到一对节点之间的路径，并且该路径中的所有顶点也是第 1 部分的解决方案。
第 2 部分。解决方案是图中的所有桥
如果一条边E在从顶点A到顶点B的路径上，但从A到B也有一条路径不包含E，则E在环中。
如果E在一个环中，并且E在一条从A到B的路径上，那么有一条从A到B通过环中其他边的路径不包括E。
因此，您在第 2 部分中寻找的边是不在循环中但也在从 A 到 B 的路径上的边。
然后回答你的问题：
1) 使用Hopcroft/Tarjan算法找出图中所有的双连通分量（圈）。参见 https://en.wikipedia.org/wiki/Biconnected_component
2) 将每个双连通分量折叠为单个顶点（更准确地说，组合由循环中的边连接的任何 2 个顶点，直到 运行 超出这些边）。这样就会创建一个tree对应的block cut tree（上面也有描述link）。包含 A 的组件将是新图中的 A，对于 B 也是如此。
3) 由于生成的图是一棵树，因此从 A 到 B 它只有 一条 路径。用 DFS 找到它。该路径上的边缘是第 2 部分的答案。
4) (3) 中的边，以及与这些边相邻的每个双连通组件中的边，是第 1 部分的答案。
是的，听起来有点像@EmmanuelAC 的回答试图指向这个方向。