0 votes 0 votes What is the time complexity of Prim algorithm without using min heap? Algorithms algorithms graph-algorithm prims-algorithm time-complexity + – Alakhator asked Oct 11, 2018 retagged Jul 7, 2022 by Lakshman Bhaiya Alakhator 1.1k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply MiNiPanda commented Oct 11, 2018 reply Follow Share Please elaborate your approach of solving this without min heap.. 0 votes 0 votes Alakhator commented Oct 12, 2018 reply Follow Share 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 0 votes 0 votes MiNiPanda commented Oct 12, 2018 reply Follow Share 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(dv) using adjacency list where dv is the degree of V (i.e. traversing through the list associated with V). Each updation takes O(1). So for dv adj vertices we need O(dv). 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(V2) Step 2 takes O(dv1 + dv2 + dv3 ..+ dvn) = O(E) for all the vertices. So total it takes O(V2). 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(V2logV). This increases the time complexity. 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes 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 arya_stark answered Oct 12, 2018 arya_stark comment Share Follow See 1 comment See all 1 1 comment reply dhruvil3 commented Oct 2, 2020 reply Follow Share Build Heap should be O(V) 0 votes 0 votes Please log in or register to add a comment.