DB Johnson 的“基本电路”算法是否应该产生不同的结果？

Question

开始在有向图中描述不同的基本电路（简单循环）：如果没有顶点但第一个和最后一个出现两次，则电路是基本的。如果一个不是另一个的循环置换，则两个基本电路是不同的。G中有c个不同的基本电路我试图拼凑出一些类似于伪代码的东西，有点严重欺骗了networkx和这个Java 实现。我显然没有得到不同的基本电路。这是我的代码。它使用goraph 库，但除了获得强连接组件之外，并没有真正用它做太多事情。package mainimport (    "fmt"    "github.com/gyuho/goraph/algorithm/scc/tarjan"    "github.com/gyuho/goraph/graph/gs")func main() {    gr := gs.NewGraph()    a := gr.CreateAndAddToGraph("A")    b := gr.CreateAndAddToGraph("B")    c := gr.CreateAndAddToGraph("C")    d := gr.CreateAndAddToGraph("D")    e := gr.CreateAndAddToGraph("E")    f := gr.CreateAndAddToGraph("F")    gr.Connect(a, b, 1)    gr.Connect(b, c, 1)    gr.Connect(c, a, 1)    gr.Connect(d, e, 1)    gr.Connect(e, f, 1)    gr.Connect(f, d, 1)    sccs := tarjan.SCC(gr) // returns [][]string    for _, scc := range sccs {        if len(scc) < 3 {            continue        }        for _, v := range scc {            n := node(v)            circuit(n, n, gr)        }    }    fmt.Println(result)}type node stringvar blocked = make(map[node]bool)var B = make(map[node][]node)var path []nodevar result [][]nodefunc circuit(thisNode node, startNode node, g *gs.Graph) bool {    closed := false    path = append(path, thisNode)    blocked[thisNode] = true    adj := g.FindVertexByID(string(thisNode)).GetOutVertices().GetElements()    for _, next := range adj {        nextNode := node(next.(*gs.Vertex).ID)        if nextNode == startNode {            cycle := []node{}            cycle = append(cycle, path...)            cycle = append(cycle, startNode)            result = append(result, cycle)            closed = true        } else if !blocked[nextNode] {            if circuit(nextNode, startNode, g) {                closed = true            }        }    }这是输出：[[C A B C] [B C A B] [A B C A] [F D E F] [E F D E] [D E F D]]图论对我来说是一个充满魔力的幽灵般的黑暗森林，所以我不确定我错过了什么。我误读了报纸吗？是否暗示应该以其他方式过滤掉多余的排列？我搞砸了代码吗？

Answer 1

多余的排列被过滤掉，因为每个返回排列的起始节点总是小于所有剩余元素（在某种排序下）。

我怀疑问题在于缺少这些步骤的实现：

AK:=由{s,s+1,n}诱导的G子图中顶点最少的强分量K的邻接结构；

和

s := V 中的最小顶点；

这些步骤应该确保每个排列的开始总是小于排列的其余部分，但我看不到实现这一点的代码，相反，您似乎遍历了强连接组件中的每个节点。