Prim's algorithm - Revision history

Ajmullen: /* Description */ Formalised pseudocode

2025-05-15T20:30:55Z

Description: Formalised pseudocode

← Previous revision		Revision as of 20:30, 15 May 2025
Line 84:		Line 84:

	In more detail, it may be implemented following the [[pseudocode]] below.		In more detail, it may be implemented following the [[pseudocode]] below.
			'''function''' Prim(vertices, edges) '''is'''
	{{ordered list
			'''for''' '''each''' vertex '''in''' vertices '''do'''
	\| Associate with each vertex ''v'' of the graph a number ''C''[''v''] (the cheapest cost of a connection to ''v'') and an edge ''E''[''v''] (the edge providing that cheapest connection). To initialize these values, set all values of ''C''[''v''] to +∞ (or to any number larger than the maximum edge weight) and set each ''E''[''v''] to a special [[flag value]] indicating that there is no edge connecting ''v'' to earlier vertices.
			cheapestCost[vertex] ← ∞
	\| Initialize an empty forest ''F'' and a set ''Q'' of vertices that have not yet been included in ''F'' (initially, all vertices).
			cheapestEdge[vertex] ← null
	\| Repeat the following steps until ''Q'' is empty:

	{{ordered list\|type=a
			explored ← empty set
	\| Find and remove a vertex ''v'' from ''Q'' having the minimum possible value of ''C''[''v'']
			unexplored ← set containing all vertices
	\| Add ''v'' to ''F''

	\| Loop over the edges ''vw'' connecting ''v'' to other vertices ''w''. For each such edge, if ''w'' still belongs to ''Q'' and ''vw'' has smaller weight than ''C''[''w''], perform the following steps:
			startVertex ← any element of vertices
	{{ordered list\|type=lower-roman
			cheapestCost[startVertex] ← 0
	\| Set ''C''[''w''] to the cost of edge ''vw''

	\| Set ''E''[''w''] to point to edge ''vw''.
			'''while''' unexplored '''is''' not empty '''do'''
	}}
			// Select vertex in unexplored with minimum cost
	}}
			currentVertex ← vertex in unexplored with minimum cheapestCost[vertex]
	\| Return ''F'', which specifically includes the corresponding edges in E
			unexplored.remove(currentVertex)
	}}
			explored.add(currentVertex)


			'''for''' '''each''' edge (currentVertex, neighbor) '''in''' edges '''do'''
			'''if''' neighbor '''in''' unexplored '''and''' weight(currentVertex, neighbor) < cheapestCost[neighbor] THEN
			cheapestCost[neighbor] ← weight(currentVertex, neighbor)
			cheapestEdge[neighbor] ← (currentVertex, neighbor)

			resultEdges ← empty list
			'''for''' '''each''' vertex '''in''' vertices '''do'''
			'''if''' cheapestEdge[vertex] ≠ null '''THEN'''
			resultEdges.append(cheapestEdge[vertex])

			'''return''' resultEdges
	As described above, the starting vertex for the algorithm will be chosen arbitrarily, because the first iteration of the main loop of the algorithm will have a set of vertices in ''Q'' that all have equal weights, and the algorithm will automatically start a new tree in ''F'' when it completes a spanning tree of each connected component of the input graph. The algorithm may be modified to start with any particular vertex ''s'' by setting ''C''[''s''] to be a number smaller than the other values of ''C'' (for instance, zero), and it may be modified to only find a single spanning tree rather than an entire spanning forest (matching more closely the informal description) by stopping whenever it encounters another vertex flagged as having no associated edge.		As described above, the starting vertex for the algorithm will be chosen arbitrarily, because the first iteration of the main loop of the algorithm will have a set of vertices in ''Q'' that all have equal weights, and the algorithm will automatically start a new tree in ''F'' when it completes a spanning tree of each connected component of the input graph. The algorithm may be modified to start with any particular vertex ''s'' by setting ''C''[''s''] to be a number smaller than the other values of ''C'' (for instance, zero), and it may be modified to only find a single spanning tree rather than an entire spanning forest (matching more closely the informal description) by stopping whenever it encounters another vertex flagged as having no associated edge.

