What is Depth First Search

The Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores all the nodes by going forward if possible or uses backtracking.

Algorithm

The DFS can be easily implemented as a recursive method. Here are steps:

• Mark a current node as visited
• Visit recursively all the nodes that are adjacent to a current node and that have not yet been marked as visited.

Here is an implementation of DFS algorithm

    public void Dfs(Graph graph, int vertex)
    {
        // Mark a vertex as visited
        _visited[vertex] = true;

        // Visit adjacent vertices
        foreach(int adjacent in graph.Adjacents(vertex))
        {
            // Visit not visited vertex
            if (_visited[adjacent] == false)
            {
                Dfs(graph, adjacent);
            }
        }
    }

DFS example

Let's see how the Depth First Search algorithm works with an example. We use an undirected graph with 4 vertices.

 

 

The adjacency-lists for the graph will be:

0: 1, 3
1: 0, 3
2: 3
3: 0, 1, 2

and the _visited array is empty.

We start from vertex 0

• mark vertex 0 as visited: _visited[0] = true
• visit adjacent vertices (1, 3) for vertex 0

 

 

Process vertex 1:

• vertex 1 was not visited
• visit vertex 1
• mark vertex 1 as visited _visited[1] = true
• visit adjacent vertices (0, 3) for vertex 1

 

 

Process vertex 0:

• vertex 0 was visited
• skip vertex 0

Process vertex 3:

• vertex 3 was not visited
• Visit vertex 3
• mark vertex 3 as visited _visited[3] = true
• visit adjacent vertices (0, 1, 2) for vertex 3

 

 

Process vertex 0:

• vertex 0 was visited
• skip vertex 0

Process vertex 1:

• vertex 1 was visited
• skip vertex 1

Process vertex 2:

• vertex 2 was not visited
• Visit vertex 2
• mark vertex 2 as visited _visited[2] = true
• visit adjacent vertices (3) for vertex 2

 

 

The DFS visited all not visited vertices. Because we were using recursion the algorithm will backtrack but will not visit any vertices (all vertices already were visited)

Time complexity

The time complexity for DFSis O(V + E) where V is the number of vertices and E is the number of edges