Tag Archives: Spanning Trees

Spanning forest of a graph in C

A graph showing a spanning forest

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)

Spanning tree of a graph in C

A complete graph on 5 vertices showing a spanning tree

In a previous post I showed an algorithm to find all spanning trees in a graph. A simpler problem is just to find a single spanning tree. This can be solved using a depth-first search. We simply need to record, for each vertex we visit, the edge by which we reached it.

Below is an implementation in C. The function spanning_tree() takes a graph in edge list format, the number of edges (size), the number of vertices (order), and the address of a pointer to which to assign the spanning tree. The spanning tree is in the form of an array of edge indices. The function returns the number of edges in this array, which will be order – 1 if the graph is connected. If the graph is not connected, the function will return a spanning tree of the component containing vertex 0, and the returned size will be correspondingly smaller.

#include <stdlib.h>

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

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);
            }
        }
    }
}

unsigned int spanning_tree(const edge *edges, unsigned int size, unsigned int order,
        unsigned int **tree)
{
    unsigned int *visited = calloc(order, sizeof(unsigned int));
    *tree = malloc((order - 1) * sizeof(unsigned int));
    unsigned int len = 0;
    if (visited == NULL || *tree == NULL) {
        free(visited);
        free(*tree);
        *tree = NULL;
        return 0;
    }
    spanning_tree_recursive(edges, size, order, visited, *tree, 0, -1, &len);
    free(visited);
    return len;
}

Here is an example program that finds a spanning tree of the complete graph on 5 vertices:

/* Calculate the nth triangular number T(n) */
unsigned int triangular_number(unsigned int n)
{
    return (n * (n + 1)) / 2;
}

/* Construct a complete graph on v vertices */
unsigned int complete_graph(unsigned int v, edge **edges)
{
    unsigned int n = triangular_number(v - 1);
    unsigned int i, j, k;
    *edges = malloc(n * sizeof(edge));
    if (edges != NULL) {
        for (i = 0, k = 0; i < v - 1; i++) {
            for (j = i + 1; j < v; j++) {
                (*edges)[k].first = i;
                (*edges)[k].second = j;
                k++;
            }
        }
    }
    else {
        n = 0;
    }
    return n;
}

int main(void)
{
    edge *edges;
    const unsigned int order = 5; /* Vertices */
    const unsigned int size = complete_graph(5, &edges); /* Edges */
    unsigned int *tree;
    unsigned int tree_size = spanning_tree(edges, size, order, &tree);
    unsigned int e;
    for (e = 0; e < tree_size; e++) {
        printf("(%u, %u) ", edges[tree[e]].first, edges[tree[e]].second);
    }
    putchar('\n');
    free(edges);
    free(tree);
    return 0;
}

The output:

(0, 1) (1, 2) (2, 3) (3, 4)

Spanning trees of a graph in C

A spanning tree of a graph is a subgraph that includes all of the vertices, but only enough edges to connect them. A connected graph will have more than one spanning tree unless the graph is a tree, in which case it has just one spanning tree which is the graph itself. A spanning tree of a graph of order \(v\) will contain \(v – 1\) edges.

In order to list all of the spanning trees of a graph, we could just construct all of the subsets of the edges of size \(v – 1\), and then check if they form a spanning tree, but that wouldn’t be very efficient. A more efficient method is to use backtracking, which is what the algorithm presented here does.

In order to decide whether or not to add an edge to a partially constructed spanning tree, the algorithm checks that the candidate edge:

  1. Has a higher numeric index than its predecessor
  2. Doesn’t have both edges in the same connected component of the tree

The first condition prevents duplicates because the edges are always listed in ascending order. The second one ensures that the tree doesn’t contain too many edges, because an edge is superfluous if both of its endpoints are in the same connected component. In order to check this condition, I used the connected components of a graph algorithm I described previously.

The C code is below. The function spanning_trees() takes a graph in edge list representation, the number of edges and vertices, and a user callback that is called for every spanning tree found.

#include <stdlib.h>

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

typedef void (*treefn)(const edge *, unsigned int);

/* Check if vertices v1 and v2 are in different components in the tree */
static unsigned int different_components(const edge *tree, unsigned int t, unsigned int order,
        unsigned int v1, unsigned int v2)
{
    int *components;
    unsigned int different;
    connected_components(tree, t, order, &components);
    different = components[v1] != components[v2];
    free(components);
    return different;
}

static void spanning_trees_recursive(const edge *edges, unsigned int n, unsigned int order, 
        edge *tree, unsigned int t, int predecessor, treefn fun)
{
    if (t == order - 1) {
        /* Found a tree */
        fun(tree, order - 1);
    }
    else {
        unsigned int e;
        for (e = predecessor + 1; e < n; e++) {
            if (t == 0 /* First edge */
                || different_components(tree, t, order, 
                    edges[e].first, edges[e].second))
            {
                tree[t] = edges[e];   
                spanning_trees_recursive(edges, n, order, tree, t + 1, e, fun);
            }
        }
    }
}

