Prims Algorithm - Revision history

Rice: /* Analysis */

2024-03-20T17:56:17Z

Analysis

← Older revision		Revision as of 17:56, 20 March 2024
Line 26:		Line 26:

	= Analysis =		= Analysis =
	~~Priority~~ queue is slower than array when the graph is dense~~, so sometimes it's better to use Dijsktra's algorithm~~.		Initialization takes O(V). Walk through is O(V + E).

			During the walk through, the minimum edge is extracted V times, and the edge priority queue is updated E times. Depending on the data structure used, the runtime is different.

			* For an ''array'', the extraction takes O(V) and the update takes O(1). The overall runtime is O(V^2)
			* For a ''heap'', the extraction takes O(logV) and the update takes O(logV). The overall runtime is O(E logV).

			As such, priority queue is slower than array when the graph is dense (where E approaches V^2).

	= Proof: Greedy =		= Proof: Greedy =

2024-03-20T17:47:53Z

Approach: Greedy

← Older revision		Revision as of 17:47, 20 March 2024
Line 1:		Line 1:
	{{Infobox Algorithm\|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]\| runtime=V*Extract_min + V + E + E update <br> Heap: O(E log V) <br> Array: O(V^2)}}		{{Infobox Algorithm\|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]\| runtime=V*Extract_min + V + E + E update <br> Heap: O(E log V) <br> Array: O(V^2)}}
	== Approach: Greedy ==		== Approach: Greedy ==
	The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of <math>T</math> vs. <math>V - T</math>		The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of <math>T</math> vs. <math>V - T</math>. Unlike [[Dijkstra's Algorithm\|Dijkstra's algorithm]], the weight of the crossing edge is directly considered (as opposed to the distance from the source node).

	Given the MST of <math>V_{n - m} = v_1, v_2, \ldots, v_{ n - m} </math>, the MST of <math>V</math> should be that of <math>V_{n-1}</math> plus the edge that connects to <math>v_n</math> that is the shortest.		Given the MST of <math>V_{n - m} = v_1, v_2, \ldots, v_{ n - m} </math>, the MST of <math>V</math> should be that of <math>V_{n-1}</math> plus the edge that connects to <math>v_n</math> that is the shortest.

2024-03-20T17:41:08Z

Approach: Greedy

← Older revision		Revision as of 17:41, 20 March 2024
Line 1:		Line 1:
	{{Infobox Algorithm\|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]\| runtime=V*Extract_min + V + E + E update <br> Heap: O(E log V) <br> Array: O(V^2)}}		{{Infobox Algorithm\|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]\| runtime=V*Extract_min + V + E + E update <br> Heap: O(E log V) <br> Array: O(V^2)}}
			== Approach: Greedy ==
			The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of <math>T</math> vs. <math>V - T</math>

	= ~~Approach: Greedy~~ =		Given the MST of <math>V_{n - m} = v_1, v_2, \ldots, v_{ n - m} </math>, the MST of <math>V</math> should be that of <math>V_{n-1}</math> plus the edge that connects to <math>v_n</math> that is the shortest.
	~~See [[Minimum_Spanning_Tree]]~~
			<math>
			OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E )
			</math>

	= Implementation =		= Implementation =

2024-03-12T23:54:33Z

← Older revision		Revision as of 23:54, 12 March 2024
Line 1:		Line 1:
	{{Infobox Algorithm\|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]\|runtime=V*Extract_min + V + E + E update <br> Heap: O(E log V) <br> Array: O(V^2)}}~~<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">~~		{{Infobox Algorithm\|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]\| runtime=V*Extract_min + V + E + E update <br> Heap: O(E log V) <br> Array: O(V^2)}}
	~~== Prims Algorithm ==~~
	~~</aside><span></span>~~

	= Approach: Greedy =		= Approach: Greedy =

2024-03-12T23:52:19Z

← Older revision		Revision as of 23:52, 12 March 2024
Line 1:		Line 1:
	{{Infobox Algorithm\|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]\|runtime=Heap: O(E log V) <br> Array: O(V^2)}}		{{Infobox Algorithm\|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]\|runtime=V*Extract_min + V + E + E update <br> Heap: O(E log V) <br> Array: O(V^2)}}<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">
			== Prims Algorithm ==
			</aside><span></span>

	= Approach: Greedy =		= Approach: Greedy =

2024-03-08T01:39:09Z

@@ Line 32: / Line 32: @@
 smallest edge that crosses the cut from <math>A = r</math> and <math>V -
 r</math>.
 [[Category:Algorithms]]

2024-03-08T01:34:38Z

← Older revision		Revision as of 01:34, 8 March 2024
Line 24:		Line 24:

	= Proof: Greedy =		= Proof: Greedy =

			'''Greeedy strategy:''' Let the greedy choice be the edge that is
			smallest that crosses the cut between <math>A</math> and <math>V -
			A</math>.

			'''Name greedy choice:''' let <math>r \rightarrow x</math> be the
			smallest edge that crosses the cut from <math>A = r</math> and <math>V -
			r</math>.

	[[Category:Algorithms]]		[[Category:Algorithms]]

2024-03-08T01:29:02Z

← Older revision		Revision as of 01:29, 8 March 2024
Line 24:		Line 24:

	= Proof: Greedy =		= Proof: Greedy =

	~~== Suboptimality ==~~

	~~Given MST tree for the graph G~~

	~~<math>~~
	~~OPT = \text{set of edges}~~
	~~</math>~~

	~~where the number of edges is <math>n - 1</math>, the weight of edges is~~
	~~minimum, and the tree is spanning.~~

	~~Consider <math>(x,y)</math>, where X is a leaf node.~~

	~~Prove that <math>A = OPT - (x, y)</math> is a MST for the subproblem~~
	~~<math>G - X</math>~~

	~~By contradiction, assume that <math>A</math> is not optimal. There must~~
	~~be <math>B</math> such that~~

	~~<math>~~
	~~w(B) < w(A)~~
	~~</math>~~

	~~Adding the edge (x, y) back to both graphs~~

	~~<math>B + (x, y)</math> is a viable tree.~~

	~~<math>~~
	~~w(B + w(x,y)) < w(A + w(x,y)) = w(OPT)~~
	~~</math>~~

	~~Therefore, OPT is not the optimal solution.~~

	~~By contradiction, <math>A</math> must be optimal.~~


	[[Category:Algorithms]]		[[Category:Algorithms]]

2024-03-08T01:24:36Z

← Older revision		Revision as of 01:24, 8 March 2024
Line 48:		Line 48:
	</math>		</math>

	Adding the edge (x, y) back to both graphs, ~~we have~~		Adding the edge (x, y) back to both graphs

			<math>B + (x, y)</math> is a viable tree.

	<math>		<math>

2024-03-08T01:23:19Z