Kruskal's algorithm
From Wiki @ Karl Jones dot com
Revision as of 07:14, 25 April 2016 by Karl Jones (Talk | contribs)
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