void spanning_trees(const edge *edges, unsigned int n, unsigned int order, treefn fun)
{
    edge *tree;
    tree = malloc((n - 1) * sizeof(edge));
    if (tree == NULL) {
        return;
    }
    spanning_trees_recursive(edges, n, order, tree, 0, -1, fun);
    free(tree);
}

Here is an example that prints all of the spanning trees of the complete graph on 5 vertices:

#include <stdio.h>
#include <stdlib.h>

/* Calculate the nth triangular number T(n) */
unsigned int triangular_number(unsigned int n)
{
    return (n * (n + 1)) / 2;
}

/* Construct a complete graph on v vertices */
edge *complete_graph(unsigned int v)
{
    const unsigned int n = triangular_number(v - 1);
    unsigned int i, j, k;
    edge *edges = malloc(n * sizeof(edge));
    if (edges != NULL) {
        for (i = 0, k = 0; i < v - 1; i++) {
            for (j = i + 1; j < v; j++) {
                edges[k].first = i;
                edges[k].second = j;
                k++;
            }
        }
    }
    return edges;
}

/* Print the edges in a tree */
static void print_tree(const edge *tree, unsigned int n)
{
    unsigned int e;
    for (e = 0; e < n; e++) {
        printf("(%u, %u) ", tree[e].first, tree[e].second);
    }
    putchar('\n');
}


int main(void)
{
    const unsigned int v = 5;
    const unsigned int n = triangular_number(v - 1);
    edge *edges;
    
    edges = complete_graph(v);
    if (edges == NULL) {
        return 1;
    }
    spanning_trees(edges, n, v, print_tree);
    free(edges);

    return 0;
}

Here is the output. There are 125 spanning trees of the complete graph on 5 vertices:

