Kruskal's Algorithm - Revision history

Rice: /* Kruskal's Algorithm */

2024-03-20T18:06:48Z

Kruskal's Algorithm

← Older revision		Revision as of 18:06, 20 March 2024
Line 1:		Line 1:
	{{Infobox Algorithm\|runtime=O(E log E)\|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}}~~<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">~~		{{Infobox Algorithm\|runtime=O(E log E)\|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}}
	~~== Kruskal's Algorithm ==~~
	~~</aside><span></span>~~

	= Approach: Greedy =		= Approach: Greedy =
	The approach is to try to add the smallest edges as long as they do not create a cycle. Unlike [[Prims Algorithm\|Prim's algorithm]], which prevents cycles by only choosing edges that crosses a cut of nodes already in the tree and nodes that aren't, Kruskal prevents cycles using a data structure known as disjoint set (aka. union-find).		The approach is to try to add the smallest edges as long as they do not create a cycle. Unlike [[Prims Algorithm\|Prim's algorithm]], which prevents cycles by only choosing edges that crosses a cut of nodes already in the tree and nodes that aren't, Kruskal prevents cycles using a data structure known as disjoint set (aka. union-find).

2024-03-20T18:06:24Z

← Older revision		Revision as of 18:06, 20 March 2024
Line 1:		Line 1:
	{{Infobox Algorithm\|runtime=~~Sort +~~ E ~~cycle? + (V - 1~~) ~~adding-edge~~\|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}}		{{Infobox Algorithm\|runtime=O(E log E)\|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}}<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">
			== Kruskal's Algorithm ==
			</aside><span></span>

	= Approach: Greedy =		= Approach: Greedy =

2024-03-20T18:06:00Z

Analysis

← Older revision		Revision as of 18:06, 20 March 2024
Line 28:		Line 28:

	Sort edges + E (cycle?) + (V - 1) adding edge		Sort edges + E (cycle?) + (V - 1) adding edge

			Disjoint set allows O(log V) cycle checking and O(log V) edge adding.

	Sorting takes E log E		Sorting takes E log E

2024-03-20T18:05:05Z

Analysis

@@ Line 9: / Line 9: @@
 OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E )
 </math>
 = Analysis =

2024-03-20T18:00:32Z

Approach: Greedy

← Older revision		Revision as of 18:00, 20 March 2024
Line 2:		Line 2:

	= Approach: Greedy =		= Approach: Greedy =
	The approach is to try to add the smallest edges as long as they do not create a cycle. Unlike [[Prims Algorithm\|Prim's algorithm]], which prevents cycles by only choosing edges that crosses a cut of nodes already in the tree and nodes that aren't, Kruskal prevents cycles using a data structure known as union-find.		The approach is to try to add the smallest edges as long as they do not create a cycle. Unlike [[Prims Algorithm\|Prim's algorithm]], which prevents cycles by only choosing edges that crosses a cut of nodes already in the tree and nodes that aren't, Kruskal prevents cycles using a data structure known as disjoint set (aka. union-find).

	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:59:57Z

Approach: Greedy

← Older revision		Revision as of 17:59, 20 March 2024
Line 2:		Line 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. Unlike [[Prims Algorithm\|Prim's algorithm]], which prevents cycles by only choosing edges that crosses a cut of nodes already in the tree and nodes that aren't, Kruskal prevents cycles using a data structure known as union-find.

	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:42:28Z

Approach

← Older revision		Revision as of 17:42, 20 March 2024
Line 1:		Line 1:
	{{Infobox Algorithm\|runtime=Sort + E cycle? + (V - 1) adding-edge\|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}}		{{Infobox Algorithm\|runtime=Sort + E cycle? + (V - 1) adding-edge\|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}}
	~~= Approach =~~

	~~Select~~ edges ~~in order~~ of ~~smallest to largest~~, ~~using disjoint~~-~~sets~~ to		= Approach: Greedy =
	~~prevent cycles.~~		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>

			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.

			<math>
			OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E )
			</math>

	= Analysis =		= Analysis =

2024-03-13T00:06:46Z

← Older revision		Revision as of 00:06, 13 March 2024
Line 14:		Line 14:

	For fast-find, where all members have the same ID, fast-set-id needs O(1) and union needs O(n)		For fast-find, where all members have the same ID, fast-set-id needs O(1) and union needs O(n)

			[[Category:Algorithms]]

2024-03-13T00:03:29Z

← Older revision		Revision as of 00:03, 13 March 2024
Line 1:		Line 1:
	{{Infobox Algorithm\|runtime=Sort + E cycle? + (V - 1) adding-edge\|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}}~~<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">~~		{{Infobox Algorithm\|runtime=Sort + E cycle? + (V - 1) adding-edge\|class=[[Minimum Spanning Tree]], [[Greedy Algorithm]]}}
	~~== Kruskal's Algorithm ==~~
	~~</aside><span></span>~~

	= Approach =		= Approach =

2024-03-13T00:02:44Z

Analysis

← Older revision		Revision as of 00:02, 13 March 2024
Line 15:		Line 15:

	For weighted disjoint set, checking cycle takes log V, and adding edge takes log V		For weighted disjoint set, checking cycle takes log V, and adding edge takes log V

			For fast-find, where all members have the same ID, fast-set-id needs O(1) and union needs O(n)