Depth-first Search

One of the most useful things we can do with a graph is to somehow traverse it. For example, we can start in a node and see which other nodes can be reached from it. In our city graph example you can think about it as seeing which other cities can be reached from our start city.

Depth-first search (or simply DFS) is one of the most used graph traversal algorithms. You start in a node and recursively visit all other unvisited nodes connected to it:

void dfs(int node, List<List<Integer>> graph, boolean visited[]) {
    visited[node] = true;

    for (int neighbour : graph.get(node))
        if (!visited[neighbour])
            dfs(neighbour, graph, visited);
}

We can traverse our example graph above with DFS like this:

void dfs(int node, List<List<Integer>> graph, boolean visited[]) {
    visited[node] = true;

    for (int neighbour : graph.get(node))
        if (!visited[neighbour])
            dfs(neighbour, graph, visited);
}

final int N = 4; // size of the graph
List<List<Integer>> graph = Arrays.asList(
    Arrays.asList(1, 2),
    Arrays.asList(0, 2, 3),
    Arrays.asList(0, 1),
    Arrays.asList(1)
);

boolean[] visited = new boolean[N];

for (int i = 0; i < N; i++)
    if (!visited[i])
        dfs(i, graph, visited);

Let's try to solve the following problem with DFS:

DFS details

It's easy to see that as a result of DFS each node in the graph will be visited at most once. Let's also say we have N vertices and M edges in the graph. DFS will visit or go along each one of them at most once, so the runtime of DFS will be O(N + M).

Connectivity check. Connected components

An undirected graph is called connected if from any node we can reach all the other nodes. In other words, there is a path between any two nodes of the graph.

We can easily check if an undirected graph is connected with DFS: simply run DFS from any node, and check if all the nodes have been visited.

If the graph is not connected, it consists of several connected components: subgraphs of the graph that are connected.

You can solve the following problem to learn more about connected components in practice:

Grid graph

A lot of situations can be modeled as a graph, and often transition to the graph in the problem is not so obvious. Try to solve the following problem and check out the solution to see how the grid can be modeled as a graph:

Finding cycles

With DFS, we can also check if a graph has cycles. Let each node of the graph have one of three states: UNVISITED (we didn't visit it yet), VISITING (we are currently in the DFS function traversing this node and its neighbours), or VISITED (we have finished with the DFS function traversing the node).

Then, we say a graph has a cycle if we are trying to move to a neighbouring node that is currently in the VISITING state, as this means we are trying to move to the node we somehow came from.

To understand more, try to solve the following problem, and then check out the solution:

Practice problems

Here are some more good problems to practice: