Editing Kruskal's algorithm (section)

{{short description|Minimum spanning forest algorithm that greedily adds edges}}
{{Distinguish|Kruskal's principle}}
{{Infobox Algorithm
|image=[[File:KruskalDemo.gif|frameless|upright=1.35]]
|caption=Animation of Kruskal's algorithm on a [[complete graph]] with weights based on Euclidean distance
|class=[[Minimum spanning tree|Minimum spanning tree algorithm]]
|data=[[Graph (abstract data type)|Graph]]
|time=<math>O(|E|\log |V|)</math>
}}
'''Kruskal's algorithm'''<ref>{{Cite book |last=Kleinberg |first=Jon |url=https://www.worldcat.org/oclc/57422612 |title=Algorithm design |date=2006 |publisher=Pearson/Addison-Wesley |others=Éva Tardos |isbn=0-321-29535-8 |location=Boston |pages=142–151 |oclc=57422612}}</ref> finds a [[minimum spanning tree|minimum spanning forest]] of an undirected [[weighted graph|edge-weighted graph]]. If the graph is [[Connectivity (graph theory)|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 (graph theory)|cycle]].<ref name=":0">{{Cite book|last1=Cormen|first1=Thomas|url=https://archive.org/details/introductiontoal00corm_805|title=Introduction To Algorithms|last2=Charles E Leiserson, Ronald L Rivest, Clifford Stein|publisher=MIT Press|year=2009|isbn=978-0262258104|edition=Third|pages=[https://archive.org/details/introductiontoal00corm_805/page/n651 631]|url-access=limited}}</ref> 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 (graph theory)|connected component]].

This algorithm was first published by [[Joseph Kruskal]] in 1956,<ref>{{Cite journal | last1 = Kruskal | first1 = J. B. | author-link1 = Joseph Kruskal| doi = 10.1090/S0002-9939-1956-0078686-7 | title = On the shortest spanning subtree of a graph and the traveling salesman problem | journal = [[Proceedings of the American Mathematical Society]] | volume = 7 | issue = 1 | pages = 48–50 | year = 1956| jstor = 2033241| doi-access = free }}</ref> and was rediscovered soon afterward by {{harvtxt|Loberman|Weinberger|1957}}.<ref>{{cite journal | last1 = Loberman | first1 = H. | last2 = Weinberger | first2 = A. | date = October 1957 | doi = 10.1145/320893.320896 | issue = 4 | journal = Journal of the ACM | pages = 428–437 | title = Formal Procedures for connecting terminals with a minimum total wire length | volume = 4| s2cid = 7320964 | doi-access = free }}</ref> Other algorithms for this problem include [[Prim's algorithm]], [[Borůvka's algorithm]], and the [[reverse-delete algorithm]].