小编Bzb*_*Bzb的帖子

我想在加权有向图上找到最小生成树(MST).我一直在尝试使用Chu-Liu/Edmond的算法,我已经用Python实现了这个算法(下面的代码).可以在此处找到对算法的简单,清晰的描述.我有两个问题.

1. Edmond的算法是否可以保证收敛于解决方案？

   我担心删除一个循环会增加另一个循环.如果发生这种情况,算法将继续尝试永久删除循环.

   我似乎找到了这种情况的例子.输入图如下所示(在代码中).该算法永远不会完成,因为它在周期[1,2]和[1,3]以及[5,4]和[5,6]之间切换.添加到图中以解决循环[5,4]的边创建了循环[5,6],反之亦然,对于[1,2]和[1,3]也类似.

   我应该注意到,我不确定我的实施是否正确.

2. 为了解决这个问题,我介绍了一个临时补丁.当删除边以移除循环时,我会从我们正在搜索MST的基础图G中永久删除该边.因此,不能再添加该边缘,这应该可以防止算法卡住.有了这个改变,我保证找到一个MST吗？

   我怀疑人们可以找到一个病态的案例,这一步将导致一个不是MST的结果,但我无法想到一个.它似乎适用于我尝试过的所有简单测试用例.

码:

import sys

# --------------------------------------------------------------------------------- #

def _reverse(graph):
    r = {}
    for src in graph:
        for (dst,c) in graph[src].items():
            if dst in r:
                r[dst][src] = c
            else:
                r[dst] = { src : c }
    return r

# Finds all cycles in graph using Tarjan's algorithm
def strongly_connected_components(graph):
    """
    Tarjan's Algorithm (named for its discoverer, Robert Tarjan) is a graph theory algorithm
    for finding the strongly connected components …