什么是删除图形中不属于至少一个循环的所有边的好算法？

Question

删除图形中不属于至少一个循环的所有边的好算法是什么？基本上我想从任意图中“修剪所有的树”。

我突然想到的算法效率不高而且也不正确：

给定一个图 G，设 C 是至少一个循环中的一组边。通过图形遍历在 G 中找到一个循环，并用它的边作为种子 C。
对于不在C中但与C中的边的顶点相邻的每条边e，执行从e开始的遍历以找到路径P 终止于 C.
如果存在这样的路径P，将P的边添加到C并转到2。否则e是树的根，所以删除e 及其所有子项。

以上是低效的，但更重要的是“否则 e 是树的根”的说法是不正确的：如果两个循环都不在循环边缘集合中，则该算法将删除循环之间的桥它知道。要解决此问题，您只需在步骤 3 中删除 e，然后通过对连通分量重复整个算法来处理与集合 C 未连通的连通分量。整个方法感觉效率低下且不必要地多毛，但我还没有想到更好的方法。

Answer 1

由于 Hopcroft 和 Tarjan 寻找 articulation points.

，我们可以通过修改算法得到 linear-time 算法

首先，一点点理论：对于所有生成树 T，对于所有边 e，存在一个包含 e 的循环当且仅当存在关于包含 e 的 T 的 fundamental cycle。算法中 T 的特殊选择是 depth-first 搜索树，它只有树边和后边。

下面代码背后的 high-level 思想是，每当我们找到后边时，将包含基本循环的边标记为属于循环。天真地，这会产生一个 quadratic-time 算法，所以我们所做的是让每个递归调用 return 树边可以达到的最小深度，然后是后边，我们将其与当前顶点的深度进行比较以确定刚刚遍历的边是否有标记

在Python 3:

graph = {
    1: {2, 3},
    2: {1, 4},
    3: {1, 4},
    4: {2, 3, 5},
    5: {4, 6},
    6: {5, 7},
    7: {6, 8, 9, 13},
    8: {7},
    9: {7, 10, 11},
    10: {9, 11},
    11: {9, 10, 12},
    12: {11, 13},
    13: {7, 12, 14},
    14: {13},
}

for v, neigh in graph.items():
    for w in neigh:
        assert v in graph[w]

depths = {}


def traverse(v, depth, parent):
    if v in depths:
        return depths[v]
    depths[v] = depth
    v_low = float("inf")
    for w in graph[v]:
        if w == parent:
            continue
        w_low = traverse(w, depth + 1, v)
        if w_low <= depth:
            print(v, "--", w)
        v_low = min(v_low, w_low)
    return v_low


print("graph {")
for v in graph.keys():
    traverse(v, 0, None)
print("}")

什么是删除图形中不属于至少一个循环的所有边的好算法？

What is a good algorithm for removing all the edges of a graph that are not part of at least one cycle?

algorithm

graph-algorithm

data-structures