# Minimum Spanning Forest

Supported Graph Characteristics
 Weighted edges Directed edges Undirected edges Homogeneous vertex types Heterogeneous vertex types

Algorithm link: 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.

## Notes

This is an implementation of the algorithm in section 6.2 of Qin et al. 2014: Scalable Big Graph Processing in MapReduce

## Specifications

``````tg_msf (SET<STRING> v_type, SET<STRING> e_type, STRING wt_attr, STRING wt_type,
BOOL print_accum = TRUE, STRING result_attr = "", STRING file_path = "")``````

### Parameters

Parameter Description Default

`SET<STRING> v_type`

Names of vertex types to use

(empty set of strings)

`SET<STRING> e_type`

Names of edge types to use

(empty set of strings)

`STRING wt_attr`

Name of edge weight attribute

(empty string)

`STRING wt_type`

Data type of edge weight attribute (must be `INT`, `FLOAT`, or `DOUBLE`)

(empty string)

`BOOL print_accum`

If True, output JSON to standard output

True

`STRING result_attr`

If not empty, store result values (`BOOL`) to this attribute

(empty string)

`STRING file_path`

If not empty, write output to this file.

(empty string)

### Output

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.

### Result size

V - c where V is the number of vertices and c is the number of components.

### Time complexity

This algorithm has a time complexity of O((V+E) * log(V)), where V is equal to the number of vertices and E is equal to the number of edges.

## Example

Refer to the example for the Minimum Spanning Tree algorithm. This graph has three components. The MSF algorithm finds an MST for each of the three components.