CODEWITHSUNDEEP
algorithmgraphminimum-spanning-tree
Jayce
Jayce

Reputation: 601

Can the adjacency matrix implementation of Prim use a min heap?

I found that there are two ways to implement Prim algorithm, and that the time complexity with an adjacency matrix is O(V^2) while time complexity with a heap and adjacency list is O(E lg(V)).

I'm wondering can I use a heap when graph is represented with adjacency matrix. Does it make sense? If it does, is there any difference between adjacency matrix + heap and adjacency list + heap?

Upvotes: 4

Views: 1352

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76366

Generally, the matrix graph-representation is not so good for Prim's algorithm.

This is because of the main iteration of the algorithm, which pops out a node from the heap, and then scans its neighbors. How do you find its neighbors? Using the matrix graph representation, you basically need to loop over an entire matrix row (in the list graph-representation, you just need to loop over the node's list, which can be significantly shorter).

This means that, irrespective of the heap, just the sum of the part of finding the neighbor's of the popped node is already Ω(|V|2), as each node's row is eventually scanned.

So, no - it doesn't make much sense. The heap does not reduce the overall complexity.

Upvotes: 7

Related Questions