In graph theory a minimum spanning tree (MST) T {\displaystyle T} of a graph G = ( V , E ) {\displaystyle G=(V,E)} with | V | = n {\displaystyle |V|=n} and | E | = m {\displaystyle |E|=m} is a tree subgraph of G {\displaystyle G} that contains all of its vertices and is of minimum weight. MSTs are useful and versatile tools utilised in a wide variety of practical and theoretical fields. For example, a company looking to supply multiple stores with a certain product from a single warehouse might use an MST originating at the warehouse to calculate the shortest paths to each company store. In this case the stores and the warehouse are represented as vertices and the road connections between them - as edges. Each edge is labelled with the length of the corresponding road connection. If G {\displaystyle G} is edge-unweighted every spanning tree possesses the same number of edges and thus the same weight. In the edge-weighted case, the spanning tree, the sum of the weights of the edges of which is lowest among all spanning trees of G {\displaystyle G} , is called a minimum spanning tree (MST). It is not necessarily unique. More generally, graphs that are not necessarily connected have minimum spanning forests, which consist of a union of MSTs for each connected component. As finding MSTs is a widespread problem in graph theory, there exist many sequential algorithms for solving it. Among them are Prim's, Kruskal's and Borůvka's algorithms, each utilising different properties of MSTs. They all operate in a similar fashion - a subset of E {\displaystyle E} is iteratively grown until a valid MST has been discovered. However, as practical problems are often quite large (road networks sometimes have billions of edges), performance is a key factor. One option of improving it is by parallelising known MST algorithms.
Prim's algorithm This algorithm utilises the cut-property of MSTs. A simple high-level pseudocode implementation is provided below:
T ← ∅ {\displaystyle T\gets \emptyset }
S ← { s } {\displaystyle S\gets \{s\}} where s {\displaystyle s} is a random vertex in V {\displaystyle V}
repeat | V | − 1 {\displaystyle |V|-1} times find lightest edge ( u , v ) {\displaystyle (u,v)} s.t. u ∈ S {\displaystyle u\in S} but v ∈ ( V ∖ S ) {\displaystyle v\in (V\setminus S)}
S ← S ∪ { v } {\displaystyle S\gets S\cup \{v\}}
T ← T ∪ { ( u , v ) } {\displaystyle T\gets T\cup \{(u,v)\}}
return T
Each edge is observed exactly twice - namely when examining each of its endpoints. Each vertex is examined exactly once for a total of O ( n + m ) {\displaystyle O(n+m)} operations aside from the selection of the lightest edge at each loop iteration. This selection is often performed using a priority queue (PQ). For each edge at most one decreaseKey operation (amortised in O ( 1 ) {\displaystyle O(1)} ) is performed and each loop iteration performs one deleteMin operation ( O ( log n ) {\displaystyle O(\log n)} ). Thus using Fibonacci heaps the total runtime of Prim's algorithm is asymptotically in O ( m + n log n ) {\displaystyle O(m+n\log n)} . The loop is inherently sequential and can not be properly parallelised. This is the case, since the lightest edge with one endpoint in S {\displaystyle S} and on in V ∖ S {\displaystyle V\setminus S} might change with the addition of edges to T {\displaystyle T} . Thus no two selections of a lightest edge can be performed at the same time. However, there do exist some attempts at parallelisation. One possible idea is to use O ( n ) {\displaystyle O(n)} processors to support PQ access in O ( 1 ) {\displaystyle O(1)} on an EREW-PRAM machine, thus lowering the total runtime to O ( n + m ) {\displaystyle O(n+m)} .
Kruskal's algorithm Kruskal's MST algorithm utilises the cycle property of MSTs. A high-level pseudocode representation is provided below.
T ← {\displaystyle T\gets } forest with every vertex in its own subtree foreach ( u , v ) ∈ E {\displaystyle (u,v)\in E} in ascending order of weight if u {\displaystyle u} and v {\displaystyle v} in different subtrees of T {\displaystyle T}
… excerpt ends here. Continue reading the full article.
