python - 克鲁斯卡复杂度

Question

我就是这样实现kruskal算法的。我的问题是，这个实现的复杂性是多少？

为了实现该算法，我首先将所有节点初始化为-1，即所有节点都是分开且均匀的他们没有团体。从这里我想到可能会发生4种情况:

1:如果要分析的两个节点是-1和-1，则意味着它们是分开的，因此我们必须将它们连接起来并创建一个新的group，将一开始初始化的group变量加1。

2:两个节点的组号相同。在这种情况下，我们不能加入它们，因为它们会形成一个循环。

3:在这种情况下，两个节点之一没有组 (-1)，因此，分配没有组(A 或 B)的节点其他节点的组加入您的组。

4 在最后一种情况下，两个节点的组不同，只需更改两个组中的一个即可另一组。示例:如果我们有一组节点 4 和另一个节点组 6，则组 4 的所有节点都将变为组 6 的组。您也可以更改其他组的组。

import heapq
def kruskal(G):



    for iniciarNode in G.nodes():

        nodes[iniciarNode] = -1


    for i in aristasLista:


        heapq.heappush(aristasOrden, (G.edges[i]['weight'], i))


    while (len(aristasOrden) != 0):


        arestaSeguent = heapq.heappop(aristasOrden)[1]


        nodeA = arestaSeguent[0] 
        nodeB = arestaSeguent[1] 

        if ((nodes[nodeA] == -1) and (nodes[nodeB] == -1)):


            nodes[nodeA] = grup
            nodes[nodeB] = grup
            grup = grup + 1
            treeG.add_edge(arestaSeguent[0],arestaSeguent[1],weight=arestaSeguent[0])
            total_weight = total_weight + arestaSeguent[0]



        elif (nodes[nodeA] == nodes[nodeB]): continue



        elif ((nodes[nodeA] == -1) or (nodes[nodeB] == -1)  ):


            if (nodes[nodeA] == -1):

                nodes[nodeA] = nodes[nodeB]
                treeG.add_edge(arestaSeguent[0],arestaSeguent[1],weight=arestaSeguent[0])
                total_weight = total_weight + arestaSeguent[0]


            else:

                nodes[nodeB] = nodes[nodeA]
                treeG.add_edge(arestaSeguent[0],arestaSeguent[1],weight=arestaSeguent[0])
                total_weight = total_weight + arestaSeguent[0]





            treeG.add_edge(arestaSeguent[0],arestaSeguent[1],weight=arestaSeguent[0])
            total_weight = total_weight + arestaSeguent[0]

Answer 1

对于 V 顶点和 E 边，我们的时间复杂度为 O(ElogE) or O(ElogV) 。边缘排序需要 O(ELogE)时间。排序后，您将迭代所有边并应用查找并集算法(分组技术)。查找和并集操作最多可以花费 O(LogV)时间。所以总体复杂度是O(ELogE + ELogV)时间。 E的值最多可以是O(V^2) ，所以O(LogV)是 O(LogE)相同。因此，总体时间复杂度为O(ElogE)或O(ElogV) .