Talk:Prim's algorithm: Difference between revisions

Revision as of 14:34, 22 October 2020

Latest revision as of 07:14, 25 March 2025

(8 intermediate revisions by 4 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-->

Line 226 ⟶ 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)