
related topics 
{math, number, function} 
{@card@, make, design} 
{line, north, south} 
{style, bgcolor, rowspan} 
{island, water, area} 

Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. 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). Kruskal's algorithm is an example of a greedy algorithm.
This algorithm first appeared in Proceedings of the American Mathematical Society, pp. 48–50 in 1956, and was written by Joseph Kruskal.
Other algorithms for this problem include Prim's algorithm, ReverseDelete algorithm, and Borůvka's algorithm.
Contents
Description
 create a forest F (a set of trees), where each vertex in the graph is a separate tree
 create a set S containing all the edges in the graph
 while S is nonempty and F is not yet spanning
 remove an edge with minimum weight from S
 if that edge connects two different trees, then add it to the forest, combining two trees into a single tree
 otherwise discard that edge.
At the termination of the algorithm, the forest has only one component and forms a minimum spanning tree of the graph.
Performance
Where E is the number of edges in the graph and V is the number of vertices, Kruskal's algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time, all with simple data structures. These running times are equivalent because:
 E is at most V^{2} and logV^{2} = 2logV is O(log V).
 If we ignore isolated vertices, which will each be their own component of the minimum spanning forest, V ≤ E+1, so log V is O(log E).
Full article ▸


related documents 
Euler's totient function 
Convex set 
Symmetric group 
Local ring 
Golomb coding 
Carmichael number 
Group representation 
Goodstein's theorem 
Controllability 
Search algorithm 
Wellorder 
Division algebra 
Constant of integration 
Analytic geometry 
Diophantine set 
Exact sequence 
Mersenne twister 
Lebesgue measure 
Mersenne prime 
Kolmogorov space 
Separable space 
Laurent series 
Probability space 
Automated theorem proving 
Cartesian product 
Linear equation 
Banach fixed point theorem 
Inverse limit 
Axiom of regularity 
Conjunctive normal form 
