Content deleted Content added
m Reverted edit by 137.132.215.131 (talk) to last version by JustinBlank |
|||
| (29 intermediate revisions by 20 users not shown) | |||
Line 1:
{{
{{WikiProject Mathematics|priority=Mid}}
{{WikiProject Computer science|importance=high}}
}}
== Usage in 3d printing ==
The algorithim is used within the 3d printing slicer cura to generate tree supports, could a note about this application (along potentially with others be added)? (source of use in cura https://github.com/Ultimaker/CuraEngine/pull/655/commits/5004290e594332d23dcb94cc776144b5804b72e8 ) <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Gsykesvoyage|Gsykesvoyage]] ([[User talk:Gsykesvoyage#top|talk]] • [[Special:Contributions/Gsykesvoyage|contribs]]) 14:33, 22 October 2020 (UTC)</small> <!--Autosigned by SineBot-->
== Developed by Vojtech Jarnik? ==
Why is it stated that the algorithm was originally developed by Vojtech Jarnick? The cited paper actually contains description of Boruvka's algorithm (initially all vertices are fragments, and on each step a minimum edge for each fragment is added to MST, until there remains only one fragment). [[User:Reminiscenza|Reminiscenza]] ([[User talk:Reminiscenza|talk]]) 19:14, 30 May 2015 (UTC)
:In the cited paper, the relevent part is on page 60. Note that in step 1, he chooses any one vertex and in step k, he chooses one vertex from the vertices 1-k and one vertex from (k+1)-n. The Germant translation explains that same algorithm. The PDF I checked for is this one: http://dml.cz/bitstream/handle/10338.dmlcz/500726/Jarnik_01-0000-31_1.pdf [[User:Oracions|Petr Hudeček]] ([[User talk:Oracions|talk]]) 15:10, 11 June 2015 (UTC)
== complexity by binary heap ==
Is "(V+E)log(E)" really correct?
Thinking a heap H of edges which are directly connecting to the growing spanning tree.
All edges can be added to and removed from the heap H.
(Every edge can be adjacent to the growing spanning tree. This way edges can be added to the heap.
One edge can be added to the spanning tree, or become loop-making one and get disqualified.This way they can be removed so that
edges heap becomes {}.) I suspect that (V+E)log(E)-> E log(E) argument is missing something. I suspect (E+E) log(E) -> E log(E) is an
exhaustive argument.
--[[User:Timothy Redt|Timothy Redt]] ([[User talk:Timothy Redt|talk]]) 01:08, 22 July 2012 (UTC)
== C++ code for Prim's using adjacency matrix A ==
A[i][j] is
#include <algorithm>
Line 32 ⟶ 54:
}
}
== Colored lines in graph ==
Line 135 ⟶ 156:
:** Remove ''q'' from ''Q''
:** Add ''q'' to ''A'', under vertex ''a''
:This is how I interpreted the section '''Prim's algorithm''' in ''Introduction to Algorithms'' (chapter 23, section 2, {{ISBN
== pseudocode cleanup ==
Line 168 ⟶ 189:
:::I'd say that calls for some bookkeeping, but it's simple enough and I should have thought of it. Thanks, and sorry. —[[User:C. lorenz|c. lorenz]] ([[User talk:C. lorenz|talk]]) 14:48, 7 October 2008 (UTC)
::::Just a note to clarify the above explanation (wasn't obvious to me). You keep an array of distances from each remaining node to closest node in tree. When one node is added to the tree, you only need to check if the distances of remaining nodes to new node is smaller than previous closest. This makes it < |V| checks for every node added -> O(V). <small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/212.250.200.210|212.250.200.210]] ([[User talk:212.250.200.210|talk]]) 09:19, 27 October 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
== Isn't there anything wrong in the example ? ==
Line 186 ⟶ 209:
Why can't the graph contain negative weights in the example? Isn't this a little confusing for people who just learned Dijkstra? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/78.21.33.78|78.21.33.78]] ([[User talk:78.21.33.78|talk]]) 05:48, 29 May 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
== Simpler end of proof ==
Proof can be made slightly simpler at the end. We are in case Y != Y_1, and Y_1 is minimal spanning tree. There two possibilities, Y is also minimal spanning tree (other one with the same sum of the weight), which is OK, or Y have different sum of weight. If it have different number, then if must of course have more than sum for Y_1. At the ending wee see that Y_2, constructed from Y by removing f and adding e, have sum of weights smaller (or equal) than Y itself, and is again spanning tree. If it is equal then it s OK for us. If it is greater, this leads to contradiction (Y_2 cannot have smaller sum of weight from Y_1, which already have smallest possible one). Therfore Y != Y_1, and sum of Y < sum of Y_1, is impossible. End of proof. --[[Special:Contributions/91.213.255.7|91.213.255.7]] ([[User talk:91.213.255.7|talk]]) 04:28, 7 January 2011 (UTC)
== All black image: Maze Generation ==
The "Maze Generation" image used in this article renders all black and doesn't change. I've viewed this article with Chrome, Firefox and IE under Windows XP and they're all the same. When I go [http://upload.wikimedia.org/wikipedia/commons/d/da/Mazegeneration.gif directly to the GIF], I can see that it's actually an animated GIF demonstrating the generation of a maze. Seeing how this image is only indirectly related to the topic (even if it were working properly), I think this image should be removed. <span style="white-space:nowrap;"><b>[[User:Justin W Smith|Justin W Smith]]</b> <i><sup>[[User talk:Justin W Smith|talk]]</sup>/<sub>[[Special:Contributions/Justin W Smith|stalk]]</sub></i></span> 22:00, 17 January 2011 (UTC)
: to me it also seems that this maze is not generated with Prim's algorithm, as there are multiple "maze compononets" that grow into each other. Prim's algorithm only has one tree that grows to become a spanning tree. --[[Special:Contributions/134.96.156.103|134.96.156.103]] ([[User talk:134.96.156.103|talk]]) <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|undated]] comment added 10:13, 21 January 2011 (UTC).</span><!--Template:Undated--> <!--Autosigned by SineBot-->
== Djikstra and Prim algorithms ==
It is not clear the meaning of the sentence saying that Dijkstra "rediscovered" the algorithm: it seems to suggest that Prim's algorithm and the famous Djikstra's shortest path algorithm are the same, while they solve two different problems (minimum spanning tree and single-source shortest path problem). The quote should be made more precise or eliminated <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/93.36.87.111|93.36.87.111]] ([[User talk:93.36.87.111|talk]]) 12:01, 24 January 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
:No, it means precisely what it says: Dijkstra rediscovered the same minimum spanning tree algorithm. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:09, 24 January 2014 (UTC)
== [[:File:MAZE 30x20 Prim.ogv]] to appear as POTD ==
Hello! This is a note to let the editors of this article know that [[:File:MAZE 30x20 Prim.ogv]] will be appearing as [[Wikipedia:picture of the day|picture of the day]] on June 12, 2015. You can view and edit the POTD blurb at [[Template:POTD/2015-06-12]]. If this article needs any attention or maintenance, it would be preferable if that could be done before its appearance on the [[Main Page]]. Thanks! — [[User:Crisco 1492|Chris Woodrich]] ([[User talk:Crisco 1492|talk]]) 23:50, 22 May 2015 (UTC)
{{POTD/2015-06-12}}
== Linear Time For Dense Graphs ==
The article currently claims "However, for graphs that are sufficiently dense, Prim's algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.[10]". The reference is to Tarjan, "Data Structures and Network Algorithms", page 77. While I am only now learning about Prim's algorithm, I do not believe this is accurate. The page states:
: The running time of this implementation is dominated by the heap operations, of which there are n — 1 deletemin operations, n — 1 insert operations, and at most m — n + 1 siftup operations. By the analysis of §3.2, the total running time is 0(n d logd n + m logd n).
I cannot find anything on that page that indicates that the algorithm is ever linear. [[User:JustinBlank|JustinBlank]] ([[User talk:JustinBlank|talk]]) 19:06, 27 October 2024 (UTC)
| |||