我正在寻找运行Kruskal的算法，因此已经使用一些getter和setter初始化了Tree对象。在其中一种方法中，我使用了set和get方法来获取值，如您在第一个代码中显示的find和union方法中所见。在另一种方法中，我直接使用“ class.method”来检索第二个代码中显示的值。我使用这两种方式都得到相同的输出，但是我想知道两者在逻辑上是否相同？另外，哪个会更快，为什么呢？而且，如果图是密集连接还是稀疏连接，会有所不同吗？

图解释了输入和输出方案： First input and output Second input and output

第一种方法/方式：

abc=[(0,1,1),(0,2,5),(1,(2,3,2),6)]
abcd=[(0,6),3),8),4,7),(3,9)]

import operator
import math

def MST_Kruskel(graph):
    vertices={}
    edges={}
    for i in graph:
        if i[0] not in vertices:
            vertices[i[0]]='infinity and beyond!'
        if i[1] not in vertices:
            vertices[i[1]]='infinity and beyond!'
        edges[(i[0],i[1])]=i[2]
    #print(vertices)
    #print(edges)
    sorted_edges=sorted(edges.items(),key=operator.itemgetter(1))
    #print(sorted_edges)
    tree_nodes={}
    for i in vertices.keys():
        tree_nodes[i]=makeset(i)
    #print(tree_nodes)
    X={}
    #so-called Kruskal's algorithm
    for i in sorted_edges:
        if len(X.keys())==len(vertices.keys())-1:
            break
        else:
            if find(i[0][0],tree_nodes)!=find(i[0][1],tree_nodes):
                X[i[0]]=i[1]
                union(i[0][0],i[0][1],tree_nodes)
                #print(X)
    return sum(X.values()),list(X.keys())

class Tree(object):
    def __init__(self,u):
        self.parent=u
        self.rank=0

    def get_parent(self):
        return self.parent

    def get_rank(self):
        return self.rank

    def set_parent(self,v):
        self.parent=v

    def set_rank(self,v):
        self.rank=v

def makeset(u):
    tree_node=Tree(u)
    return tree_node

def find(u,tree_nodes):
    for i in tree_nodes.keys():
        if i==u:
            tree_node=tree_nodes[u]
            while u!=tree_nodes[u].get_parent():
                tree_nodes[u].set_parent(u)
                #print("We got executed")
    return u

def union(u,v,tree_nodes):
    rx=find(u,tree_nodes)
    ry=find(v,tree_nodes)
    if rx==ry:
        return 'Both in the same tree,you fool!'
    if tree_nodes[rx].get_rank()>tree_nodes[ry].get_rank():
        tree_nodes[ry].set_parent(rx)
        #print("Yo mama!")
    else:
        #print("Hi!")
        tree_nodes[rx].set_parent(ry)
        if tree_nodes[rx].get_rank()==tree_nodes[ry].get_rank():
            tree_nodes[ry].set_rank(tree_nodes[ry].get_rank()+1)
            #print(tree_nodes[rx].parent)
            #print(tree_nodes[ry].parent)
            #print(tree_nodes[rx].rank)
            #print(tree_nodes[ry].rank)

第二种方法/方式：

abc=[(0,key=operator.itemgetter(1))
    #print(sorted_edges)
    tree_nodes={}
    for i in vertices.keys():
        tree_nodes[i]=makeset(i)
    #print(tree_nodes)
    X={}
    #so-called Kruskal's algorithm
    for i in sorted_edges:
        if find(i[0][0],tree_nodes):
            X[i[0]]=i[1]
            union(i[0][0],tree_nodes)
            #print(X)
    return sum(X.values()),tree_nodes):
    for i in tree_nodes.keys():
        if i==u:
            tree_node=tree_nodes[u]
            while u!=tree_nodes[u].parent:
                u=tree_nodes[u].parent
                #print("We got executed")
    return u

def union(u,you fool!'
    if tree_nodes[rx].rank>tree_nodes[ry].rank:
        tree_nodes[ry].parent=rx
        #print("Yo mama!")
    else:
        #print("Hi!")
        tree_nodes[rx].parent=ry
        if tree_nodes[rx].rank==tree_nodes[ry].rank:
            tree_nodes[ry].rank=tree_nodes[ry].rank+1
            #print(tree_nodes[rx].parent)
            #print(tree_nodes[ry].parent)
            #print(tree_nodes[rx].rank)
            #print(tree_nodes[ry].rank)