0

Is it possible to implement Prim's algorithm using fibonacci heap too? Any kind of assistance is welcome.

Improve this question
4
  • You can take any min-heap, and the complexity of the heap operations will influence the complexity of the algorithm overall. Commented Oct 12, 2015 at 8:13
  • But prim's method's complexity is o(n^2) and in case of min-heap complexity will be-(worst case) o(log n). So how is it going to influence the complexity of the algorithm overall?Kindly explain. Commented Oct 12, 2015 at 8:19
  • If you use a min heap, you can implement Prim's algorithm in O(n*log(n)) not in O(log(n)) Commented Oct 12, 2015 at 8:48
  • It depends on what representation of your graph you have access to. If you have an adjacency matrix, you won't do better than Theta(n^2) since you have to look at half of the matrix to see all edges, but you can do it in O(n^2) by maintaining an array of costs required to connect each vertex to the current tree and linearly searching through that at each step. With an adjacency list, you can make the complexity dependent on the number of edges, and then you can do better for graphs that aren't almost complete with a binary heap, and equally well with a Fibonacci heap. Commented Oct 12, 2015 at 8:56

1 Answer 1

Reset to default
1

Any type of min heap will do for Prim's algorithm. However, please note that although Fibonacci heap has better asymptotic complexity for some operations than binary heap, I've empirically proven that because of the big constant, it outperforms the binary heap only for really big graphs(in the order of billion or even tens of billions edges).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.