求图的最小权

Question

我在做一个程序，用克鲁斯卡尔算法计算最小跨越重量， 我已经用这些边按升序排序，并把它放在一个二维列表中。 然后我写了一个用sortedge得到最小重量的方法， 作为样本，sortededge = [['1', '2', '1'], ['5', '6', '1'], ['2', '4', '2'], ['3', '6', '2'], ['3', '5', '3'], ['4', '6', '3'], ['3', '4', '5'], ['1', '3', '6']] 方法是

vertexcheck = []
minimumdistance  = 0
def MSW:
    for i in range(len(sortededge)):
        if (sortededge[i][0] not in vertexcheck) or (sortededge[i][1] not in vertexcheck):
            if (sortededge[i][0] not in vertexcheck):
                vertexcheck.append(sortededge[i][0])


            if (sortededge[i][1] not in vertexcheck):
                vertexcheck.append(sortededge[i][1])
            minimumdistance += int(sortededge[i][2])

但它并不适用于所有的图表，我欢迎任何帮助

Answer 1

你的算法实现是错误的。在

举一个你的算法失败的例子：

排序后边缘将如下所示：

边缘：

    1, 2, 1
    3, 4, 2
    2, 3, 5

在第一次迭代中，你将把1和2放在顶点检查中。更新的vertexcheck=[1,2]
在第二次迭代中，你将把3和4放在顶点检查中。更新的vertexcheck=[1,2,3,4]
但在第三次迭代中，您不能添加2->；3条边，因为这两个顶点都存在于vertexcheck中。在

这就是为什么你的实现给出了错误的输出：（

实际上，对于Kruskal的实现，您需要知道并使用一个名为Union Find的数据结构算法，该算法会告诉您当前尝试连接的节点是否已经连接：）

如果它们已经连接，则跳过边缘，因为它们已经以较低的成本连接：）否则连接它们。。。在

由于使用python的MST有很多实现，所以我不麻烦您给出一个：）

您可以在这里找到伪代码： Kruskal's_algorithm

以及一个示例实现： Kruskal's_implementation