Borůvka's algorithm

animation

The borůvka's algorithm is considered the first algorithm for finding minimum spanning trees in undirected graphs . It was described in 1926 by the Czech mathematician Otakar Borůvka . The two better known algorithms for solving this problem are the Prim's algorithm and the Kruskal's algorithm . Borůvka is mentioned in the first publication of these two algorithms.

Basic principle and complexity

Borůvka's algorithm uses the cutting property of minimal spanning trees. In each round the lightest outgoing edge of each node is selected and the graph is contracted along these edges. The two nodes that are incident to form a contracted edge merge into one node. The minimal spanning tree consists of exactly the contracted edges. If implemented skillfully, each round takes time in . Since the number of remaining components is halved in each round, there is a sequential running time in . ${\displaystyle O(|E|)}$ ${\displaystyle O(|E|\log |V|)}$

  ${\displaystyle T\gets \emptyset }$
 solange  ${\displaystyle |V|>0}$
    ${\displaystyle S\gets \emptyset }$
   für alle  ${\displaystyle v\in V}$
      ${\displaystyle S\gets S}$  ${\displaystyle \cup }$ leichteste Kante  ${\displaystyle \{u,v\}\in E}$
   für alle  ${\displaystyle \{u,v\}\in S}$
     kontrahiere  ${\displaystyle \{u,v\}}$
    ${\displaystyle T\gets T\cup S}$
 return  ${\displaystyle T}$

Parallel implementation

The following is the number of processors. The algorithm uses the representation of the graph by an adjacency array . Here is the set of neighbors of and correspondingly their number. With is the weight of the edge from to . Each undirected edge is represented by two oppositely directed edges. ${\displaystyle p}$ ${\displaystyle \Gamma (v)}$ ${\displaystyle v}$ ${\displaystyle |\Gamma (v)|}$ ${\displaystyle c(v,w)}$ ${\displaystyle v}$ ${\displaystyle w}$

For each node, a subset of the processors searches in parallel for the easiest outgoing edge.

 für alle  ${\displaystyle v\in V}$ parallel
   ordne  ${\displaystyle |\Gamma (v)|{\tfrac {p}{2|E|}}}$ Prozessoren Knoten  ${\displaystyle v}$ zu
   wähle  ${\displaystyle (v,w)}$ mit minimalem Gewicht  ${\displaystyle c(v,w)}$ in  ${\displaystyle \Gamma (v)}$
   gib originale Kante  ${\displaystyle (v,w)}$ als Teil des Spannbaums aus (Kante vor allen Kontraktionen)
   setze  ${\displaystyle pred(v)\gets w}$

The processors can be assigned using a parallel prefix sum so that calculations can be carried out in constant time. This can then be determined by a minimum reduction between the processors involved. This can be done in time . ${\displaystyle |\Gamma (v)|}$ ${\displaystyle w}$ ${\displaystyle O\left({\tfrac {|E|}{p}}+\log p\right)}$

Now consider the directed graph . The graph has exit degree . So there are edges in every component of this graph, so it is a tree with exactly one additional edge. In addition, there is exactly one circle along the originally lightest edge and all other edges in are directed towards or towards. We call this structure a pseudo-tree. In time , all pseudo-trees can be converted into rooted trees, i.e. trees with a clear root towards which all edges run. ${\displaystyle (V,\{(v,pred(v)):v\in V\})}$ ${\displaystyle 1}$ ${\displaystyle C}$ ${\displaystyle |C|}$ ${\displaystyle 2}$ ${\displaystyle (u,w)}$ ${\displaystyle C}$ ${\displaystyle u}$ ${\displaystyle w}$ ${\displaystyle O\left({\tfrac {|V|}{p}}\right)}$

 für alle  ${\displaystyle v\in V}$ parallel
    ${\displaystyle w\gets pred(v)}$
   falls  ${\displaystyle v<w}$ und  ${\displaystyle pred(w)=v}$
      ${\displaystyle pred(v)\gets v}$

In a further step with runtime , these rooted trees can then be converted into rooted stars. These are special trees of height , that is, all edges point directly to the unique root. ${\displaystyle O\left({\tfrac {|V|}{p}}~\log |V|\right)}$ ${\displaystyle 1}$

 solange  ${\displaystyle \exists v\in V:pred(pred(v))\neq pred(v)}$
   für alle  ${\displaystyle v\in V}$ parallel
      ${\displaystyle pred(v)\gets pred(pred(v))}$

The rooted stars can now be contracted by their roots forming the new set of nodes. This takes time in . ${\displaystyle O\left({\tfrac {|E|}{p}}+\log p\right)}$

  ${\displaystyle k\gets }$ Anzahl der Komponenten (Sterne)
  ${\displaystyle V'\gets \{1,\ldots ,k\}}$
 wähle eine bijektive Abbildung  ${\displaystyle f:\{{\text{Sternwurzeln}}\}\to \{1,\ldots ,k\}}$
  ${\displaystyle E'\gets \{(f(pred(u)),f(pred(v)),c,e_{\text{old}}):(u,v,c,e_{\text{old}})\in E\land pred(u)\neq pred(v)\}}$

A graph is obtained . The nodes of are exactly the star roots that were renamed from the bijective mapping to . It may contain parallel edges, of which only the lightest is required. The graph must now be brought into adjacency array representation for the recursion step. This can be done in the expected time . ${\displaystyle G'=(V',E')}$ ${\displaystyle G'}$ ${\displaystyle f}$ ${\displaystyle \{1,\ldots ,k\}}$ ${\displaystyle E'}$ ${\displaystyle G'}$ ${\displaystyle O\left({\tfrac {|E|}{p}}+\log p\right)}$

In summary, this results in an expected total running time of per lap and thus of overall . ${\displaystyle O\left({\tfrac {|E|}{p}}+\log p\right)}$ ${\displaystyle O\left({\tfrac {|E|}{p}}\log |V|+\log ^{2}|V|\right)}$

literature

• Borůvka, Otakar (1926). "O jistémproblemému minimálním (About a certain minimal problem)". Práce mor. Přírodověd. spol. v Brně III (in Czech, German summary) 3: 37–58.
• Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)". Elektronický Obzor (in Czech) 15: 153-154.
• Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena (2001). "Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history". Discrete Mathematics 233 (1-3): 3-36. doi : 10.1016 / S0012-365X (00) 00224-7 .
• Choquet, Gustave (1938). "Étude de certains réseaux de routes". Comptes-rendus de l'Académie des Sciences (in French) 206: 310-313.
• Florek, Kazimierz (1951). "Sur la liaison et la division des points d'un ensemble fini". Colloquium Mathematicum 2 (1951) (in French): 282-285.
• Sollin, M. (1965). "Le tracé de canalisation". Programming, Games, and Transportation Networks (in French).
• Eppstein, David (1999). "Spanning trees and spanners". In Sack, J.-R .; Urrutia, J. Handbook of Computational Geometry. Elsevier. pp. 425-461.
• Mareš, Martin (2004). "Two linear time algorithms for MST on minor closed graph classes". Archivum mathematicum 40 (3): 315-320.

Individual evidence

1. ^ Rajasekaran, J Reif: Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms . In: SIAM Journal on Computing . 18, 1989, pp. 594-607.