我编码的霍顿算法不适用

Question

我试着对Horton算法进行编码，得到一个无权无向2连通图的最小循环基。 然而，基通常覆盖图的所有边。 我想这个程序可以正确地使霍顿设定。 那么如何修复我的代码才能正常工作呢？你知道吗

for v in G.nodes():
    T = BFS_Tree(G,v)
    for x,y in G.edges():
        path_vtox = nx.shortest_path(T,source=v,target=x)
        path_vtoy = nx.shortest_path(T,source=v,target=y)
        if set(path_vtox) & set(path_vtoy) == {v}:
            cycel = []
            for i in range(len(path_vtox)-1):
                cycle.append(path_vtox[i],path_vtox[i+1])
            for i in range(len(path_vtoy)-1):
                cycle.append(path_vtoy[i],path_vtoy[i+1])
            cycle.append((x,y))
            g = nx.Graph()
            g.add_edges_from(cycle)
            try:
                nx.find_cycle(g)
                Cycles.append(cycle)
            except:
                pass

Answer 1

谢谢你发帖提问。你知道吗

首先，就如何提问和代码发表一些评论： 你应该写一个独立的例子。这包括工作代码、玩具问题和预期输出。在你的情况下，我漏掉了一行 import networkx as nx在顶部。另外，您在第2行和第17行引用了类BFS_Tree和Cycles，之前没有定义它们。 有个拼写错误。第7行应该是cycle，而不是cycel。 最重要的是，我希望有一个简短的工作示例，说明如何定义图G，以及您希望作为代码输出的内容。你知道吗

现在，我将试着说一些关于算法的东西，尽管我可能遗漏了一些概念。 霍顿设定了最短长度的循环基准吗？ 一般来说，假设所有边都是某个循环的一部分，当基可以覆盖图的所有边时，我看不出有什么问题。或者你的意思是基元素覆盖了图的所有边，但是应该更短？ 我找不到对Horton算法的唯一引用，我假设您是在the original paper的p.360中实现它的。在本参考文献中，Horton将算法描述为：

1）在每对点x，y之间找到最小路径p（x，y）

2）对于图中的每个顶点v和边{x，y}，创建循环C（v，x，y）=p（v，x）+p（v，y）+{x，y}，并计算其长度。退化情形中，P（v，x）和P（v，y）具有除v以外的公共顶点可以省略。你知道吗

3）按重量排序

4）使用贪心算法从这组循环中寻找最小循环基

在您的代码中，我只看到实现了步骤1）和2）。3） 对于未加权的情况来说是微不足道的，因为每个循环都由其长度加权。但似乎缺少了第四步。霍顿在参考文献第362页提出了一个解决方案。你知道吗

我希望这有帮助。你知道吗