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)