PK

PKBytes

Explore tracks
Chapter 33: BFS, DFS and Graph Connectivity
33.03Intermediate / Advanced5 topics16 min5 interactive animations

Connected components

Connected components split an undirected graph into maximal groups of mutually reachable vertices; one search per unvisited vertex finds them, and grids turn this into islands and flood fill.

Learning goals

  • Count and label components with repeated searches
  • Count islands and fill regions on a grid
  • Collect the size of every region
  • Pick between search and union-find for connectivity

Prerequisites

Breadth-first searchDepth-first search

Are all the computers on a network able to talk to each other? How many separate islands are on a map? Both questions ask for the connected components of a graph.

33.03.1

Undirected components

A **connected component** is a maximal set of vertices in which every two are joined by a path. Every vertex is in exactly one component, and no edge joins two components. To count them, loop over all vertices; whenever you meet one that is unvisited, run a search from it (which marks its entire component) and add 1 to the count.

The loop plus the searches visit each vertex and edge once, so the total is O(n + m). The animation's *Label connected components* option, with the preset of three groups, shows the count increase once per new search start.

Java
1static int countComponentsBfs(List<List<Integer>> g) {
2    boolean[] seen = new boolean[g.size()];
3    int count = 0;
4    for (int start = 0; start < g.size(); start++) {
5        if (seen[start]) continue;
6        count++;                                     // a new, unvisited vertex begins a new component
7        Deque<Integer> queue = new ArrayDeque<>();
8        seen[start] = true;
9        queue.add(start);
10        while (!queue.isEmpty()) {
11            int u = queue.poll();
12            for (int v : g.get(u))
13                if (!seen[v]) { seen[v] = true; queue.add(v); }
14        }
15    }
16    return count;
17}

Components, two-colouring and cycle detection in an undirected graph

Interactive · edit the input

Your input

Try

undirected graph · 8 vertices · 6 edges

0
1
2
3
4
5
6
7
Colour / component AColour / component BComponent CConflictBeing expanded

component of each vertex

-0
-1
-2
-3
-4
-5
-6
-7
Setup

Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.

Step 1 / 13
Java
1int[] components(List<List<Integer>> g) {        // component id per vertex
2    int n = g.size(); int[] comp = new int[n]; Arrays.fill(comp, -1);
3    int id = 0;
4    for (int s = 0; s < n; s++) {
5        if (comp[s] != -1) continue;
6        Deque<Integer> q = new ArrayDeque<>(); q.add(s); comp[s] = id;
7        while (!q.isEmpty()) {
8            int u = q.poll();
9            for (int v : g.get(u)) if (comp[v] == -1) { comp[v] = id; q.add(v); }
10        }
11        id++;                                    // the search ended: one whole component labelled
12    }
13    return comp;
14}
15boolean isBipartite(List<List<Integer>> g) {
16    int n = g.size(); int[] color = new int[n]; Arrays.fill(color, -1);
17    for (int s = 0; s < n; s++) {                // check every component
18        if (color[s] != -1) continue;
19        color[s] = 0; Deque<Integer> q = new ArrayDeque<>(); q.add(s);
20        while (!q.isEmpty()) {
21            int u = q.poll();
22            for (int v : g.get(u)) {
23                if (color[v] == -1) { color[v] = color[u] ^ 1; q.add(v); }
24                else if (color[v] == color[u]) return false;        // an odd cycle
25            }
26        }
27    }
28    return true;
29}
30boolean hasCycle(int n, List<int[]>[] g) {       // undirected; g[u] holds {v, edgeId}
31    boolean[] seen = new boolean[n];
32    for (int s = 0; s < n; s++) if (!seen[s] && dfsCycle(g, s, -1, seen)) return true;
33    return false;
34}
35boolean dfsCycle(List<int[]>[] g, int u, int viaEdge, boolean[] seen) {
36    seen[u] = true;
37    for (int[] e : g[u]) {
38        if (e[1] == viaEdge) continue;           // do not walk back along the edge we came by
39        if (seen[e[0]] || dfsCycle(g, e[0], e[1], seen)) return true;   // a seen vertex reached by another edge: a cycle
40    }
41    return false;
42}

Live state

0 components0 vertices visited

