python - python中的Kruskels MST算法似乎不太正确

Question

我正在用 Python 实现 Kruskel 算法。但它没有给出密集图的正确答案。逻辑有问题吗？？我使用的算法是这样的:

1) 将所有顶点存储在visited

中

2)根据权重对所有边进行排序

3) 继续选取最小的边，直到所有顶点 v 都访问过[v]=1

这是我尝试过的:

def Kruskal(weighted_graph):
    visited = {}
    for u,v,_ in weighted_graph:
        visited[u] = 0
        visited[v] = 0

    sorted_edges = deque(sorted(weighted_graph, key = lambda x:x[2]))
    mstlist = []
    sumi=0
    while 0 in visited.values():
        u,v,w = sorted_edges.popleft()
        if visited[u] == 0  or visited[v] == 0:
            mstlist.append((u,v))
            visited[u] = 1
            visited[v] = 1
            sumi += w
    return (sumi,mstlist)

输入是元组列表..单个元组看起来像这样(源，邻居，权重)我正在计算的最小生成树总和对于密集图来说是错误的。请帮忙。谢谢!

Answer 1

您添加边的条件是ifvisited[u]==0或visited[v]==0，因此您要求相邻节点之一没有连接到您的任何边到目前为止已添加到您的 MST。然而，为了使算法正常工作，有时即使您已经“访问”了两个节点，也有必要添加边。考虑这个非常简单的图表:

[
    (A, B, 2),
    (B, C, 3),
    (C, D, 1),
]

visual representation:
[A]---(2)---[B]---(3)---[C]---(1)---[D]

• 您的算法将首先添加边 (C, D)，将 C 和 D 标记为已访问。
• 然后，它会添加边 (A, B)，将 A 和 B 标记为已访问。
• 现在，您只剩下边缘(B, C)。该图的 MST 显然包含该边。但是您的条件失败了 - B 和 C 都被标记为已访问。因此，您的算法不会添加该优势。

总之，您需要更换该支票。您应该检查当前边连接的两个节点是否已经由迄今为止添加到 MST 的边连接。如果是，则跳过它，否则添加它。

通常，disjoint-set data structures用于以良好的运行时间复杂度实现此目的(请参阅 the pseudocode on wikipedia )。但是，到目前为止，您的代码已经具有糟糕的运行时复杂性，因为访问的值()中的 0 必须线性搜索字典的值，直到到达末尾或找到值为 0 的元素，所以你做一些更简单的事情可能就足够了。

您可以在互联网上找到一些使用不相交集数据结构的算法实现，例如here .