Minimum Spanning Forest in C for Disconnected Graphs

A disconnected graph has no minimum spanning tree covering every vertex. The useful result is a minimum spanning forest: one minimum spanning tree for each connected component. This C program finds that forest, reports its total weight, and counts components, including isolated vertices. The worked example includes a zero-weight edge, negative weights, a cycle, parallel edges, and a self-loop.

Why a disconnected graph needs a forest

A spanning tree must connect all vertices using edges from the original graph. If no path joins two groups of vertices, choosing a different collection of existing edges cannot connect them. Inventing an edge would change the problem. Instead, preserve each connected group and find its cheapest spanning tree. An isolated vertex forms a component with no selected edges.

This definition of a minimum spanning forest follows the treatment in Princeton's Minimum Spanning Trees lesson. Here, “minimum” refers to the sum of selected edge weights, while every vertex and every original component must be represented.

Example: two groups and one isolated vertex

Number the vertices from 0 to 6. Vertices 0, 1, 2 form one connected group; 3, 4, 5 form another. Vertex 6 has no edges. There are two different edges between vertices 0 and 1, with weights 4 and 2. A self-loop joins vertex 5 to itself.

The table shows every edge after sorting by weight. “Accept” means the endpoints belong to different groups in the forest built so far.

Sorted edges and the decisions made by the program

Edge	Weight	Decision	Reason
5 – 5	-10	Skip	A self-loop cannot join groups.
3 – 4	-2	Accept	Join vertices 3 and 4.
4 – 5	0	Accept	Add vertex 5 to that group.
1 – 2	1	Accept	Join vertices 1 and 2.
0 – 1	2	Accept	Add vertex 0 to that group.
0 – 2	3	Skip	A path already joins the endpoints.
0 – 1	4	Skip	The cheaper parallel edge already joined them.
3 – 5	5	Skip	It would close a cycle.

The forest selects four edges with total weight -2 + 0 + 1 + 2 = 1. The three final components are {0,1,2}, {3,4,5}, and {6}. Vertex 6 remains present even though it never appears in an edge printed below.

Complete C program

The edge list represents an undirected graph with zero-based endpoints. The reusable function leaves that input unchanged and writes a bounded result structure. A fixed demonstration graph keeps the output reproducible without keyboard input or external files.

#include <stdio.h>

#define MAX_VERTICES 100
#define MAX_EDGES 1000
#define MAX_WEIGHT 1000000L

typedef struct {
    int u, v;
    long weight;
} Edge;

typedef struct {
    Edge edges[MAX_VERTICES - 1];
    int edge_count;
    int component_count;
    long total_weight;
} Forest;

static int find_root(int parent[], int vertex)
{
    while (parent[vertex] != vertex) {
        parent[vertex] = parent[parent[vertex]];
        vertex = parent[vertex];
    }
    return vertex;
}

static int comes_after(Edge left, Edge right)
{
    if (left.weight != right.weight)
        return left.weight > right.weight;
    if (left.u != right.u)
        return left.u > right.u;
    return left.v > right.v;
}

/* Return 1 on success, or 0 for invalid arguments. */
int minimum_spanning_forest(int vertex_count, const Edge *edges,
                           int edge_count, Forest *forest)
{
    Edge sorted[MAX_EDGES];
    int parent[MAX_VERTICES], rank[MAX_VERTICES];
    int i, j;

    if (forest == NULL || vertex_count < 0 ||
        vertex_count > MAX_VERTICES || edge_count < 0 ||
        edge_count > MAX_EDGES || (edge_count > 0 && edges == NULL))
        return 0;

    for (i = 0; i < edge_count; ++i) {
        if (edges[i].u < 0 || edges[i].u >= vertex_count ||
            edges[i].v < 0 || edges[i].v >= vertex_count ||
            edges[i].weight < -MAX_WEIGHT ||
            edges[i].weight > MAX_WEIGHT)
            return 0;
    }

    for (i = 0; i < edge_count; ++i)
        sorted[i] = edges[i];

    /* Insertion sort: weight first, then endpoints for repeatable ties. */
    for (i = 1; i < edge_count; ++i) {
        Edge current = sorted[i];
        j = i;
        while (j > 0 && comes_after(sorted[j - 1], current)) {
            sorted[j] = sorted[j - 1];
            --j;
        }
        sorted[j] = current;
    }

    for (i = 0; i < vertex_count; ++i) {
        parent[i] = i;
        rank[i] = 0;
    }

    forest->edge_count = 0;
    forest->component_count = vertex_count;
    forest->total_weight = 0;

    for (i = 0; i < edge_count; ++i) {
        int root_u = find_root(parent, sorted[i].u);
        int root_v = find_root(parent, sorted[i].v);

        if (root_u == root_v)
            continue; /* This includes self-loops. */

        if (rank[root_u] < rank[root_v]) {
            parent[root_u] = root_v;
        } else {
            parent[root_v] = root_u;
            if (rank[root_u] == rank[root_v])
                ++rank[root_u];
        }

        forest->edges[forest->edge_count++] = sorted[i];
        forest->total_weight += sorted[i].weight;
        --forest->component_count;
    }
    return 1;
}

