---
title: "Minimum Spanning Forest"
component: "graph-ml"
version: "3.10"
module: "pathfinding-algorithms"
html_url: "/graph-ml/3.10/pathfinding-algorithms/minimum-spanning-forest"
canonical_url: "https://www.tigergraph.com/docs/graph-ml/3.10/pathfinding-algorithms/minimum-spanning-forest"
markdown_url: "https://www.tigergraph.com/docs/graph-ml/3.10/pathfinding-algorithms/minimum-spanning-forest.md"
---

[View as HTML](https://www.tigergraph.com/docs/graph-ml/3.10/pathfinding-algorithms/minimum-spanning-forest)

# Minimum Spanning Forest

Supported Graph Characteristics

| Weighted edges |
| --- |
| Directed edges |
| Undirected edges |
| Homogeneous vertex types |
| Heterogeneous vertex types |

Algorithm link: [Minimum Spanning Forest](https://github.com/tigergraph/gsql-graph-algorithms/tree/master/algorithms/Path/minimum%5Fspanning%5Fforest)

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](http://www-std1.se.cuhk.edu.hk/~hcheng/paper/SIGMOD2014qin.pdf)

## Specifications

```gsql
tg_msf ( SET<STRING> v_type_set,  SET<STRING> e_type_set, STRING weight_attribute, STRING weight_type,
BOOL print_results = TRUE, STRING result_attribute = "", 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 weight_attribute` | Name of edge weight attribute | (empty string) |
| `STRING weight_type` | Data type of edge weight attribute (must be `INT`, `FLOAT`, or `DOUBLE`) | (empty string) |
| `BOOL print_results` | If True, output JSON to standard output | True |
| `STRING result_attribute` | 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\_attribute 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](https://www.tigergraph.com/docs/graph-ml/3.10/pathfinding-algorithms/minimum-spanning-tree.md) algorithm. This graph has three components. The MSF algorithm finds an MST for each of the three components.
