找到一个图的最小权重

我想制作一个程序，它使用Kruskal算法计算最小跨度重量，我已经按照递增的顺序使用他们的weghts对边进行了排序，并将其放入2d列表中。后来我也写一个方法使用sortededge，采取样本，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])

拿到最低的重量，但它亘古不变的工作，为所有的图表和我将欢迎任何帮助

来源

2014-12-12 Kal

欢迎计算器！您可以使用编辑器中的“{}”按钮以可读方式格式化代码。请具体说明“不行”的含义;代码失败的例子是什么？这个例子的实际和预期结果是什么？ – 2014-12-12 23:34:45

你的算法实现是错误的。

让一个例子，其中的算法中失败：

enter image description here

和边缘看起来是这样排序后：

边缘：

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

在第一次迭代

你会把1和2在你的vertexcheck中。在第二次迭代中更新vertexcheck = [1,2]
，你将把3和4放在你的vertexcheck中。更新vertexcheck = [1,2,3,4]
但在第三次迭代，你可以不加2-> 3的边缘，因为这两个顶点出现在您vertexcheck。

这就是为什么你的实现给错误输出:(

实际上，对于克鲁斯卡的实现，你需要知道和使用称为联盟查找数据结构算法，它告诉你，如果你正在尝试连接当前节点已经连接:)

如果他们已经连接然后跳过优势，因为他们已经用低成本的:)否则将它们连接连接...

由于很多实现可供MST使用python ，我不会打扰给你一个:)

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

以及范例： Kruskal's_implementation

来源

2014-12-14 06:48:44

找到一个图的最小权重

回答

相关问题