我正在使用Kruskal算法来查找最小生成树。我只是遵循了讲座期间提供的算法，我应该保持Edge类的格式。排序不起作用，所以我无法弄清楚逻辑是否错误。
是否有任何理由在Edge类的构造函数中命名父级。
import sys
class Edge:
def __init__(self, start_ver, to_vertex, weight):
self.start_ver = start_ver
self.to_vertex = to_vertex
self.weight = weight
self.spanning_tree = False
# def __lt__(self, other):
# return self.weight < other.weight
class UnionFind:
def __init__(self, ver_num):
self.parent = None
self.create_set(ver_num)
def create_set(self, ver_num):
self.parent = list(range(ver_num))
def find_set(self, ver_num):
if self.parent[ver_num] != ver_num:
self.parent[ver_num] = self.find_set(self.parent[ver_num])
return self.parent[ver_num]
def merge_set(self, one_ver, two_ver):
self.parent[self.find_set(one_ver)] = self.find_set(two_ver)
def MST_Kruskal(ver_num, edge_list):
union_find = UnionFind(ver_num)
mst_tree = list()
sorted(edge_list, key=lambda vertex: vertex.weight)
for edge in edge_list:
if not edge.spanning_tree:
if union_find.find_set(edge.start_ver) != union_find.find_set(edge.to_vertex):
mst_tree.append(edge)
if len(mst_tree) == ver_num - 1:
edge.spanning_tree = True
union_find.merge_set(edge.start_ver, edge.to_vertex)
sorted(edge_list, key=lambda vertex: vertex.weight)
else:
return
total = 0
for x in mst_tree:
total += x.weight
print(total)
def main():
edge_list = list()
vertex_num, edge_num = map(int, (sys.stdin.readline().split()))
for e in range(edge_num):
start, end, weight = map(int, sys.stdin.readline().split())
edge = Edge(start-1, end-1, weight)
edge_list.append(edge)
MST_Kruskal(vertex_num, edge_list)
if __name__== "__main__":
main()
输入
4 5
1 2 10
2 3 15
1 3 5
4 2 2
4 3 40
预期产出
17
您将排序的函数(迭代[，键][，反向](与列表方法sort(*，键=无，反向=无(混淆了。
根据文档排序的位置是："从可迭代的项目中返回一个新的排序列表。 虽然根据文档排序：此方法仅使用项目之间的
因此，要使代码正常工作，您需要更改： sorted(edge_list， key=lambda vertex： vertex.weight( to edge_list.sort(key=lambda vertex： vertex.weight(
这假设您的代码中的其他所有内容都是正确的