145.118.199.231: /* Proof of correctness */ added newline

2025-04-29T16:22:44Z

Proof of correctness: added newline

← Previous revision		Revision as of 16:22, 29 April 2025
Line 136:		Line 136:

	== Proof of correctness ==		== Proof of correctness ==
	Let ''P'' be a connected, weighted [[graph theory\|graph]]. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since ''P'' is connected, there will always be a path to every vertex. The output ''Y'' of Prim's algorithm is a [[Tree (graph theory)\|tree]], because the edge and vertex added to tree ''Y'' are connected. Let ''Y<sub>1</sub>'' be a minimum spanning tree of graph P. If ''Y<sub>1</sub>''=''Y'' then ''Y'' is a minimum spanning tree. Otherwise, let ''e'' be the first edge added during the construction of tree ''Y'' that is not in tree ''Y<sub>1</sub>'', and ''V'' be the set of vertices connected by the edges added before edge ''e''. Then one endpoint of edge ''e'' is in set ''V'' and the other is not. Since tree ''Y<sub>1</sub>'' is a spanning tree of graph ''P'', there is a path in tree ''Y<sub>1</sub>'' joining the two endpoints. As one travels along the path, one must encounter an edge ''f'' joining a vertex in set ''V'' to one that is not in set ''V''. Now, at the iteration when edge ''e'' was added to tree ''Y'', edge ''f'' could also have been added and it would be added instead of edge ''e'' if its weight was less than ''e'', and since edge ''f'' was not added, we conclude that		Let ''P'' be a connected, weighted [[graph theory\|graph]]. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since ''P'' is connected, there will always be a path to every vertex. The output ''Y'' of Prim's algorithm is a [[Tree (graph theory)\|tree]], because the edge and vertex added to tree ''Y'' are connected.

			Let ''Y<sub>1</sub>'' be a minimum spanning tree of graph P. If ''Y<sub>1</sub>''=''Y'' then ''Y'' is a minimum spanning tree. Otherwise, let ''e'' be the first edge added during the construction of tree ''Y'' that is not in tree ''Y<sub>1</sub>'', and ''V'' be the set of vertices connected by the edges added before edge ''e''. Then one endpoint of edge ''e'' is in set ''V'' and the other is not. Since tree ''Y<sub>1</sub>'' is a spanning tree of graph ''P'', there is a path in tree ''Y<sub>1</sub>'' joining the two endpoints. As one travels along the path, one must encounter an edge ''f'' joining a vertex in set ''V'' to one that is not in set ''V''. Now, at the iteration when edge ''e'' was added to tree ''Y'', edge ''f'' could also have been added and it would be added instead of edge ''e'' if its weight was less than ''e'', and since edge ''f'' was not added, we conclude that

	:<math>w(f) \ge w(e).</math>		:<math>w(f) \ge w(e).</math>

Xathious: Reverted good faith edits by 186.185.247.155 (talk): Edit not in english

2025-03-27T12:17:56Z

Reverted good faith edits by 186.185.247.155 (talk): Edit not in english

