_Anim.gif)
Borůvka's algorithm
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,or a minimum spanning forest in the case of a graph that is not connected. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia.The algorithm was rediscovered by Choquet in 1938; again by , Łukasiewicz, , Steinhaus, and in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature.
- Comment
- enBorůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,or a minimum spanning forest in the case of a graph that is not connected. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia.The algorithm was rediscovered by Choquet in 1938; again by , Łukasiewicz, , Steinhaus, and in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature.
- Depiction
- Has abstract
- enBorůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,or a minimum spanning forest in the case of a graph that is not connected. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia.The algorithm was rediscovered by Choquet in 1938; again by , Łukasiewicz, , Steinhaus, and in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature. The algorithm begins by finding the minimum-weight edge incident to each vertex of the graph, and adding all of those edges to the forest.Then, it repeats a similar process of finding the minimum-weight edge from each tree constructed so far to a different tree, and adding all of those edges to the forest.Each repetition of this process reduces the number of trees, within each connected component of the graph, to at most half of this former value,so after logarithmically many repetitions the process finishes. When it does, the set of edges it has added forms the minimum spanning forest.
- Hypernym
- Algorithm
- Is primary topic of
- Borůvka's algorithm
- Label
- enBorůvka's algorithm
- Link from a Wikipage to another Wikipage
- Ackermann function
- Bernard Chazelle
- Big O notation
- Category:Articles with example pseudocode
- Category:Graph algorithms
- Category:Spanning tree
- Component (graph theory)
- Electricity network
- File:Boruvka's algorithm (Sollin's algorithm) Anim.gif
- File:Borůvka Algorithm 1.svg
- File:Borůvka Algorithm 2.svg
- File:Borůvka Algorithm 3.svg
- Graph minor
- Greedy algorithm
- Gustave Choquet
- Hugo Steinhaus
- Jan Łukasiewicz
- Julian Perkal
- Kazimierz Florek
- Kruskal's algorithm
- Memory address
- Minimum spanning tree
- Moravia
- Otakar Borůvka
- Parallel computing
- Planar graph
- Prim's algorithm
- Stefan Zubrzycki
- Total order
- SameAs
- Algorithme de Borůvka
- Algorithmus von Borůvka
- Algoritmo de Boruvka
- Algoritmo de Borůvka
- Algoritmo di Borůvka
- Algorytm Borůvki
- Boruvka algoritam
- Borůvka-algoritmus
- Borůvkův algoritmus
- m.01c0p6
- Q1468211
- Thuật toán Borůvka
- U58E
- Алгоритм Борувки
- Алгоритм Борувки
- الگوریتم بروکا
- ขั้นตอนวิธีของโบรุฟกา
- ブルーフカ法
- Subject
- Category:Articles with example pseudocode
- Category:Graph algorithms
- Category:Spanning tree
- Thumbnail
_Anim.gif?width=300)
- WasDerivedFrom
- Borůvka's algorithm?oldid=1083605866&ns=0
- WikiPageLength
- 10925
- Wikipage page ID
- 197253
- Wikipage revision ID
- 1083605866
- WikiPageUsesTemplate
- Template:Math
- Template:Short description
