If a graph isn’t connected, there isn’t a spanning tree that covers all of the vertices. We can, however, construct a spanning forest, which is a set of spanning trees, one for each connected component in the graph. This is rather similar to finding connected components, except that in a spanning forest the components are represented by a set of edges, rather than a set of vertices. Any vertices in the graph that are entirely unconnected will not appear in the spanning forest.
To find the spanning forest, all we need to do is to use the depth-first search algorithm for finding a spanning tree repeatedly, starting at each unvisited vertex in turn. Once all vertices that appear in edges have been visited, the spanning forest is complete.
Below is an implementation in C. The function spanning_forest() takes a graph in edge list format, the number of edges (size), the number of vertices (order), and a callback function that is called with each spanning tree found. It reuses the spanning_tree_recursive() function from the spanning tree algorithm to find each spanning tree.
#include <stdlib.h>
typedef struct {
unsigned int first;
unsigned int second;
} edge;
typedef void (*treefn)(const unsigned int *, size_t, const edge *, size_t);
void spanning_tree_recursive(const edge *edges, unsigned int size,
unsigned int order, unsigned int *visited, unsigned int *tree,
unsigned int vertex, int edge, unsigned int *len)
{
unsigned int e;
visited[vertex] = 1;
if (edge != -1) {
tree[(*len)++] = edge;
}
for (e = 0; e < size; e++) {
if (edges[e].first == vertex || edges[e].second == vertex) {
unsigned int neighbour = edges[e].first == vertex ?
edges[e].second : edges[e].first;
if (!visited[neighbour]) {
spanning_tree_recursive(edges, size, order, visited, tree,
neighbour, e, len);
}
}
}
}
void spanning_forest(const edge *edges, unsigned int size, unsigned int order,
treefn fun)
{
unsigned int *visited = calloc(order, sizeof(unsigned int));
unsigned int *tree = malloc((order - 1) * sizeof(unsigned int));
unsigned int len, v;
if (visited == NULL || tree == NULL) {
free(visited);
free(tree);
return;
}
for (v = 0; v < order; v++) {
if (!visited[v]) {
len = 0;
spanning_tree_recursive(edges, size, order, visited, tree, v, -1, &len);
if (len > 0) {
fun(tree, len, edges, size);
}
}
}
free(visited);
free(tree);
}
Here is an example program that finds the spanning forest of the graph shown at the top.
#include <stdio.h>
#include <stdlib.h>
/* Connect two edges */
void edge_connect(edge *edges, unsigned int first, unsigned int second,
unsigned int *pos)
{
edges[*pos].first = first;
edges[*pos].second = second;
(*pos)++;
}
void print(const unsigned int *tree, size_t tree_size, const edge *edges, size_t size)
{
unsigned int e;
for (e = 0; e < tree_size; e++) {
printf("(%u, %u) ", edges[tree[e]].first, edges[tree[e]].second);
}
putchar('\n');
}
int main(void)
{
const unsigned int order = 9; /* Vertices */
const unsigned int size = 8; /* Edges */
edge *edges;
edges = malloc(size * sizeof(edge));
if (edges == NULL) {
return 1;
}
/* Square */
edges[0].first = 0;
edges[0].second = 1;
edges[1].first = 1;
edges[1].second = 2;
edges[2].first = 2;
edges[2].second = 3;
edges[3].first = 3;
edges[3].second = 0;
/* Triangle */
edges[4].first = 4;
edges[4].second = 5;
edges[5].first = 5;
edges[5].second = 6;
edges[6].first = 6;
edges[6].second = 4;
/* Line */
edges[7].first = 7;
edges[7].second = 8;
spanning_forest(edges, size, order, print);
free(edges);
return 0;
}
The output:
(0, 1) (1, 2) (2, 3) (4, 5) (5, 6) (7, 8)
