Kruskal's algorithm
Sign in to saveminimum spanning forest algorithm that greedily adds edges
Key facts
- Class
- Minimum spanning tree algorithm
- Data structure
- Graph
- Worst case performance
- O ( | E | log | V | ) {\displaystyle O(|E|\log |V|)}
via Wikipedia infobox
Wikidata facts
- Image
- MST kruskal en.gif
Show 3 more facts
- Commons category
- Kruskal's algorithm
- Stack Exchange tag
- stackoverflow.com/tags/kruskals-algorithm
- publication date
- 1956-00-00
Sources (2)
via Wikidata · CC0
~9 min read
Article
Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. It is a greedy algorithm that in each step adds to the forest the lowest-weight edge that will not form a cycle. The key steps of the algorithm are sorting and the use of a disjoint-set data structure to detect cycles. Its running time is dominated by the time to sort all of the graph edges by their weight.
A minimum spanning tree of a connected weighted graph is a connected subgraph, without cycles, for which the sum of the weights of all the edges in the subgraph is minimal. For a disconnected graph, a minimum spanning forest is composed of a minimum spanning tree for each connected component.