它没有使用 "sorted" 排序，得到了错误的答案。而且我不确定算法是否正确

Question

我正在使用 Kruskal 算法 来寻找最小生成树。我只是按照讲座中提供的算法进行操作，我应该保持 Edge class 的格式。 sorted 不工作所以我不知道逻辑是否错误。

在 Edge class 的构造函数中是否有任何命名父级的原因？

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()

输入

预期输出

Answer 1

您混淆了函数 sorted(iterable[ key][ reverse]) 和列表方法 sort(*, key=None, reverse=None).

根据文档排序的位置："Return a new sorted list from the items in iterable." 虽然根据文档进行排序：此方法对列表进行就地排序，仅使用 < 项目之间的比较。不抑制异常 - 如果任何比较操作失败，整个排序操作将失败（并且列表可能会保留部分修改状态）。

因此，为了让您的代码正常工作，您需要更改：排序（edge_list，键=lambda顶点：vertex.weight）到 edge_list.sort(key=lambda 顶点: vertex.weight)

假设您的代码中的其他所有内容都是正确的

它没有使用 "sorted" 排序，得到了错误的答案。而且我不确定算法是否正确

it's not sorted using "sorted", and getting a wrong answer. And I am not sure if the algorithm is right

minimum-spanning-tree

python-3.x

kruskals-algorithm