Difference between revisions of "Kruskal's algorithm"
From Wiki @ Karl Jones dot com
Karl Jones (Talk | contribs) |
Karl Jones (Talk | contribs) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 5: | Line 5: | ||
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. | ||
| − | 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. | * 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]] | * [[Algorithm]] | ||
| + | * [[Graph theory]] | ||
* [[Maze generation algorithm]] | * [[Maze generation algorithm]] | ||
| Line 19: | 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]] | ||
Latest revision as of 07:14, 25 April 2016
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.
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
External links
- Kruskal's algorithm @ Wikipedia1
