## Types of DFS

There are a few "types" of depth-first search questions that you may encounter in coding interviews. Here are a couple of examples:

### Connected Components

These types of problems use DFS to identify the number of connected components in a graph. An example of this is finding the number of islands in a matrix, where each "1" represents a cell of land.

- We traverse over each unvisited cell in the matrix.
- If the cell contains a 1, then we use DFS to traverse all land cells neighboring that cell (marking cells as visited as we go).
- When that completes, we have fully explored a single island, and we move onto the next island, which is the next unvisited cell in the matrix that contains a 1.

Here's what that looks like animated:

0 / 12

2x

### Boundary DFS

These types of problems involve starting a DFS traversal from the boundary of a matrix. An example of this is finding all "1"s that are connected to the boundary of a matrix, which is a key step in solving the "Surronded Regions" problem:

0 / 12

2x

Compare UsCompare to Interviewing.io

Â© 2024 Optick Labs Inc. All rights reserved.

Loading comments...