**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).

It works as follows:

- 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- 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

- remove an edge with minimum weight from

With the use of a suitable data structure, Kruskal's algorithm can be shown to run in O (m log m) time, where m is the number of edges in the graph.

Let *P* be a connected, weighted graph and let *Y* be the subgraph of *P* produced by the algorithm. *Y* cannot have a cycle, since the last edge added to that cycle would have been within one subtree and not between two different trees. *Y* cannot be disconnected, since the first encountered edge that joins two components of *Y* would have been added by the algorithm. Thus, *Y* is a spanning tree of *P*.

Let *Y _{1}* be a minimum spanning tree for

Other algorithms for this problem include Prim's algorithm, and Boruvka's algorithm.