Reachability and connected components

After this page, you should be able to:

• Distinguish a single reachable region from a full component partition.

• Explain shared discovery state, isolated vertices and directed-connectivity limits.

Builds on: BFS, DFS and graph direction.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

JavaScript graphs use Map; Julia graphs use Dict. Stored neighbour order is preserved, but Julia Dict vertex iteration can change valid component ordering or tied choices. The shared DequeBuffer supplies constant-time linked endpoints. The figures and check answers use Python’s declared iteration order.

A single start explores only what it can reach¶

On the shared undirected graph, BFS or DFS from A reaches A through G and stops. H is never discovered. This is correct single-source traversal: reaching every graph vertex is a different requirement, requiring additional starts when the graph is disconnected.

Starting at isolated H reaches H itself. An empty graph has no valid starting label, but it does have a well-defined full-graph component result: no components.

Components partition an undirected graph¶

A connected component is a maximal group of vertices connected by paths. “Maximal” means no additional vertex from this graph can be added while preserving that property. In an undirected graph, every vertex belongs to exactly one component, including singleton components for isolated vertices.

The component groups are {A, B, C, D, E, F, G} and {H}. Within a group, list order is a traversal choice. Component membership does not depend on which vertex happens to be processed first.

Return a partition of the whole undirected graph¶

connected_components(graph) returns a new list of component vertex lists. Every graph vertex appears exactly once, including isolated vertices; {} returns []. It does not mutate the graph or return all connecting edges. Outer dictionary order chooses component starts; stored neighbour order chooses each group’s traversal order. Membership is independent of these order choices.

Reciprocal undirected adjacency is a precondition, not something the function verifies. Group lists contain references to the original labels. Reordering a returned list does not edit the graph, and a returned partition is a snapshot rather than automatically updated state.

Restart with one shared discovered set¶

This routine assumes undirected, reciprocal adjacency lists. It imports deque explicitly and iterates vertices in dictionary insertion order.

from collections import deque

def connected_components(graph):
    seen, groups = set(), []
    for start in graph:
        if start in seen:
            continue
        seen.add(start)
        queue, group = deque([start]), []
        while queue:
            u = queue.popleft()
            group.append(u)
            for v in graph[u]:
                if v not in seen:
                    seen.add(v)
                    queue.append(v)
        groups.append(group)
    return groups

function connected_components(graph) {
    const seen = new Set(), groups = [];
    for (const start of graph.keys()) {
        if (seen.has(start)) continue;
        seen.add(start); const queue = new DequeBuffer([start]), group = [];
        while (!queue.is_empty()) {
            const u = queue.remove_first(); group.push(u);
            for (const v of graph.get(u)) if (!seen.has(v)) { seen.add(v); queue.add_last(v); }
        }
        groups.push(group);
    }
    return groups;
}

function connected_components(graph)
    seen = Set{Any}(); groups = Any[]
    for start in keys(graph)
        start in seen && continue
        push!(seen, start); queue = DequeBuffer([start]); group = Any[]
        while queue.n > 0
            u = db_remove_first!(queue); push!(group, u)
            for v in graph[u]
                if !(v in seen); push!(seen, v); db_add_last!(queue, v); end
            end
        end
        push!(groups, group)
    end
    return groups
end

For the shared graph, the result is [['A', 'B', 'C', 'D', 'E', 'F', 'G'], ['H']]. After A’s traversal, the outer checks at B through G do not launch another search because those vertices are already seen. H starts the second search.

Several starts produce a forest¶

If parent links were also recorded, each component’s start would have no parent and each other vertex would have one discovery parent. These traversal trees form a forest. The original graph can still have cycles and many non-tree edges; the discovery forest records how the algorithm reached vertices, not all the graph’s connections.

The shared seen set is essential. Resetting it for every outer-loop vertex would repeat traversals and output overlapping groups rather than a partition.

Directed connectivity asks different questions¶

For outgoing lists A: [B], B: [], C: [B], both A and C can reach B, but neither reaches the other. Running the undirected restart routine on those lists can produce groups dependent on outer order. Those groups are not a valid general definition of directed components.

Weak connectivity ignores arrow direction when testing connection. Strong connectivity requires a directed path in both directions between every pair within a group. They need appropriate algorithms; a sequence of outgoing-only BFS restarts does not compute either notion in general.

Costs and implementation choices¶

All restarts together discover n vertices and scan 2m neighbour entries, giving O(n+m+1) time with expected hash-table costs. Returned groups hold Θ(n+1) references; the seen set and queue require O(n+1) additional working storage. No copy of every original edge is needed.

BFS or DFS can produce the same undirected partition with different list orders and memory shapes. Use a full traversal when the graph is available and the partition is needed once. Union–find instead maintains merge/connectivity information across arriving edges; its parent arrays do not automatically provide member lists or actual routes.

Check your understanding¶

Predict the result or state change before opening the explanation.

1. After completing the shared graph from A, must the outer loop traverse again from B?

2. Does removing an edge from the graph automatically update previously returned component groups?

Next: Traversal costs and choices.