Timeline for Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2018 at 17:06 | vote | accept | abkds | ||
| Mar 19, 2014 at 19:56 | comment | added | Tanmoy Banerjee | @AbKDs: I have edited my answer.now this may be helpful. | |
| Mar 19, 2014 at 19:14 | comment | added | G. Bach | For a solid implementation of Prim's algorithm with a Fibonacci heap, see this answer on SO. Since it's object oriented, checking whether a node is in the queue is done using hashing. | |
| Mar 19, 2014 at 19:13 | comment | added | G. Bach | @tan With a binary heap you don't get the complexity AbKDs is looking for. | |
| Mar 19, 2014 at 19:13 | comment | added | Tanmoy Banerjee | @G.Bach:sorry.it is a binary heap. | |
| Mar 19, 2014 at 19:09 | comment | added | G. Bach | @tan That much is obvious. But is it a binary heap, a binomial heap, a Fibonacci heap, some other minheap implementation I'm not aware of? | |
| Mar 19, 2014 at 19:06 | comment | added | Tanmoy Banerjee | @G.Bach: It is using a min priority queue(clearly written in my answer). | |
| Mar 19, 2014 at 19:06 | answer | added | A.Schulz | timeline score: 2 | |
| Mar 19, 2014 at 19:01 | comment | added | G. Bach | @tan Your answer doesn't address what heap implementation will give you that complexity, and considering AbKDs's question, that is a key point. | |
| Mar 19, 2014 at 18:58 | comment | added | Tanmoy Banerjee | now go through this link and see my answer. | |
| Mar 19, 2014 at 18:56 | history | edited | abkds | CC BY-SA 3.0 |
added 89 characters in body
|
| Mar 19, 2014 at 18:55 | comment | added | Tanmoy Banerjee | please edit your post to reflect that. | |
| Mar 19, 2014 at 18:55 | comment | added | abkds | m number of edges and n number of vertices | |
| Mar 19, 2014 at 18:54 | comment | added | Tanmoy Banerjee | What is m and n? | |
| Mar 19, 2014 at 18:38 | review | First posts | |||
| Mar 20, 2014 at 0:02 | |||||
| Mar 19, 2014 at 18:29 | history | edited | abkds |
edited tags
|
|
| Mar 19, 2014 at 18:20 | history | asked | abkds | CC BY-SA 3.0 |