Editing Minimum spanning tree (section)

=== Classic algorithms ===
The first algorithm for finding a minimum spanning tree was developed by Czech scientist [[Otakar Borůvka]] in 1926 (see [[Borůvka's algorithm]]). Its purpose was an efficient electrical coverage of [[Moravia]].  The algorithm proceeds in a sequence of stages. In each stage, called ''Boruvka step'', it identifies a forest {{mvar|F}} consisting of the minimum-weight edge incident to each vertex in the graph {{mvar|G}}, then forms the graph {{math|1=''G''{{sub|1}} = ''G'' \ ''F''}} as the input to the next step. Here {{math|''G'' \ ''F''}} denotes the graph derived from {{mvar|G}} by contracting edges in {{mvar|F}} (by the [[#Cut property|Cut property]], these edges belong to the MST). Each Boruvka step takes linear time. Since the number of vertices is reduced by at least half in each step, Boruvka's algorithm takes {{math|''O''(''m'' log ''n'')}} time.<ref name=PettieRamachandran2002/>

A second algorithm is [[Prim's algorithm]], which was invented by [[Vojtěch Jarník]] in 1930 and rediscovered by [[Robert C. Prim|Prim]] in 1957 and [[Edsger W. Dijkstra|Dijkstra]] in 1959. Basically, it grows the MST ({{mvar|T}}) one edge at a time. Initially, {{mvar|T}} contains an arbitrary vertex. In each step, {{mvar|T}} is augmented with a least-weight edge {{math|(''x'',''y'')}} such that {{mvar|x}} is in {{mvar|T}} and {{mvar|y}} is not yet in {{mvar|T}}. By the [[#Cut property|Cut property]], all edges added to {{mvar|T}} are in the MST. Its run-time is either {{math|''O''(''m'' log ''n'')}} or {{math|''O''(''m'' + ''n'' log ''n'')}}, depending on the data-structures used.

A third algorithm commonly in use is [[Kruskal's algorithm]], which also takes {{math|''O''(''m'' log ''n'')}} time.

A fourth algorithm, not as commonly used, is the [[reverse-delete algorithm]], which is the reverse of Kruskal's algorithm. Its runtime is {{math|O(''m'' log ''n'' (log log ''n''){{sup|3}})}}.

All four of these are [[greedy algorithm]]s. Since they run in polynomial time, the problem of finding such trees is in '''[[FP (complexity)|FP]]''', and related [[decision problem]]s such as determining whether a particular edge is in the MST or determining if the minimum total weight exceeds a certain value are in '''[[P (complexity)|P]]'''.