Connected Components with DFS

Foundations

A graph is a set of nodes joined by edges. Two nodes joined by an edge are neighbors, and an undirected edge works both ways. Unlike a tree, a graph has no root and may contain cycles, paths that lead back to where they started, so a walk must remember which nodes it has visited, or it can circle forever.

Store a graph as an adjacency list: for each node, the list of its neighbors. With nodes numbered 0 to n - 1, that is a list of lists, and adj[i] holds node i's neighbors, read in O(1) like any array slot. A grid is a graph too: cell (r, c) has up to four neighbors, (r + 1, c), (r - 1, c), (r, c + 1), and (r, c - 1).

Take five nodes, 0 to 4, with adj = [[1], [0, 2], [1], [4], [3]]: node 0 touches 1, node 1 touches 0 and 2, and nodes 3 and 4 touch each other. A depth-first walk from 0 marks 0, 1, and 2, then runs out of unmarked neighbors. Scanning on, node 3 is still unmarked, so it starts a second walk that marks 3 and 4. Two walks mean two connected components.

• Level-Order BFS

  Graphs reuse the two tree walks, depth-first and breadth-first, plus a way to avoid revisiting nodes.

  Open lesson

Case Scenario

Number of Islands is a grid graph: each land cell, "1", is a node, and land cells that touch up, down, left, or right are neighbors. An island is a connected component, so the answer is the number of walks the scan has to start, and marking a visited cell can simply turn its "1" into "0". The example grid has 3 islands.

The direct approach labels every land cell, then repeatedly copies the smaller label from each neighbor until nothing changes, and counts the labels left. A long, winding island passes its label along one cell per round, so it can need as many rounds as it has cells: O((m · n)²) for an m by n grid.