Talk:Prim's algorithm: Difference between revisions

Revision as of 06:15, 30 July 2015

Latest revision as of 07:14, 25 March 2025

(14 intermediate revisions by 9 users not shown)

Line 1:

{{mathsWikiProject ratingbanner shell|class=C|priorityvital=Midyes|field1=discrete}}

{{WikiProject Computer scienceMathematics|importancepriority=high|class=CMid}}

{{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">—&nbsp;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? ==

Line 19 ⟶ 24:

== C++ code for Prim's using adjacency matrix A ==

A[i][j] is dstancea distance from node i to node j. Sentinels NONE and INF are used to avoid complex logic. The code is written in "computer olympiad style", using static allocation over STL containers or malloc'd memory. [[User:Jettlogic|Jettlogic]] 15:35, 11 October 2006 (UTC)

#include <algorithm>

Line 151 ⟶ 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 |0-262-53196-8}}). I suggest somebody that can explain this more intuitively edit the article accordingly. --[[User:Stimpy|Stimpy]] 16:08, 17 December 2006 (UTC)

== pseudocode cleanup ==

Line 184 ⟶ 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">—&nbsp;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 220 ⟶ 227:

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!&nbsp;—&nbsp;[[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)