int main(void)
{
    const Edge graph[] = {
        {0, 1, 4}, {1, 2, 1}, {0, 2, 3}, {0, 1, 2},
        {3, 4, -2}, {4, 5, 0}, {3, 5, 5}, {5, 5, -10}
    };
    const int vertex_count = 7;
    const int edge_count = (int)(sizeof graph / sizeof graph[0]);
    Forest forest;
    int i;

    if (!minimum_spanning_forest(vertex_count, graph, edge_count, &forest)) {
        fputs("Invalid graph.\n", stderr);
        return 1;
    }

    puts("Minimum spanning forest:");
    for (i = 0; i < forest.edge_count; ++i)
        printf("%d -- %d : %ld\n", forest.edges[i].u,
               forest.edges[i].v, forest.edges[i].weight);
    printf("Total weight: %ld\n", forest.total_weight);
    printf("Components: %d\n", forest.component_count);
    printf("Selected edges: %d\n", forest.edge_count);
    return 0;
}

Output

Minimum spanning forest:
3 -- 4 : -2
4 -- 5 : 0
1 -- 2 : 1
0 -- 1 : 2
Total weight: 1
Components: 3
Selected edges: 4

Union-find invariants and component count

Initially, each vertex is a separate set, so the counter starts at seven. Each accepted edge joins two sets and reduces the counter by one. Four successful joins leave 7 - 4 = 3 components. More generally, a spanning forest with V vertices and C components contains V - C edges.

The disjoint-set invariant is that two vertices have the same root exactly when the selected forest already connects them. find_root uses path halving: each visited vertex is redirected to its grandparent. Union attaches a lower-rank root beneath a higher-rank root and increments rank only on equal-rank joins. After path shortening, rank remains a guide for merging, rather than an exact height or component size.

If both endpoints have the same root, accepting that edge would create a cycle. Otherwise, the program joins their sets and stores the edge. Sorting first makes it consider cheaper connections before more expensive ones. This is Kruskal's selection rule, applied across every component. Read the existing Kruskal's algorithm lesson for the broader topic.

At an accepted edge, its two sets define a cut inside one original component. No cheaper unprocessed edge crosses that cut, because edges are considered in nondecreasing order. The minimum-edge cut rule therefore permits the join. Processing every edge eventually connects each original component internally. The loop is bounded by edge_count; waiting only for V - 1 accepted edges would fail to terminate safely on this disconnected example.

Weights, limits, and running time

Zero is a real edge weight here, rather than a marker meaning “no edge.” Negative weights are also allowed. A negative self-loop is still rejected because the answer must be a forest. Equal weights may allow several equally good answers; comparing endpoints after weight makes this example's ordering repeatable. These weight cases also appear in Princeton's KruskalMST documentation.

The function accepts 0 to 100 vertices, up to 1,000 edges, and weights from -1,000,000 to 1,000,000. It returns 0 for invalid counts, endpoints, weights, or required pointers; callers should read the result only after a return value of 1. An empty graph returns zero components. As with any array function in C, the caller must provide at least edge_count readable elements.

At most 99 edges are selected, so the total stays between -99,000,000 and 99,000,000, within the range guaranteed for long. The comparison avoids subtracting weights. With E edges and V vertices, insertion sorting and initialization give O(E² + V) worst-case time. Arrays reserve space for the maximum capacities regardless of actual graph size. For larger graphs, replace insertion sort with a suitable O(E log E) sort.

Verification beyond the sample

The function passed 90 automated cases, including connected and disconnected inputs, empty graphs, isolated vertices, equal weights, reversed parallel edges, self-loops, invalid bounds, and maximum permitted totals. For 64 small generated graphs, expected minimum weights came from exhaustive enumeration of candidate forests. Checks also confirm original connectivity is preserved, every selected edge exists in the input, and the input array remains unchanged. This coverage validates the stated bounds; it does not replace testing when changing the representation or limits.

Try one change

Add {2, 3, 6} to the graph. Before running it, predict which components merge. The new result should have two components, five selected edges, and total weight seven; vertex 6 remains isolated. For a different way to grow a tree, continue with the Prim's algorithm lesson.