Minimum Spanning Forest
Given an undirected graph with one or more connected components, a minimum spanning forest is a set of minimum spanning trees, one for each component. The library implements the algorithm in section 6.2 of Qin et al. 2014: http://www-std1.se.cuhk.edu.hk/~hcheng/paper/SIGMOD2014qin.pdf.
Specifications
Characteristic | Value |
Result | Computes a minimum spanning forest. If the JSON or file output selected, the output is the set of edges that form the MSF. If the result_attr option is selected, the edges which are part of the MSF are tagged True; other edges are tagged False. |
Input Parameters |
|
Result Size | V - c, V = number of vertices, c = number of components |
Time Complexity | O((V+E) * logV) |
Graph Types | Undirected edges |
Example
Refer to the example for the MST algorithm. This graph has 3 components. MSF will find an MST for each of the three components.
Last updated