(0, 1) (0, 2) (0, 3) (0, 4) 
(0, 1) (0, 2) (0, 3) (1, 4) 
(0, 1) (0, 2) (0, 3) (2, 4) 
(0, 1) (0, 2) (0, 3) (3, 4) 
(0, 1) (0, 2) (0, 4) (1, 3) 
(0, 1) (0, 2) (0, 4) (2, 3) 
(0, 1) (0, 2) (0, 4) (3, 4) 
(0, 1) (0, 2) (1, 3) (1, 4) 
(0, 1) (0, 2) (1, 3) (2, 4) 
(0, 1) (0, 2) (1, 3) (3, 4) 
(0, 1) (0, 2) (1, 4) (2, 3) 
(0, 1) (0, 2) (1, 4) (3, 4) 
(0, 1) (0, 2) (2, 3) (2, 4) 
(0, 1) (0, 2) (2, 3) (3, 4) 
(0, 1) (0, 2) (2, 4) (3, 4) 
(0, 1) (0, 3) (0, 4) (1, 2) 
(0, 1) (0, 3) (0, 4) (2, 3) 
(0, 1) (0, 3) (0, 4) (2, 4) 
(0, 1) (0, 3) (1, 2) (1, 4) 
(0, 1) (0, 3) (1, 2) (2, 4) 
(0, 1) (0, 3) (1, 2) (3, 4) 
(0, 1) (0, 3) (1, 4) (2, 3) 
(0, 1) (0, 3) (1, 4) (2, 4) 
(0, 1) (0, 3) (2, 3) (2, 4) 
(0, 1) (0, 3) (2, 3) (3, 4) 
(0, 1) (0, 3) (2, 4) (3, 4) 
(0, 1) (0, 4) (1, 2) (1, 3) 
(0, 1) (0, 4) (1, 2) (2, 3) 
(0, 1) (0, 4) (1, 2) (3, 4) 
(0, 1) (0, 4) (1, 3) (2, 3) 
(0, 1) (0, 4) (1, 3) (2, 4) 
(0, 1) (0, 4) (2, 3) (2, 4) 
(0, 1) (0, 4) (2, 3) (3, 4) 
(0, 1) (0, 4) (2, 4) (3, 4) 
(0, 1) (1, 2) (1, 3) (1, 4) 
(0, 1) (1, 2) (1, 3) (2, 4) 
(0, 1) (1, 2) (1, 3) (3, 4) 
(0, 1) (1, 2) (1, 4) (2, 3) 
(0, 1) (1, 2) (1, 4) (3, 4) 
(0, 1) (1, 2) (2, 3) (2, 4) 
(0, 1) (1, 2) (2, 3) (3, 4) 
(0, 1) (1, 2) (2, 4) (3, 4) 
(0, 1) (1, 3) (1, 4) (2, 3) 
(0, 1) (1, 3) (1, 4) (2, 4) 
(0, 1) (1, 3) (2, 3) (2, 4) 
(0, 1) (1, 3) (2, 3) (3, 4) 
(0, 1) (1, 3) (2, 4) (3, 4) 
(0, 1) (1, 4) (2, 3) (2, 4) 
(0, 1) (1, 4) (2, 3) (3, 4) 
(0, 1) (1, 4) (2, 4) (3, 4) 
(0, 2) (0, 3) (0, 4) (1, 2) 
(0, 2) (0, 3) (0, 4) (1, 3) 
(0, 2) (0, 3) (0, 4) (1, 4) 
(0, 2) (0, 3) (1, 2) (1, 4) 
(0, 2) (0, 3) (1, 2) (2, 4) 
(0, 2) (0, 3) (1, 2) (3, 4) 
(0, 2) (0, 3) (1, 3) (1, 4) 
(0, 2) (0, 3) (1, 3) (2, 4) 
(0, 2) (0, 3) (1, 3) (3, 4) 
(0, 2) (0, 3) (1, 4) (2, 4) 
(0, 2) (0, 3) (1, 4) (3, 4) 
(0, 2) (0, 4) (1, 2) (1, 3) 
(0, 2) (0, 4) (1, 2) (2, 3) 
(0, 2) (0, 4) (1, 2) (3, 4) 
(0, 2) (0, 4) (1, 3) (1, 4) 
(0, 2) (0, 4) (1, 3) (2, 3) 
(0, 2) (0, 4) (1, 3) (3, 4) 
(0, 2) (0, 4) (1, 4) (2, 3) 
(0, 2) (0, 4) (1, 4) (3, 4) 
(0, 2) (1, 2) (1, 3) (1, 4) 
(0, 2) (1, 2) (1, 3) (2, 4) 
(0, 2) (1, 2) (1, 3) (3, 4) 
(0, 2) (1, 2) (1, 4) (2, 3) 
(0, 2) (1, 2) (1, 4) (3, 4) 
(0, 2) (1, 2) (2, 3) (2, 4) 
(0, 2) (1, 2) (2, 3) (3, 4) 
(0, 2) (1, 2) (2, 4) (3, 4) 
(0, 2) (1, 3) (1, 4) (2, 3) 
(0, 2) (1, 3) (1, 4) (2, 4) 
(0, 2) (1, 3) (2, 3) (2, 4) 
(0, 2) (1, 3) (2, 3) (3, 4) 
(0, 2) (1, 3) (2, 4) (3, 4) 
(0, 2) (1, 4) (2, 3) (2, 4) 
(0, 2) (1, 4) (2, 3) (3, 4) 
(0, 2) (1, 4) (2, 4) (3, 4) 
(0, 3) (0, 4) (1, 2) (1, 3) 
(0, 3) (0, 4) (1, 2) (1, 4) 
(0, 3) (0, 4) (1, 2) (2, 3) 
(0, 3) (0, 4) (1, 2) (2, 4) 
(0, 3) (0, 4) (1, 3) (2, 3) 
(0, 3) (0, 4) (1, 3) (2, 4) 
(0, 3) (0, 4) (1, 4) (2, 3) 
(0, 3) (0, 4) (1, 4) (2, 4) 
(0, 3) (1, 2) (1, 3) (1, 4) 
(0, 3) (1, 2) (1, 3) (2, 4) 
(0, 3) (1, 2) (1, 3) (3, 4) 
(0, 3) (1, 2) (1, 4) (2, 3) 
(0, 3) (1, 2) (1, 4) (3, 4) 
(0, 3) (1, 2) (2, 3) (2, 4) 
(0, 3) (1, 2) (2, 3) (3, 4) 
(0, 3) (1, 2) (2, 4) (3, 4) 
(0, 3) (1, 3) (1, 4) (2, 3) 
(0, 3) (1, 3) (1, 4) (2, 4) 
(0, 3) (1, 3) (2, 3) (2, 4) 
(0, 3) (1, 3) (2, 3) (3, 4) 
(0, 3) (1, 3) (2, 4) (3, 4) 
(0, 3) (1, 4) (2, 3) (2, 4) 
(0, 3) (1, 4) (2, 3) (3, 4) 
(0, 3) (1, 4) (2, 4) (3, 4) 
(0, 4) (1, 2) (1, 3) (1, 4) 
(0, 4) (1, 2) (1, 3) (2, 4) 
(0, 4) (1, 2) (1, 3) (3, 4) 
(0, 4) (1, 2) (1, 4) (2, 3) 
(0, 4) (1, 2) (1, 4) (3, 4) 
(0, 4) (1, 2) (2, 3) (2, 4) 
(0, 4) (1, 2) (2, 3) (3, 4) 
(0, 4) (1, 2) (2, 4) (3, 4) 
(0, 4) (1, 3) (1, 4) (2, 3) 
(0, 4) (1, 3) (1, 4) (2, 4) 
(0, 4) (1, 3) (2, 3) (2, 4) 
(0, 4) (1, 3) (2, 3) (3, 4) 
(0, 4) (1, 3) (2, 4) (3, 4) 
(0, 4) (1, 4) (2, 3) (2, 4) 
(0, 4) (1, 4) (2, 3) (3, 4) 
(0, 4) (1, 4) (2, 4) (3, 4)