AlgoVerse

Connected components

Group the nodes of an undirected graph by whether they can reach each other: each unlabelled node starts a new search.

In an undirected graph, a connected component is a largest group of nodes that can all reach each other. To find every component:

Read the full explanation ↓
Input:
V=8 · E=6 · src=APDF export

Three components: a triangle, a three-node chain and a pair.

  1. def components(graph, src):
  2. comp = {v: 0 for v in graph}
  3. count = 0
  4. for s in graph:
  5. if comp[s] == 0:
  6. count = count + 1
  7. comp[s] = count
  8. stack = [s]
  9. while stack:
  10. u = stack.pop()
  11. for v, _ in graph[u]:
  12. if comp[v] == 0:
  13. comp[v] = count
  14. stack.append(v)
  15. return comp

Invariant: Nodes with the same (non-zero) label can reach each other; nodes with different labels cannot.

Start

ABCDEFGH
  • Current node (u)
  • Search tree (from parent)
  • Edge being checked

Stack stack

empty

Local variables

src'A'

Orange = changed in this step

graph dict
  • 'A': [('B', 1), ('C', 1)]
  • 'B': [('A', 1), ('C', 1)]
  • 'C': [('B', 1), ('A', 1)]
  • 'D': [('E', 1)]
  • 'E': [('D', 1), ('F', 1)]
  • 'F': [('E', 1)]
  • 'G': [('H', 1)]
  • 'H': [('G', 1)]

Call stack

  1. components()line 1
Step 1 of 91
Black = new_component · Orange = key steptry_start: 0/8 · new_component: 0/3 · visit: 0/8 · check: 0/12 · label: 0/5

    How the work grows with input size

    Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • check
    • visit
    • current input (n=8)
    050100481216202428n = number of nodescheckvisit
    Show as a table
    ncheckvisit
    410.44
    827.68
    1241.612
    165616
    2070.820
    2474.424
    2894.428
    Explanation

    The idea

    In an undirected graph, a connected component is a largest group of nodes that can all reach each other. To find every component:

    1. Go through the nodes in order.
    2. If a node has no label yet, increase the component counter and start a search from it (here a DFS with a stack); every node the search reaches gets the same label.

    Cost

    Every node is labelled once and every edge is checked at most twice: O(V + E).

    What to watch in the trace

    • The number next to each node is its component number (0 means not labelled yet).
    • The stack is under the picture; use the "every loop round" detail level to see only the start of each new component.