识别无向图中所有循环基的算法

Question

我有一个带有顶点

V

和边

E

的无向图。我正在寻找一种算法来识别该图中的所有循环基础。

我认为Tarjans算法是一个好的开始。但是我所拥有的参考是关于找到所有循环，而不是循环基础（根据定义，它是不能通过其他循环的联合构造的循环）。

例如，看一下下图：

因此，算法会很有帮助。如果有现成的实现（最好是 C#），那就更好了！

Answer 1

据我所知，Brian 的预感不仅成立，而且还有一个更强有力的命题：不在最小生成树中的每条边都恰好添加了一个新的“基环”。

为了了解这一点，让我们看看当您添加一条不在 MST 中的边 E 时会发生什么。让我们用最喜欢的数学方法来使事情复杂化并添加一些符号；）将原始图称为 G、添加 E G' 之前的图以及添加 E G'' 后的图。所以我们需要找出“基本周期计数”如何从 G' 变为 G''。

添加E必须关闭至少一个循环（否则E将首先出现在G的MST中）。显然，它必须在 G' 中已有的基础周期上添加至少一个“基周期”。但它会添加多个吗？

它不能添加超过两个，因为没有边可以是两个以上基循环的成员。但如果 E 是两个基循环的成员，那么这两个基循环的“并集”一定是 G' 中的基循环，所以我们再次得到循环数的变化仍然是 1。

因此，对于不在 MST 中的每条边，您都会获得一个新的基本周期。所以“计数”部分很简单。找到每个基循环的所有边有点棘手，但按照上面的推理，我认为这可以做到（在伪Python中）：

for v in vertices[G]:
    cycles[v] = []

for e in (edges[G] \ mst[G]):
    cycle_to_split = intersect(cycles[e.node1], cycles[e.node2])
    if cycle_to_split == None:
        # we're adding a completely new cycle
        path = find_path(e.node1, e.node2, mst[G])
        for vertex on path:
            cycles[vertex].append(path + [e]) 
        cycles
    else:
        # we're splitting an existing base cycle
        cycle1, cycle2 = split(cycle_to_split, e)
        for vertex on cycle_to_split:
            cycles[vertex].remove(cycle_to_split)
            if vertex on cycle1:
                cycles[vertex].append(cycle1)
            if vertex on cycle2:
                cycles[vertex].append(cycle2)

base_cycles = set(cycles)

编辑：代码应该找到图中的所有基本周期（底部设置的base_cycles）。假设您知道如何：

• 找到图的最小生成树（mst[G]）
• 找出两个列表之间的差异（edges \ mst[G]）
• 找到两个列表的交集
• 查找 MST 上两个顶点之间的路径
• 通过添加额外的边将循环分成两部分（分割函数）

主要是遵循上面的讨论。对于不在 MST 中的每条边，有两种情况：要么带来一个全新的基本周期，要么将现有的基本周期一分为二。为了跟踪这两种情况中的哪一种，我们跟踪顶点所属的所有基本循环（使用循环字典）。

Answer 2

我首先会考虑任何最小生成树算法（Prim、Kruskal 等）。基循环（如果我理解正确的话）不能多于不在 MST 中的边......

Answer 3

以下是我实际的未经测试的 C# 代码，用于查找所有这些“基本周期”：

public HashSet<List<EdgeT>> FindBaseCycles(ICollection<VertexT> connectedComponent)
{
   Dictionary<VertexT, HashSet<List<EdgeT>>> cycles =
       new Dictionary<VertexT, HashSet<List<EdgeT>>>();

   // For each vertex, initialize the dictionary with empty sets of lists of
   // edges
   foreach (VertexT vertex in connectedComponent)
       cycles.Add(vertex, new HashSet<List<EdgeT>>());

   HashSet<EdgeT> spanningTree = FindSpanningTree(connectedComponent);

   foreach (EdgeT edgeNotInMST in
           GetIncidentEdges(connectedComponent).Except(spanningTree)) {
       // Find one cycle to split, the HashSet resulted from the intersection
       // operation will contain just one cycle
       HashSet<List<EdgeT>> cycleToSplitSet =
           cycles[(VertexT)edgeNotInMST.StartPoint]
               .Intersect(cycles[(VertexT)edgeNotInMST.EndPoint]);

       if (cycleToSplitSet.Count == 0) {
           // Find the path between the current edge not in ST enpoints using
           // the spanning tree itself
           List<EdgeT> path =
               FindPath(
                   (VertexT)edgeNotInMST.StartPoint,
                   (VertexT)edgeNotInMST.EndPoint,
                   spanningTree);

           // The found path plus the current edge becomes a cycle
           path.Add(edgeNotInMST);

           foreach (VertexT vertexInCycle in VerticesInPathSet(path))
               cycles[vertexInCycle].Add(path);
       } else {
            // Get the cycle to split from the set produced before
            List<EdgeT> cycleToSplit = cycleToSplitSet.GetEnumerator().Current;
            List<EdgeT> cycle1 = new List<EdgeT>();
            List<EdgeT> cycle2 = new List<EdgeT>();
            SplitCycle(cycleToSplit, edgeNotInMST, cycle1, cycle2);

            // Remove the cycle that has been splitted from the vertices in the
            // same cicle and add the results from the split operation to them 
            foreach (VertexT vertex in VerticesInPathSet(cycleToSplit)) {
                cycles[vertex].Remove(cycleToSplit);
                if (VerticesInPathSet(cycle1).Contains(vertex))
                     cycles[vertex].Add(cycle1);
                     if (VerticesInPathSet(cycle2).Contains(vertex))
                         cycles[vertex].Add(cycle2); ;
            }
       }
   }
   HashSet<List<EdgeT>> ret = new HashSet<List<EdgeT>>();
   // Create the set of cycles, in each vertex should be remained only one
   // incident cycle
       foreach (HashSet<List<EdgeT>> remainingCycle in cycles.Values)
           ret.AddAll(remainingCycle);

       return ret;
}

Oggy的代码非常好且清晰，但我很确定它包含一个错误，或者是我不理解你的伪Python代码:)

cycles[v] = []

不能是边列表的顶点索引字典。在我看来，它必须是边的列表集的顶点索引字典。

并且，要添加精确度：

for vertex on cycle_to_split:

cycle-to-split 可能是一个 ordered 边列表，因此要通过顶点迭代它，您必须将其转换为一组顶点。这里的顺序可以忽略不计，所以这是一个非常简单的算法。

我再说一遍，这是“未经测试”和“不完整”的代码，但这是向前迈出的一步。它仍然需要适当的图形结构（我使用事件列表）和许多图形算法，您可以在 Cormen 等教科书中找到。我无法在教科书中找到 FindPath() 和 SplitCycle()，并且很难在图中边+顶点数量的线性时间内对它们进行编码。当我测试它们时，会在这里报告它们。 非常感谢奥吉！ 检测循环的标准方法是使用两个迭代器 - 对于每次迭代，一个迭代器向前移动一步，另外两个迭代器向前移动一步。 如果存在循环，它们会在某个时刻指向彼此。

这种方法可以扩展以记录找到的周期并继续。

Answer 4