Can binomial heap be used to find connected components in a graph?

Question

How can a binomial heap be useful in finding connected components of a graph, it cannot be used then why?

Answer 1

I've never seen binomial heaps used this way, since graph connected components are usually found using a depth-first search or breadth-first search, and neither algorithm requires you to use any sort of priority queue. You could, of course, do a sort of "priority-first search" to find connected components by replacing the stack or queue of DFS or BFS with a priority queue, but there's little reason to do so. That would slow the cost of finding connected components down to O(m + n log n) rather than the O(m + n) you'd get from a vanilla BFS or DFS.

There is one way in which you can tenuously say that binomial heaps might be useful, and that's in a different strategy for finding connected components. You can, alternatively, use a disjoint-set forest to identify connected components. You begin with each node in its own partition, then call the union operation for each edge to link nodes together. When you've finished, you will end up with a collection of trees, each of which represents one connected component.

There are many strategies for determining how to link trees in a disjoint-set forest. One of them is union-by-size, in which whenever you need to pick which representative to change, you pick the tree of smaller size and point it at the tree of larger size. You can prove that the smallest tree of height k that can be formed this way is a binomial tree of rank k. That's formed by pairing off all the nodes, then taking the representatives and pairing them off, etc. (Try it for yourself - isn't that cool?)

But that, to me, feels more like a coincidence than anything else. This is less about binomial heaps and more about binomial trees, and this particular shape only arises if you're looking for a pathological case rather than as a matter of course in the execution of the algorithm.

So the best answer I have is "technically you could do this, but you shouldn't, and technically binomial trees arise in this other context that's related to connected components, but that's not the same as using binomial heaps."

Hope this helps!