vertices

8

edges

6

No condition evaluated on this step
Execution trace (dry run table)Show 13 steps
StepLineStateWhat happens
1L2vertices=8 edges=6Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.
2L6start=0 component=0Vertex 0 is unlabelled: start component C1 here.
3L9u=0 v=1 component=00 - 1: 1 is unlabelled, so it belongs to C1 too.
4L9u=1 v=2 component=01 - 2: 2 is unlabelled, so it belongs to C1 too.
5L11components=1The queue is empty: component C1 is complete. 1 so far.
6L6start=3 component=1Vertex 3 is unlabelled: start component C2 here.
7L9u=3 v=4 component=13 - 4: 4 is unlabelled, so it belongs to C2 too.
8L11components=2The queue is empty: component C2 is complete. 2 so far.
9L6start=5 component=2Vertex 5 is unlabelled: start component C3 here.
10L9u=5 v=6 component=25 - 6: 6 is unlabelled, so it belongs to C3 too.
11L9u=5 v=7 component=25 - 7: 7 is unlabelled, so it belongs to C3 too.
12L11components=3The queue is empty: component C3 is complete. 3 so far.
13L13return=3 sizes=[3, 2, 3]3 components with sizes [3, 2, 3]. A vertex with no edge is a component of size 1. Cost O(V + E).
33.03.2

Component labeling

Counting is rarely enough: you usually want to know *which* component each vertex belongs to. Keep an array comp[v] and write the current label while searching. Afterwards comp[a] == comp[b] answers "are a and b connected?" in O(1), and grouping by label lists each component.

This is a good place to use an iterative stack, because a component can be as big as the whole graph and a recursive search might overflow on a long path.

Java
1static int[] labelComponents(List<List<Integer>> g) {   // comp[v] = 0, 1, 2, ... in order of the lowest vertex
2    int n = g.size();
3    int[] comp = new int[n];
4    Arrays.fill(comp, -1);
5    int label = 0;
6    for (int s = 0; s < n; s++) {
7        if (comp[s] != -1) continue;
8        Deque<Integer> stack = new ArrayDeque<>();
9        comp[s] = label;
10        stack.push(s);
11        while (!stack.isEmpty()) {
12            int u = stack.pop();
13            for (int v : g.get(u))
14                if (comp[v] == -1) { comp[v] = label; stack.push(v); }
15        }
16        label++;
17    }
18    return comp;
19}

Components, two-colouring and cycle detection in an undirected graph

Interactive · edit the input

Your input

Try

undirected graph · 8 vertices · 6 edges

0
1
2
3
4
5
6
7
Colour / component AColour / component BComponent CConflictBeing expanded

component of each vertex

-0
-1
-2
-3
-4
-5
-6
-7
Setup

Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.

Step 1 / 13
Java
1int[] components(List<List<Integer>> g) {        // component id per vertex
2    int n = g.size(); int[] comp = new int[n]; Arrays.fill(comp, -1);
3    int id = 0;
4    for (int s = 0; s < n; s++) {
5        if (comp[s] != -1) continue;
6        Deque<Integer> q = new ArrayDeque<>(); q.add(s); comp[s] = id;
7        while (!q.isEmpty()) {
8            int u = q.poll();
9            for (int v : g.get(u)) if (comp[v] == -1) { comp[v] = id; q.add(v); }
10        }
11        id++;                                    // the search ended: one whole component labelled
12    }
13    return comp;
14}
15boolean isBipartite(List<List<Integer>> g) {
16    int n = g.size(); int[] color = new int[n]; Arrays.fill(color, -1);
17    for (int s = 0; s < n; s++) {                // check every component
18        if (color[s] != -1) continue;
19        color[s] = 0; Deque<Integer> q = new ArrayDeque<>(); q.add(s);
20        while (!q.isEmpty()) {
21            int u = q.poll();
22            for (int v : g.get(u)) {
23                if (color[v] == -1) { color[v] = color[u] ^ 1; q.add(v); }
24                else if (color[v] == color[u]) return false;        // an odd cycle
25            }
26        }
27    }
28    return true;
29}
30boolean hasCycle(int n, List<int[]>[] g) {       // undirected; g[u] holds {v, edgeId}
31    boolean[] seen = new boolean[n];
32    for (int s = 0; s < n; s++) if (!seen[s] && dfsCycle(g, s, -1, seen)) return true;
33    return false;
34}
35boolean dfsCycle(List<int[]>[] g, int u, int viaEdge, boolean[] seen) {
36    seen[u] = true;
37    for (int[] e : g[u]) {
38        if (e[1] == viaEdge) continue;           // do not walk back along the edge we came by
39        if (seen[e[0]] || dfsCycle(g, e[0], e[1], seen)) return true;   // a seen vertex reached by another edge: a cycle
40    }
41    return false;
42}

