Suppose that all edge weights in a graph are integers in the

Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Prim\'s algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W ?

Solution

Answer: The running time for Prim\'s algorithm depends on the way how it is implemented. There can be multiple ways of implementing the Prim\'s algorithm. A simple implementation based on a greedy method of selecting the minimum cost edge, during each iteration, out of edges not part of tree will run in O(|V|²) time where |V| is the number of vertices in Graph. This implementation can be used for edge weights lying in the range 1 to |V| (dense graphs).

Its performance can be improved further if we implement the algorithm by using a min-heap as priority queue. In such a implementation, we can get the performance of the order of log(|V|). In such a case also, performance largely depends on the fact how min-heap is implemented. In a typical binary tree based implementation, we will get the performance of the order of O(|E| log (|V|)) where |E| and |V| are the number of edges and vertices in graph respectively.

Another option to implement min-heap is to use Fibonacci heap. In Fibonacci heap, every standard heap operation except delete takes O(1) time, while delete takes O(log n) time where n is number of nodes in heap. So, if this kind of emplementation is used, performance of Prim\'s algorithm will be improved to O(|E| + |V| log (|V|)). This kind of implementation can be used for edge weights lying between 1 and some constant W (sparse graphs).