Kruskal Complexity

Question

I have implemented the kruskal algorithm in this way. My question is, what is the complexity of this implementation?

To implement the algorithm I first initialized all the nodes to -1, that is, all the nodes are separated and even They have no group. From here I have contemplated that 4 cases can occur:

1: If the two nodes to be analyzed are -1 and -1, it means that they are separated, therefore we will have to join them and create a new group, adding 1 to the group variable initialized at the beginning.

2: The two nodes have the same group number. In this case we cannot join them, since these would form a cycle.

3: In this case, one of the two nodes has no group (-1) therefore, the node that has no group (A or B), is assigned the group of the other node to join your group.

4 In this last case the group of the two nodes is different, one of the two groups would simply have to be changed by another group. Example: If we have a group 4 of nodes and another group 6, all the nodes of group 4 would become of group 6. You could also change those of the other group.

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

For V vertices and E edges we have time complexity O(ElogE) or O(ElogV). Sorting of edges takes O(ELogE) time. After sorting, you are iterating through all edges and apply the find-union algorithm (grouping technique). The find and union operations can take at most O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be at most O(V^2), so O(LogV) is O(LogE) the same. Therefore, the overall time complexity is O(ElogE) or O(ElogV).