Connected pieces of a graph
Read these first if they are new to you
The idea in one paragraph
A graph often falls into separate pieces, with no edge from one piece to another. Each piece is a connected component: a group of nodes you can travel between along edges. A program finds the pieces by starting at any node and spreading out to neighbors, then neighbors of neighbors, until nothing new turns up. Cutting an edge can split a piece in two, but only if there was no other route around it.
A connected component is everything you can reach from a node
A path in a graph is a walk from node to node along edges. Two nodes are connected if some path joins them. A connected component, or piece, is a largest group of nodes that are all connected to each other. Every node belongs to exactly one piece; a node with no edges is a piece by itself.
Some edges are the only route between two parts of a piece. Cutting such an edge, called a bridge, splits the piece in two. An edge that lies on a loop, called a cycle, is never a bridge: after the cut, the walk the other way around the loop still joins its two ends.
Spread out from a node until nothing new turns up
To label every piece, a program repeats one search. It picks a node that has no label yet and gives it a new label. Then it visits that node's neighbors, labels them the same, and visits their neighbors in turn. When it runs out of new nodes, the piece is done. It then picks the next unlabeled node and starts a new piece. This spreading search is called breadth-first search, because it finishes all nodes one step away before those two steps away.
Nodes 1 to 7, with edges 1–2, 2–3, 3–1, 4–5 and 5–7.
- Start at 1 and label it "piece 1." Its neighbors 2 and 3 get the same label. Their neighbors are all labeled already, so piece 1 is {1, 2, 3}.
- The next unlabeled node is 4. It starts piece 4. Its neighbor 5 joins, then 5's neighbor 7. Piece 4 is {4, 5, 7}.
- Node 6 has no edges, so it is piece 6 by itself: {6}. There are 3 pieces.
- Now cut the edge 4–5. Node 4 is left alone, and 5 and 7 form their own piece: 4 pieces in all. Cutting 1–2 instead would split nothing, because 1 still reaches 2 through 3.
Your turn. Nodes A to F, with edges A–B, B–C, C–D, D–A and E–F. How many pieces are there? Which single cut would raise the count?
Answer
Two pieces: {A, B, C, D} and {E, F}. A, B, C and D form a loop, so no single cut there splits it. Only cutting E–F raises the count, to three.
This page covers graphs whose edges work both ways. When edges have a direction, "connected" splits into two ideas, depending on whether you must follow the arrows. Also, programs that handle millions of nodes, or edges that arrive one at a time, often use a different method called union–find; it finds the same pieces.
cc.py: label each node with its piece by breadth-first search
from collections import deque
def components(nodes, edges):
neighbors = {n: [] for n in nodes}
for u, v in edges:
neighbors[u].append(v)
neighbors[v].append(u)
label = {}
for start in nodes:
if start in label: # already labeled: skip to the next node
continue
label[start] = start # name the piece after its first node
queue = deque([start])
while queue: # repeat until the queue is empty
n = queue.popleft() # take the node that arrived first
for m in neighbors[n]:
if m not in label:
label[m] = start
queue.append(m)
return label
nodes = [1, 2, 3, 4, 5, 6, 7]
edges = [(1, 2), (2, 3), (3, 1), (4, 5), (5, 7)]
print(components(nodes, edges))
edges.remove((4, 5)) # cut one edge
print(components(nodes, edges))
{1: 1, 2: 1, 3: 1, 4: 4, 5: 4, 7: 4, 6: 6}
{1: 1, 2: 1, 3: 1, 4: 4, 5: 5, 7: 5, 6: 6}
A deque is a queue: nodes leave in the order they arrived, which keeps the search
breadth-first. Each output maps a node to the first node of its piece.
Check yourself
-
A graph has 10 nodes and no edges. How many pieces does it have?
Answer
10. Each node is a piece by itself.
-
Five nodes are joined in a line: 1–2, 2–3, 3–4, 4–5. You cut one edge. How many pieces are there now? What if the line were closed into a ring with the edge 5–1?
Answer
Two, whichever edge you cut: every edge of a line is a bridge. In a ring, one cut leaves a single piece, because every edge lies on the loop.
-
A shape is stored as points, with an edge between any two points closer than 1 unit. The graph has two pieces. What does that say about the shape?
Answer
The points form two separate clusters: no point of one lies within 1 unit of any point of the other.
Go further
Optional background, for readers who want more than this page.
-
Watch a breadth-first search spread across a map step by step, with short code.
-
How components are found in practice, including union–find for graphs that grow.
Where this shows up
No unit or explanation builds on this one yet.