I have implemented Boruvka's algorithm with a union-find structure to keep track of the components:

method boruvkas(GraphEdgeList, numOfNodes):
    compCount = numOfNodes
    cheapest = Array(numOfNodes), initialized with (0, 0, ∞)
    MSTEdgeList = []
    while compCount > 1:
        for (u, v, w) in GraphEdgeList:
            comp1 = find(u), comp2 = find(v)
            if comp1 != comp2:
                if w < cheapest[comp1]:
                    cheapest[comp1] = (u, v, w)
                if w < cheapest[comp2]:
                    cheapest[comp2] = (u, v, w)
        for i from 1 to nNodes:
            e = cheapest[i]
            if e.weight != ∞:
                comp1 = find(e.first), comp2 = find(e.second)
                if comp1 != comp2:
                    unite(comp1, comp2)
                    MSTEdgeList.add(e)
                    compCount--
        reset(cheapest, (0, 0, ∞))
    return MSTEdgeList

I understand that the outer loop runs log(V) times, as the number of components approximately halves in each iteration. The first for loop runs E times, but each time the find operation takes log(V) time. The second loop however, runs as many times as the number of components. I have read that the complexity of Boruvka's algorithm is Elog(V), but I can't really see why.

CodePudding user response：

I think I have figured something out. The 1st for loop runs E times, with find operation each time, so it is O(Elog(V)), the second for runs log(V) times (as many components there are in each iteration), and the find and unite operations take log(V). So it runs with O(logV*logV). The while loop also runs log(V) times, so the overall complexity must be O(Elog^2V log^3(V))=O((E logV)log^2V)=O(Elog^2(V)).

CodePudding user response：

The problem is in assuming that all those union and find operations take O(log V) time. They don't. They don't even take the usual