Kruskal's algorithm

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, Reverse-Delete 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 V2 and logV2 = 2logV \; is O(log V).
  • If we ignore isolated vertices, which will each be their own component of the minimum spanning forest, VE+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
Well-order
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