Live state

0 components0 vertices visited

vertices

8

edges

6

No condition evaluated on this step
Execution trace (dry run table)Show 13 steps
StepLineStateWhat happens
1L2vertices=8 edges=6Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.
2L6start=0 component=0Vertex 0 is unlabelled: start component C1 here.
3L9u=0 v=1 component=00 - 1: 1 is unlabelled, so it belongs to C1 too.
4L9u=1 v=2 component=01 - 2: 2 is unlabelled, so it belongs to C1 too.
5L11components=1The queue is empty: component C1 is complete. 1 so far.
6L6start=3 component=1Vertex 3 is unlabelled: start component C2 here.
7L9u=3 v=4 component=13 - 4: 4 is unlabelled, so it belongs to C2 too.
8L11components=2The queue is empty: component C2 is complete. 2 so far.
9L6start=5 component=2Vertex 5 is unlabelled: start component C3 here.
10L9u=5 v=6 component=25 - 6: 6 is unlabelled, so it belongs to C3 too.
11L9u=5 v=7 component=25 - 7: 7 is unlabelled, so it belongs to C3 too.
12L11components=3The queue is empty: component C3 is complete. 3 so far.
13L13return=3 sizes=[3, 2, 3]3 components with sizes [3, 2, 3]. A vertex with no edge is a component of size 1. Cost O(V + E).
33.03.3

Number of islands

A grid is an implicit graph: each cell is a vertex and two land cells are joined if they touch up, down, left or right. The **number of islands** is the number of connected components of land cells, so scan the grid and start a search at every land cell not seen before.

Each cell is visited once and has four neighbours, so the time is O(rows x cols). Switch the animation to *Count islands* to watch each search colour one island.

Java
1static int numIslands(int[][] grid) {                 // 1 = land, 0 = water; 4-direction connectivity
2    int rows = grid.length, cols = grid[0].length, islands = 0;
3    boolean[][] seen = new boolean[rows][cols];
4    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
5    for (int r = 0; r < rows; r++)
6        for (int c = 0; c < cols; c++) {
7            if (grid[r][c] == 0 || seen[r][c]) continue;
8            islands++;
9            Deque<int[]> stack = new ArrayDeque<>();
10            seen[r][c] = true;
11            stack.push(new int[]{r, c});
12            while (!stack.isEmpty()) {
13                int[] cell = stack.pop();
14                for (int[] d : dirs) {
15                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
16                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && !seen[nr][nc]) {
17                        seen[nr][nc] = true;
18                        stack.push(new int[]{nr, nc});
19                    }
20                }
21            }
22        }
23    return islands;
24}

Flood fill and counting islands (DFS with a stack)

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
1
0
0
1
1
0
0
1
2
0
0
1
1
Cell being expandedVisited landStart of a new islandWater
Setup

Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.

