Connected components

Overview

In an undirected graph, a connected component is a maximal island of vertices all reachable from one another. To find them, sweep every vertex with a single shared visited array: each time you meet an unvisited vertex you have found a new component, and a DFS from it floods the whole island.

Why it matters

Components answer 'is this network in one piece?', 'how many separate clusters are there?', 'how big is the largest cluster?'. They appear in clustering, image segmentation, network reliability, and union-find problems.

Core concepts

One shared visited array across the whole outer sweep — that is what prevents counting a component twice.

Component count = number of DFS starts.

Component size = number of vertices a single DFS marks; track the maximum for the largest component.

Undirected assumption. Reachability is symmetric, so a plain DFS suffices (directed graphs need the stronger notion of strongly connected components).

Syntax notes

#include <stdlib.h>

static int flood(const int *adj, int n, int v, int *vis) {
    vis[v] = 1;
    int size = 1;                                  /* this vertex counts */
    for (int u = 0; u < n; u++)
        if (adj[v*n + u] && !vis[u]) size += flood(adj, n, u, vis);
    return size;
}

void components(const int *adj, int n, int *count, int *largest) {
    int *vis = calloc((size_t)n, sizeof *vis);     /* ONE array for the whole sweep */
    if (!vis) { *count = *largest = -1; return; }
    *count = 0; *largest = 0;
    for (int i = 0; i < n; i++)
        if (!vis[i]) {                             /* a vertex not yet reached = new component */
            int s = flood(adj, n, i, vis);
            (*count)++;
            if (s > *largest) *largest = s;
        }
    free(vis);
}

Key points:

• The visited array is allocated once, outside the sweep — resetting it per iteration would count every vertex as its own component.
• Each DFS returns the size it flooded, so counting and sizing come from one pass.
• Assumes an undirected (symmetric) matrix; on a directed graph this computes something else entirely.

Lesson

An undirected graph splits into connected components — maximal groups where every pair is linked by some path. Sweep the vertices with one shared visited array: each time you find an unvisited vertex, a DFS floods its entire component. The number of floods is the component count, and the size of each flood measures that component.

Code examples

#include <stdio.h> static int n=6; /* undirected: {0-1-2} and {3-4}, 5 isolated */ static int adj[36]={ 0,1,1,0,0,0, 1,0,1,0,0,0, 1,1,0,0,0,0, 0,0,0,0,1,0, 0,0,0,1,0,0, 0,0,0,0,0,0 }; static int dfs(int v,int vis){ vis[v]=1; int s=1; for(int u=0;u<n;u++) if(adj[vn+u]&&!vis[u]) s+=dfs(u,vis); return s; } int main(void){ int vis[6]={0}, comps=0, biggest=0; for(int i=0;i<n;i++) if(!vis[i]){ int s=dfs(i,vis); comps++; if(s>biggest)biggest=s; } printf("components=%d largest=%d\n", comps, biggest); return 0; }

Line by line

Common mistakes

Resetting the visited array inside the loop (over-counts). Returning the number of components when asked for the largest size, or vice-versa. Applying this directly to a directed graph and expecting strongly-connected components.

Debugging tips

Compiler errors and warnings:

• -Wunused-result style warnings if you call flood and discard the size when you meant to use it.
• No warning for allocating the visited array inside the loop.

Runtime symptoms:

• The component count equals the vertex count. The visited array is being allocated or cleared inside the sweep, so every vertex looks new. Allocate it once.
• Only one component is ever found. You returned after the first flood instead of continuing the sweep.
• Isolated vertices are missed. A vertex with no edges still forms a component of size 1 — the sweep must visit every index, not just those with edges.
• Wrong on a directed graph. This algorithm assumes symmetry; directed graphs need strongly connected components (Tarjan/Kosaraju), which is a different algorithm.
• Stack overflow on a big component. Recursion depth reaches the component size; use an iterative flood for large graphs.

Technique: print the component id assigned to each vertex. A correct run partitions the vertices; a broken sweep shows every vertex with its own id.

Memory safety

• One allocation for the whole sweep. Beyond correctness, allocating inside the loop is an easy way to leak n arrays if any path forgets to free.
• Recursion depth equals the largest component. A single connected component spanning 100,000 vertices means 100,000 frames — convert to an explicit stack or BFS for large inputs.
• calloc is required so "unvisited" is the initial state; malloc garbage reads as visited and silently truncates components.
• Output parameters. components writes through count and largest; both must point at valid storage, and the failure path must still set them to something defined rather than leaving the caller's variables untouched.
• Symmetric-matrix precondition. Nothing detects a directed matrix; document the requirement.
• Free on every path.

Real-world uses

Concrete uses: Detecting whether a network has become partitioned, clustering related records, counting islands in a grid, finding groups of mutual friends, image segmentation by connected regions, and checking whether a circuit or mesh is fully wired. Union-find solves the same problem incrementally and is preferred when edges arrive over time rather than being known up front.

Professional best practices:

Beginner:

• Allocate the visited array once, outside the sweep.
• Remember an isolated vertex is a component.

Intermediate:

• Use union-find when edges are added dynamically; use the DFS sweep when the graph is static.
• For directed graphs, be explicit about whether you need weak or strong connectivity — they give different answers.
• Record a component id per vertex rather than just a count when downstream code needs to group by component.

Practice tasks

1. (Beginner) Count components. Implement int count_components(const int *adj, int n) using one shared visited array. Example: the demo graph -> 3. Concepts: sweep + flood.

2. (Beginner) Largest component. Implement int largest_component_size(const int *adj, int n). Example: -> 3. Concepts: flood returning a size.

3. (Intermediate) Label every vertex. Assign each vertex a component id and print the partition. Concepts: component ids rather than a bare count.

4. (Intermediate) Union-find version. Solve the same problem with union-find and confirm both agree on random graphs. Concepts: incremental vs sweep-based connectivity.

Summary

A connected component is a maximal group of mutually reachable vertices, and you find them by sweeping every vertex with a single shared visited array: each time the sweep meets an unvisited vertex, a DFS floods that entire component. The number of floods is the component count and the size each flood returns gives the largest. Allocating or clearing the visited array inside the sweep is the classic bug — it makes every vertex look like a new component. Isolated vertices still count, calloc supplies the correct unvisited default, and recursion depth can reach the size of the largest component, so large graphs want an iterative flood. Note this assumes an undirected graph; directed graphs need strongly-connected-component algorithms instead.

Practice with these exercises

• Count connected components
• Largest component size