← Previous revision		Revision as of 12:17, 27 March 2025
Line 70:		Line 70:
	}}.</ref>		}}.</ref>

	Other well-known algorithms for this problem include [[Kruskal's algorithm]] and [[Borůvka's algorithm]].<ref>{{citation\|first=Robert Endre\|last=Tarjan\|author-link=Robert Tarjan\|title=Data Structures and Network Algorithms\|series=CBMS-NSF Regional Conference Series in Applied Mathematics\|volume=44\|publisher=[[Society for Industrial and Applied Mathematics]]\|year=1983\|contribution=Chapter 6. Minimum spanning trees. 6.2. Three classical algorithms\|pages=72–77}}.</ref> These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected ~~teacher de las notas porfa~~ However, running Prim's algorithm separately for each [[Connected component (graph theory)\|connected component]] of the graph, it can also be used to find the minimum spanning forest.<ref>{{citation\|title=Graph Algorithms in the Language of Linear Algebra\|volume=22\|series=Software, Environments, and Tools\|first1=Jeremy\|last1=Kepner\|first2=John\|last2=Gilbert\|publisher=[[Society for Industrial and Applied Mathematics]]\|year=2011\|isbn=9780898719901\|page=55\|url=https://books.google.com/books?id=JBXDc83jRBwC&pg=PA55}}.</ref> In terms of their asymptotic [[time complexity]], these three algorithms are equally fast for [[sparse graph]]s, but slower than other more sophisticated algorithms.<ref name="pr02"/><ref name="chertar"/>		Other well-known algorithms for this problem include [[Kruskal's algorithm]] and [[Borůvka's algorithm]].<ref>{{citation\|first=Robert Endre\|last=Tarjan\|author-link=Robert Tarjan\|title=Data Structures and Network Algorithms\|series=CBMS-NSF Regional Conference Series in Applied Mathematics\|volume=44\|publisher=[[Society for Industrial and Applied Mathematics]]\|year=1983\|contribution=Chapter 6. Minimum spanning trees. 6.2. Three classical algorithms\|pages=72–77}}.</ref> These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected graphs. However, running Prim's algorithm separately for each [[Connected component (graph theory)\|connected component]] of the graph, it can also be used to find the minimum spanning forest.<ref>{{citation\|title=Graph Algorithms in the Language of Linear Algebra\|volume=22\|series=Software, Environments, and Tools\|first1=Jeremy\|last1=Kepner\|first2=John\|last2=Gilbert\|publisher=[[Society for Industrial and Applied Mathematics]]\|year=2011\|isbn=9780898719901\|page=55\|url=https://books.google.com/books?id=JBXDc83jRBwC&pg=PA55}}.</ref> In terms of their asymptotic [[time complexity]], these three algorithms are equally fast for [[sparse graph]]s, but slower than other more sophisticated algorithms.<ref name="pr02"/><ref name="chertar"/>
	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.<ref name="tarjan83p77">{{harvtxt\|Tarjan\|1983}}, p. 77.</ref>		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.<ref name="tarjan83p77">{{harvtxt\|Tarjan\|1983}}, p. 77.</ref>

186.185.247.155: fails

2025-03-27T12:17:13Z

fails

← Previous revision		Revision as of 12:17, 27 March 2025
Line 70:		Line 70:
	}}.</ref>		}}.</ref>

	Other well-known algorithms for this problem include [[Kruskal's algorithm]] and [[Borůvka's algorithm]].<ref>{{citation\|first=Robert Endre\|last=Tarjan\|author-link=Robert Tarjan\|title=Data Structures and Network Algorithms\|series=CBMS-NSF Regional Conference Series in Applied Mathematics\|volume=44\|publisher=[[Society for Industrial and Applied Mathematics]]\|year=1983\|contribution=Chapter 6. Minimum spanning trees. 6.2. Three classical algorithms\|pages=72–77}}.</ref> These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected ~~graphs.~~ However, running Prim's algorithm separately for each [[Connected component (graph theory)\|connected component]] of the graph, it can also be used to find the minimum spanning forest.<ref>{{citation\|title=Graph Algorithms in the Language of Linear Algebra\|volume=22\|series=Software, Environments, and Tools\|first1=Jeremy\|last1=Kepner\|first2=John\|last2=Gilbert\|publisher=[[Society for Industrial and Applied Mathematics]]\|year=2011\|isbn=9780898719901\|page=55\|url=https://books.google.com/books?id=JBXDc83jRBwC&pg=PA55}}.</ref> In terms of their asymptotic [[time complexity]], these three algorithms are equally fast for [[sparse graph]]s, but slower than other more sophisticated algorithms.<ref name="pr02"/><ref name="chertar"/>		Other well-known algorithms for this problem include [[Kruskal's algorithm]] and [[Borůvka's algorithm]].<ref>{{citation\|first=Robert Endre\|last=Tarjan\|author-link=Robert Tarjan\|title=Data Structures and Network Algorithms\|series=CBMS-NSF Regional Conference Series in Applied Mathematics\|volume=44\|publisher=[[Society for Industrial and Applied Mathematics]]\|year=1983\|contribution=Chapter 6. Minimum spanning trees. 6.2. Three classical algorithms\|pages=72–77}}.</ref> These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected teacher de las notas porfa However, running Prim's algorithm separately for each [[Connected component (graph theory)\|connected component]] of the graph, it can also be used to find the minimum spanning forest.<ref>{{citation\|title=Graph Algorithms in the Language of Linear Algebra\|volume=22\|series=Software, Environments, and Tools\|first1=Jeremy\|last1=Kepner\|first2=John\|last2=Gilbert\|publisher=[[Society for Industrial and Applied Mathematics]]\|year=2011\|isbn=9780898719901\|page=55\|url=https://books.google.com/books?id=JBXDc83jRBwC&pg=PA55}}.</ref> In terms of their asymptotic [[time complexity]], these three algorithms are equally fast for [[sparse graph]]s, but slower than other more sophisticated algorithms.<ref name="pr02"/><ref name="chertar"/>
	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.<ref name="tarjan83p77">{{harvtxt\|Tarjan\|1983}}, p. 77.</ref>		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.<ref name="tarjan83p77">{{harvtxt\|Tarjan\|1983}}, p. 77.</ref>

David Eppstein: Undid revision 1274876761 by 2601:647:C900:EEE0:74E4:B146:663B:F22D (talk) oversimplified

2025-02-09T21:02:30Z

Undid revision 1274876761 by 2601:647:C900:EEE0:74E4:B146:663B:F22D (talk) oversimplified

← Previous revision		Revision as of 21:02, 9 February 2025
Line 78:		Line 78:
	The algorithm may informally be described as performing the following steps:		The algorithm may informally be described as performing the following steps:
	{{ordered list		{{ordered list
	\| Initialize a tree with a single vertex, chosen arbitrarily from the graph.		\| Initialize a tree with a single vertex, chosen arbitrarily from the graph.
	\| ~~Find~~ ~~and~~ ~~add~~ ~~the~~ edge ~~with~~ the ~~lowest~~ weight to tree.		\| Grow the tree by one edge: Of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
	\| Repeat step 2 (until all vertices are in the tree).		\| Repeat step 2 (until all vertices are in the tree).
	}}		}}

2601:647:C900:EEE0:74E4:B146:663B:F22D: /* Description */

2025-02-09T19:28:40Z

Description

← Previous revision		Revision as of 19:28, 9 February 2025
Line 78:		Line 78:
	The algorithm may informally be described as performing the following steps:		The algorithm may informally be described as performing the following steps:
	{{ordered list		{{ordered list
	\| Initialize a tree with a single vertex, chosen arbitrarily from the graph.		\| Initialize a tree with a single vertex, chosen arbitrarily from the graph.
	\| ~~Grow~~ ~~the~~ ~~tree~~ ~~by one~~ edge: Of the ~~edges~~ ~~that connect the tree to vertices not yet in the tree, find the minimum-~~weight ~~edge, and transfer it~~ to ~~the~~ tree.		\| Find and add the edge with the lowest weight to tree.
	\| Repeat step 2 (until all vertices are in the tree).		\| Repeat step 2 (until all vertices are in the tree).
	}}		}}

Citation bot: Added publisher. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Graph algorithms | #UCB_Category 81/132

2024-10-25T14:54:51Z

Added publisher. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Graph algorithms | #UCB_Category 81/132

← Previous revision		Revision as of 14:54, 25 October 2024
Line 145:		Line 145:
	[[File:Distributed adjacency matrix for parallel prim.png\|thumb\|The adjacency matrix distributed between multiple processors for parallel Prim's algorithm. In each iteration of the algorithm, every processor updates its part of ''C'' by inspecting the row of the newly inserted vertex in its set of columns in the adjacency matrix. The results are then collected and the next vertex to include in the MST is selected globally.]]		[[File:Distributed adjacency matrix for parallel prim.png\|thumb\|The adjacency matrix distributed between multiple processors for parallel Prim's algorithm. In each iteration of the algorithm, every processor updates its part of ''C'' by inspecting the row of the newly inserted vertex in its set of columns in the adjacency matrix. The results are then collected and the next vertex to include in the MST is selected globally.]]

	The main loop of Prim's algorithm is inherently sequential and thus not [[parallel algorithm\|parallelizable]]. However, the [[#step3c\|inner loop]], which determines the next edge of minimum weight that does not form a cycle, can be parallelized by dividing the vertices and edges between the available processors.<ref name="grama2003">{{citation\|title=Introduction to Parallel Computing\|last1=Grama\|first1=Ananth\|last2=Gupta\|first2=Anshul\|last3=Karypis\|first3=George\|last4=Kumar\|first4=Vipin\|year=2003\|isbn=978-0201648652\|pages=444–446}}</ref> The following [[pseudocode]] demonstrates this.		The main loop of Prim's algorithm is inherently sequential and thus not [[parallel algorithm\|parallelizable]]. However, the [[#step3c\|inner loop]], which determines the next edge of minimum weight that does not form a cycle, can be parallelized by dividing the vertices and edges between the available processors.<ref name="grama2003">{{citation\|title=Introduction to Parallel Computing\|last1=Grama\|first1=Ananth\|last2=Gupta\|first2=Anshul\|last3=Karypis\|first3=George\|last4=Kumar\|first4=Vipin\|year=2003\|isbn=978-0201648652\|pages=444–446\|publisher=Addison-Wesley }}</ref> The following [[pseudocode]] demonstrates this.

	{{ordered list		{{ordered list

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:57:40Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:57, 12 October 2024
Line 176:		Line 176:
	{{Graph traversal algorithms}}		{{Graph traversal algorithms}}

	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]
	[[Category:Spanning tree]]		[[Category:Spanning tree]]
	[[Category:Articles containing proofs]]		[[Category:Articles containing proofs]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:24:52Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:24, 12 October 2024
Line 176:		Line 176:
	{{Graph traversal algorithms}}		{{Graph traversal algorithms}}

	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]
	[[Category:Spanning tree]]		[[Category:Spanning tree]]
	[[Category:Articles containing proofs]]		[[Category:Articles containing proofs]]

LehAn02: /* "smaller" changed to "larger" because expanded into a smaller subset is paradoxical (see "expand"’s meaning and "small"’s meaning) */

2024-07-23T05:14:22Z

"smaller" changed to "larger" because expanded into a smaller subset is paradoxical (see "expand"’s meaning and "small"’s meaning)

← Previous revision		Revision as of 05:14, 23 July 2024
Line 140:		Line 140:
	:<math>w(f) \ge w(e).</math>		:<math>w(f) \ge w(e).</math>

	Let tree ''Y<sub>2</sub>'' be the graph obtained by removing edge ''f'' from and adding edge ''e'' to tree ''Y<sub>1</sub>''. It is easy to show that tree ''Y<sub>2</sub>'' is connected, has the same number of edges as tree ''Y<sub>1</sub>'', and the total weights of its edges is not larger than that of tree ''Y<sub>1</sub>'', therefore it is also a minimum spanning tree of graph ''P'' and it contains edge ''e'' and all the edges added before it during the construction of set ''V''. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph ''P'' that is identical to tree ''Y''. This shows ''Y'' is a minimum spanning tree. The minimum spanning tree allows for the first subset of the sub-region to be expanded into a ~~smaller~~ subset ''X'', which we assume to be the minimum.		Let tree ''Y<sub>2</sub>'' be the graph obtained by removing edge ''f'' from and adding edge ''e'' to tree ''Y<sub>1</sub>''. It is easy to show that tree ''Y<sub>2</sub>'' is connected, has the same number of edges as tree ''Y<sub>1</sub>'', and the total weights of its edges is not larger than that of tree ''Y<sub>1</sub>'', therefore it is also a minimum spanning tree of graph ''P'' and it contains edge ''e'' and all the edges added before it during the construction of set ''V''. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph ''P'' that is identical to tree ''Y''. This shows ''Y'' is a minimum spanning tree. The minimum spanning tree allows for the first subset of the sub-region to be expanded into a larger subset ''X'', which we assume to be the minimum.

	== Parallel algorithm ==		== Parallel algorithm ==