Step 1 / 10
Java
1static int countIslands(int[][] g) {
2    int count = 0;
3    for (int r = 0; r < g.length; r++)
4        for (int c = 0; c < g[0].length; c++)
5            if (g[r][c] == 1) { count++; fill(g, r, c); }        // each unvisited land cell starts an island
6    return count;
7}
8static int fill(int[][] g, int sr, int sc) {                      // iterative DFS, marks land as 2
9    Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{sr, sc}); g[sr][sc] = 2; int size = 0;
10    while (!stack.isEmpty()) {
11        int[] cell = stack.pop(); size++;
12        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
13            int r = cell[0] + d[0], c = cell[1] + d[1];
14            if (r >= 0 && r < g.length && c >= 0 && c < g[0].length && g[r][c] == 1) { g[r][c] = 2; stack.push(new int[]{r, c}); }
15        }
16    }
17    return size;
18}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L2R=3 C=4Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.
2L5r=0 c=0 islands=1Unvisited land at (0,0): island number 1 begins.
3L11cell=(0,0) islands=1 size=1Pop (0,0). Unvisited land neighbours pushed: (0,1), (1,0).
4L11cell=(1,0) islands=1 size=2Pop (1,0). No unvisited land neighbours.
5L11cell=(0,1) islands=1 size=3Pop (0,1). No unvisited land neighbours.
6L5r=1 c=3 islands=2Unvisited land at (1,3): island number 2 begins.
7L11cell=(1,3) islands=2 size=1Pop (1,3). Unvisited land neighbours pushed: (2,3).
8L11cell=(2,3) islands=2 size=2Pop (2,3). Unvisited land neighbours pushed: (2,2).
9L11cell=(2,2) islands=2 size=3Pop (2,2). No unvisited land neighbours.
10L6return=22 islands. Every cell is visited at most once: O(R x C) time, O(R x C) stack in the worst case.
33.03.4

Flood fill

**Flood fill** is the paint-bucket tool: starting at a cell, change the colour of every cell reachable through cells of the *same* original colour. It is one search from the start cell, not a scan of the whole grid.

One trap: if the new colour equals the old colour, nothing should change, and a search that marks cells by their colour would never stop. Return early in that case. The animation's *Flood fill from the start cell* option shows the stack and the filled region.

Java
1static int[][] floodFill(int[][] image, int sr, int sc, int colour) {
2    int old = image[sr][sc];
3    if (old == colour) return image;                 // already that colour: nothing to do (and no endless loop)
4    int rows = image.length, cols = image[0].length;
5    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
6    Deque<int[]> stack = new ArrayDeque<>();
7    image[sr][sc] = colour;
8    stack.push(new int[]{sr, sc});
9    while (!stack.isEmpty()) {
10        int[] cell = stack.pop();
11        for (int[] d : dirs) {
12            int nr = cell[0] + d[0], nc = cell[1] + d[1];
13            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == old) {
14                image[nr][nc] = colour;              // repainting is the visited mark
15                stack.push(new int[]{nr, nc});
16            }
17        }
18    }
19    return image;
20}

Flood fill and counting islands (DFS with a stack)

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
1
0
0
1
1
0
0
1
2
0
0
1
1
Cell being expandedVisited landStart of a new islandWater
Setup

Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.

Step 1 / 10
Java
1static int countIslands(int[][] g) {
2    int count = 0;
3    for (int r = 0; r < g.length; r++)
4        for (int c = 0; c < g[0].length; c++)
5            if (g[r][c] == 1) { count++; fill(g, r, c); }        // each unvisited land cell starts an island
6    return count;
7}
8static int fill(int[][] g, int sr, int sc) {                      // iterative DFS, marks land as 2
9    Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{sr, sc}); g[sr][sc] = 2; int size = 0;
10    while (!stack.isEmpty()) {
11        int[] cell = stack.pop(); size++;
12        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
13            int r = cell[0] + d[0], c = cell[1] + d[1];
14            if (r >= 0 && r < g.length && c >= 0 && c < g[0].length && g[r][c] == 1) { g[r][c] = 2; stack.push(new int[]{r, c}); }
15        }
16    }
17    return size;
18}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L2R=3 C=4Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.
2L5r=0 c=0 islands=1Unvisited land at (0,0): island number 1 begins.
3L11cell=(0,0) islands=1 size=1Pop (0,0). Unvisited land neighbours pushed: (0,1), (1,0).
4L11cell=(1,0) islands=1 size=2Pop (1,0). No unvisited land neighbours.
5L11cell=(0,1) islands=1 size=3Pop (0,1). No unvisited land neighbours.
6L5r=1 c=3 islands=2Unvisited land at (1,3): island number 2 begins.
7L11cell=(1,3) islands=2 size=1Pop (1,3). Unvisited land neighbours pushed: (2,3).
8L11cell=(2,3) islands=2 size=2Pop (2,3). Unvisited land neighbours pushed: (2,2).
9L11cell=(2,2) islands=2 size=3Pop (2,2). No unvisited land neighbours.
10L6return=22 islands. Every cell is visited at most once: O(R x C) time, O(R x C) stack in the worst case.
33.03.5

