Prim Algorithm

Question

What is the time complexity of Prim algorithm without using min heap?

Comments

Please elaborate your approach of solving this without min heap..

---

Start with minimum edge weight and then consider only neighbours of these two vertices and select minimum neighbour of them and add to MST after consider neigbours of these three nodes and construct MST

---

I think you are indicating the implementation using Array:

Initialize the distance array with 0 (for source) and infinity (for others).

Initialize a parent array with NIL for all.

Step 1:In place of extract min in heap we need to Find the min from distance array. This takes O(V) to search through the whole array. Let this vertex with minimum d-value be V.

Step 2: Then go through all the adjacent vertices of V which are not yet taken into the MST and check if there is any need to update the distance array of the adj. vertices. This takes O(d_v) using adjacency list where d_v is the degree of V (i.e. traversing through the list associated with V).

Each updation takes O(1). So for d_v adj vertices we need O(d_v).

Step 3: If any vertex is left to be taken into MST goto step 1.

Step 1 is visited for V times and each time it takes O(V) to search the min. So O(V²)

Step 2 takes O(d_v1 + d_v2 + d_{v3 ..+} d_vn) = O(E) for all the vertices.

So total it takes O(V²).

If you sort the array to reduce the time of searching in step 1, then you have to sort the array each time after step 2.

So, step 1 : O(1) * V times = O(V)

step 2: After updation sort the array. It takes O(VlogV). Step 2 is executed for V times. So O(V²logV).

This increases the time complexity.

 

Answer 1

Use min heap :

                      Extract_min -> O(V log V)

                      Decrease_key -> O(E logV)

                     Build_heap -> O(E)

  TC = O(V logV + E logV + E) == O(E logE)

Use Fibonacci_heap ::

According Fibonacci heap perform Decrease_key in "Constent Time"

                          TC = O(V logV + E)

https://stackoverflow.com/questions/4825518/how-to-implement-prims-algorithm-with-a-fibonacci-heap

http://www.cs.northwestern.edu/~agupta/_projects/algorithms/Fibonacci%20Heaps/Doc/Design%20Document%20%231.pdf

             

Comments

Build Heap should be O(V)