Kruskal's algorithm - Revision history

Karl Jones at 14:14, 25 April 2016

2016-04-25T14:14:13Z

Karl Jones at 13:28, 8 February 2016

2016-02-08T13:28:53Z

Karl Jones at 13:28, 8 February 2016

2016-02-08T13:28:27Z

Karl Jones: Algorithm

2015-08-11T00:18:44Z

Algorithm

Karl Jones: first

2015-08-11T00:18:18Z

first

New page

'''Kruskal's algorithm''' is a minimum-spanning-tree [[algorithm]].

The algorithm finds an edge of the least possible weight that connects any two trees in the forest.

It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

* This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

== See also ==

* [[Maze generation algorithm]]

== External links ==

* [https://en.wikipedia.org/wiki/Kruskal%27s_algorithm Kruskal's algorithm] @ Wikipedia1

← Older revision		Revision as of 14:14, 25 April 2016
Line 20:		Line 20:

	* [https://en.wikipedia.org/wiki/Kruskal%27s_algorithm Kruskal's algorithm] @ Wikipedia1		* [https://en.wikipedia.org/wiki/Kruskal%27s_algorithm Kruskal's algorithm] @ Wikipedia1
		+
		+	[[Category:Algorithms]]
		+	[[Category:Computing]]
		+	[[Category:Mathematics]]

← Older revision		Revision as of 13:28, 8 February 2016
Line 1:		Line 1:
	'''Kruskal's algorithm''' is a minimum-spanning-tree [[algorithm]].		'''Kruskal's algorithm''' is a minimum-spanning-tree [[algorithm]].
		+
		+	== Description ==

	The algorithm finds an edge of the least possible weight that connects any two trees in the forest.		The algorithm finds an edge of the least possible weight that connects any two trees in the forest.

← Older revision		Revision as of 00:18, 11 August 2015
Line 11:		Line 11:
	== See also ==		== See also ==

		+	* [[Algorithm]]
	* [[Maze generation algorithm]]		* [[Maze generation algorithm]]

@@ Line 5: / Line 5: @@
 The algorithm finds an edge of the least possible weight that connects any two trees in the forest.
-It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
+It is a greedy algorithm in [[graph theory]] as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
 * This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
@@ Line 14: / Line 14: @@
 * [[Algorithm]]
 * [[Maze generation algorithm]]