Region sizes

Counting the cells found by each search gives the **size** of each region. Collect the sizes in a list to get the largest island, the smallest, or a size distribution. The only change from counting islands is a counter that restarts at each new search and is saved when the search ends.

Sizes are also how you answer "is this region big enough?" problems, such as the area of the biggest island or the number of cells that can never reach the border.

Java
1static List<Integer> regionSizes(int[][] grid) {      // size of every 4-connected group of 1s, in scan order
2    int rows = grid.length, cols = grid[0].length;
3    boolean[][] seen = new boolean[rows][cols];
4    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
5    List<Integer> sizes = new ArrayList<>();
6    for (int r = 0; r < rows; r++)
7        for (int c = 0; c < cols; c++) {
8            if (grid[r][c] == 0 || seen[r][c]) continue;
9            int size = 0;
10            Deque<int[]> stack = new ArrayDeque<>();
11            seen[r][c] = true;
12            stack.push(new int[]{r, c});
13            while (!stack.isEmpty()) {
14                int[] cell = stack.pop();
15                size++;
16                for (int[] d : dirs) {
17                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
18                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && !seen[nr][nc]) {
19                        seen[nr][nc] = true;
20                        stack.push(new int[]{nr, nc});
21                    }
22                }
23            }
24            sizes.add(size);
25        }
26    return sizes;
27}

Flood fill and counting islands (DFS with a stack)

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
1
0
0
1
1
0
0
1
2
0
0
1
1
Cell being expandedVisited landStart of a new islandWater
Setup

Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.

Step 1 / 10
Java
1static int countIslands(int[][] g) {
2    int count = 0;
3    for (int r = 0; r < g.length; r++)
4        for (int c = 0; c < g[0].length; c++)
5            if (g[r][c] == 1) { count++; fill(g, r, c); }        // each unvisited land cell starts an island
6    return count;
7}
8static int fill(int[][] g, int sr, int sc) {                      // iterative DFS, marks land as 2
9    Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{sr, sc}); g[sr][sc] = 2; int size = 0;
10    while (!stack.isEmpty()) {
11        int[] cell = stack.pop(); size++;
12        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
13            int r = cell[0] + d[0], c = cell[1] + d[1];
14            if (r >= 0 && r < g.length && c >= 0 && c < g[0].length && g[r][c] == 1) { g[r][c] = 2; stack.push(new int[]{r, c}); }
15        }
16    }
17    return size;
18}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L2R=3 C=4Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.
2L5r=0 c=0 islands=1Unvisited land at (0,0): island number 1 begins.
3L11cell=(0,0) islands=1 size=1Pop (0,0). Unvisited land neighbours pushed: (0,1), (1,0).
4L11cell=(1,0) islands=1 size=2Pop (1,0). No unvisited land neighbours.
5L11cell=(0,1) islands=1 size=3Pop (0,1). No unvisited land neighbours.
6L5r=1 c=3 islands=2Unvisited land at (1,3): island number 2 begins.
7L11cell=(1,3) islands=2 size=1Pop (1,3). Unvisited land neighbours pushed: (2,3).
8L11cell=(2,3) islands=2 size=2Pop (2,3). Unvisited land neighbours pushed: (2,2).
9L11cell=(2,2) islands=2 size=3Pop (2,2). No unvisited land neighbours.
10L6return=22 islands. Every cell is visited at most once: O(R x C) time, O(R x C) stack in the worst case.

Practice ladder

Now try it yourself

Easy

  • Flood Fill
  • Island Perimeter

Medium

  • Number of Islands
  • Max Area of Island
  • Number of Provinces
  • Number of Connected Components in an Undirected Graph

Advanced

  • Surrounded Regions
  • Number of Enclaves
  • Making A Large Island

Key takeaways

  • Loop over vertices and start a search whenever one is unvisited; the number of starts is the number of components.
  • Store a label per vertex to answer connectivity queries in O(1).
  • A grid is an implicit graph; islands are its components and flood fill is one search.
  • Count cells in each search to get region sizes.