0
$\begingroup$

Is there a way to implement Kruskal's algorithm for finding the MST of an undirected graph using priority queues? The standard implementation uses the disjoint set data structure but I was curious if a PQ implementation is possible, and potentially even better in time complexity.

I looked it up online and found a PQ implementation for Prim's algorithm, but not for Kruskal's algorithm. Any help would be much appreciated.

Improve this question
$\endgroup$
1
  • $\begingroup$ well what do you think? Do you think, on paper, you could solve an instance of MST problem by kruskals algorithm utilising priority queues? If yes, then there are high chances that it can be implemented as well. $\endgroup$
    – Rinkesh P
    Apr 10, 2022 at 4:04

1 Answer 1

Reset to default
1
$\begingroup$

A priority queue (PQ) cannot replace the disjoint-set or union-find (UF) data structure for the Kruskal's algorithm for they have different purpose.

Recall that in Kruskal, the edges in $E$ are ignored, as if the graph is fully disconnected. And for each iteration, it selects a minimum edge from $E$ that can be used to linked vertices, while ensuring that no cycle is created.

The UF is used to guarantee that there will be no cycle when adding a new edge. A PQ cannot do this. Maybe you can use a PQ for selecting the next edge to be added but I don't see how it will improve the running-time of the algorithm, compared to the usual approach of sorting the edges.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.