Depth First Search


Reading time: 15 minutes | Coding time: 5 minutes

Depth-first search (DFS) algorithm is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

DFS is one of the most useful graph search algorithms.

dfs

Pseudo-code pf DFS:


dfs (v):
        color[v] = gray
        for u in adj[v]:
                if color[u] == white
                        then dfs(u)
        color[v] = black

This recursive nature of DFS can be implemented using stacks. The steps are as follows:

  • Pick a starting node and push all its child nodes into a stack.
  • Pop a node from stack to select the next node to visit and push all its child nodes into a stack.
  • Repeat this process until the stack is empty. Ensure that the nodes that are visited are marked. This will prevent you from visiting the same node more than once and hence, avoid an infinite loop.

Complexity

  • Worst case time complexity: Θ(V+E)
  • Average case time complexity: Θ(V+E)
  • Best case time complexity: Θ(V+E)
  • Space complexity: Θ(V)

Implementations


Implementation of Depth First Search algorithm in 7 languages that includes C, C++, Java, Go, Kotlin, Ruby and Python.

  • C
  • C++
  • Java
  • Kotlin
  • Python
  • Go
  • Ruby

C


#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node* next;
};
int push(struct node** head,int element);
int pop(struct node** head,int* element);
//main program
int main()
{
    //input no of nodes: Num
    int Num;
    printf("Enter number of nodes\n");
    scanf("%d",&Num);
    //create adjacency matrix
    int adj[Num][Num];
    //input adjacency matrix
    printf("Enter adjacency matrix\n");
    for(int i=0;i<Num;i++)
    {
        for(int j=0;j<Num;j++)
        {
            scanf("%d",&adj[i][j]);
        }
    }
    //DFS traversing
    //create a stack
    struct node *Stack=NULL;
    //create status array and set it to ready state
    enum{ready,waiting,processed};
    int status[Num];
    for(int i=0;i<Num;i++)
    {
        status[i]=ready;
    }
    //add first node to stack
    push(&Stack,0);
    status[0]=waiting;
    int node=NULL;
    printf("DFS traversing\n");
    while(Stack!=NULL)
    {
        //get a node from stack, display it and change status to processed
        pop(&Stack,&node);
        printf("%d ",node);
        status[node]=processed;
        //add it's neighbours with status ready to stack
        for(int i=0;i<Num;i++)
        {
            if(adj[node][i]==1 && status[i]==ready)
            {
                push(&Stack,i);
                status[i]=waiting;
            }
        }
    }
    printf("\n");
}
//stack functions
int push(struct node** head,int element)
{
    struct node* temp;
    temp=*head;
    *head=(struct node*)malloc(sizeof(struct node));
    if(head==NULL)
        return 1;
    (*head)->data=element;
    (*head)->next=temp;
    return 0;
}
int pop(struct node** head,int* element)
{
    if(*head==NULL)
        return 1;
    *element=(*head)->data;
    struct node* temp;
    temp=*head;
    *head=(*head)->next;
    free(temp);
    return 0;
}
  

C++


#include <iostream>
#include <map>
#include <set>
/* Part of Cosmos by OpenGenus Foundation */
void dfs(int current,                           // the node that we are currently at
         std::map<int, std::set<int>>& adjList, // the adjacency list for each node
         std::map<int, bool>& visited) {        // the 'visited' state for each node
    if (visited[current]) return;
    visited[current] = true;
    for (auto neighbour : adjList[current]) {
        dfs(neighbour, adjList, visited);
    }
}
void addEdge(int a, int b, std::map<int, std::set<int>>& adjList) {
    adjList[a].insert(b);
    adjList[b].insert(a);
}
int main() {
    /*
    Do a depth-first search in this graph:
    1--2--4
    | /
    |/
    3
    5--6--7
       |
       8
    */
    std::map<int, std::set<int>> adjList;
    std::map<int, bool> visited;
    addEdge(1, 2, adjList);
    addEdge(1, 3, adjList);
    addEdge(2, 3, adjList);
    addEdge(2, 4, adjList);
    addEdge(5, 6, adjList);
    addEdge(6, 7, adjList);
    addEdge(6, 8, adjList);
    // Set all nodes as unvisited at first
    for (int i = 1; i <= 8; i++) visited[i] = false;
    // Perform a dfs from the node `1`
    dfs(1, adjList, visited);
    // Print all the visited nodes:
    for (int i = 1; i <= 8; i++) {
        if (visited[i]) {
            std::cout << i << " ";
        }
    }
    return 0;
}
  

Java


// Java program to print DFS traversal from a given Graph
// Part of Cosmos by OpenGenus Foundation
import java.io.*;
import java.util.*;
// This class represents a directed Dfs using adjacency list representation
class Dfs {
    private int V;   // No. of vertices
    // Array  of lists for Adjacency List Representation
    private LinkedList<Integer> adj[];
    // Constructor of the class
    Dfs(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList();
        }
    }
    //Function to add an edge into the Graph
    void addEdge(int v, int w) {
        adj[v].add(w);  // Add w to v's list.
    }
    // A function used by DFS
    void DFSUtil(int v,boolean visited[]) {
        // Mark the current node as visited and print it
        visited[v] = true;
        System.out.print( v + " ");
        // Recur for all the vertices adjacent to this vertex
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if ( !visited[n] ) {
                DFSUtil(n, visited);
            }
        }
    }
    // The function to do DFS traversal. It uses recursive DFSUtil()
    void DFS(int v) {
        // Mark all the vertices as not visited(set as false by default in java)
        boolean visited[] = new boolean[V];
        // Call the recursive helper function to print DFS traversal
        DFSUtil(v, visited);
    }
    public static void main(String args[]) {
        Dfs g = new Dfs(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        System.out.println("Following is Depth First Traversal "+ "(starting from vertex 2)");
        g.DFS(2);
        System.out.println();
    }
}
  

Kotlin


// Part of Cosmos by OpenGenus Foundation
import java.util.LinkedList
class Dfs(private val vertices: Int) {
    // Array of lists for Adjacency List Representation
    private val adj: List<LinkedList<Int>> = (0 until vertices).map { LinkedList<Int>() }
    // Function to add an edge into the Graph
    fun addEdge(vertex: Int, weight: Int) {
        adj[vertex].add(weight)  // Add weight to vertex's list.
    }
    // A function used by DFS
    private fun dfsUtil(vertex: Int, visited: BooleanArray) {
        // Mark the current node as visited and print it
        visited[vertex] = true
        print("$vertex ")
        // Recur for all the vertices adjacent to this vertex
        adj[vertex].filter { !visited[it] }.forEach { dfsUtil(it, visited) }
    }
    // The function to do DFS traversal. It uses recursive DfsUtil()
    fun traverse(startVertex: Int) {
        // Call the recursive helper function to print DFS traversal
        dfsUtil(startVertex, BooleanArray(vertices))
    }
}
fun main(args: Array<String>) {
    val graph = Dfs(4)
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    graph.addEdge(3, 3)
    println("Following is Depth First Traversal " + "(starting from vertex 2)")
    graph.traverse(2)
    println()
}
  

Python


""" Part of Cosmos by OpenGenus Foundation"""
import collections
class Graph:
    def __init__(self):
        self.adjList = collections.defaultdict(set)
    def addEdge(self, node1, node2):
        self.adjList[node1].add(node2)
        self.adjList[node2].add(node1)
def dfsHelper(current, graph, visited, visitFunc):
    if (visited[current]):
        return 
    visited[current] = True;
    visitFunc(current)
    for neighbor in graph.adjList[current]:
        dfsHelper(neighbor, graph, visited, visitFunc)
def dfs(current, graph, visitFunc):
    visited = collections.defaultdict(bool)
    dfsHelper(current, graph, visited, visitFunc)
def visitPrint(i):
    print(i)
# Testing the depth first search implementation
if __name__ == "__main__":
    # Testing on this tree
    #      1
    #     / \
    #    /   \
    #   2     3
    #  / \   / \
    # 4   5 6   7  
    g = Graph()
    g.addEdge(1, 2)
    g.addEdge(1, 3)
    g.addEdge(2, 4)
    g.addEdge(2, 5)
    g.addEdge(3, 6)
    g.addEdge(3, 7)
    print("Test 1:")
    dfs(1, g, visitPrint)  
    print("\nTest2:")
    dfs(2, g, visitPrint)
    """Output:
    Test 1:
    1
    2
    4
    5
    3
    6
    7
    Test2:
    2
    1
    3
    6
    7
    4
    5
    """
  

Go


package main
import "fmt"
// Part of Cosmos by OpenGenus Foundation
/**************************************
 * Structures
 **************************************/
// Define set structure (golang has no built-in set)
// Usage:
//
//    s := make(set)                // Create empty set
//    s := set{7: true, 21: true}   // Create set with values
//    _, exist := s[7]              // Check if 7 is in the set
//    s[2] = true                   // Add 2 to the set
//    delete(s, 7)                  // Remove 7 from the set
type set map[int]bool
// Define Graph structure
type Graph struct {
  adjList map[int]set
}
// Create a graph and initialize its adjacency list,
// and return a pointer to it.
func createGraph() *Graph {
  var g = Graph{}
  g.adjList = make(map[int]set)
  return &g
}
// Add an edge between the two given nodes.
// If a node does not exist in the graph yet, add it.
func (g *Graph) addEdge(node1 int, node2 int) {
  // Check if node1 is already in the graph
  if g.adjList[node1] == nil {
    // Nope. Add it
    g.adjList[node1] = make(set)
  }
  g.adjList[node1][node2] = true
  // Check if node2 is already in the graph
  if g.adjList[node2] == nil {
    // Nope. Add it
    g.adjList[node2] = make(set)
  }
  g.adjList[node2][node1] = true
}
/**************************************
 * Algorithm
 **************************************/
// Perform a depth first search from the given node
// and apply the given function to each node.
func dfs(g *Graph, current int, visited set, visitFunction func(int)) {
  if _, seen := visited[current]; seen {
    return
  }
  visited[current] = true
  visitFunction(current)
  for neighbour := range g.adjList[current] {
    dfs(g, neighbour, visited, visitFunction)
  }
}
/**************************************
 * Tests
 **************************************/
// Test the dfs algorithm on this graph:
//
//      1
//     / \
//    /   \
//   2     5
//  / \   / \
// 3 - 4 6   7
//
// Should output: 1 2 3 4 5 6 7, OR SIMILAR (example: 1 2 4 3 5 7 6)
//
// NOTE: the output order may vary because we used a for range loop,
//       and according to the spec (https://golang.org/ref/spec#For_statements):
//       "The iteration order over maps is not specified and is not guaranteed
//       to be the same from one iteration to the next."
//
//          => Output may vary but will always be right from algorithmic POV.
func main() {
  graph := createGraph()
  graph.addEdge(1, 2)
  graph.addEdge(2, 3)
  graph.addEdge(2, 4)
  graph.addEdge(3, 4)
  graph.addEdge(1, 5)
  graph.addEdge(5, 6)
  graph.addEdge(5, 7)
  visited := make(set)
  dfs(graph, 1, visited, func(node int) {
    fmt.Print(node, " ")
  })
}
  

Ruby


#   This class represents a node in a graph.
#   It has a NAME and an ID and each node knows which nodes it is connected to.
class GraphNode
  require 'set'
  @@id = 0
  attr_reader :name, :id, :connections
  def initialize(name)
    @name = name
    @id = (@@id += 1)
    @connections = Set.new
  end
  def connect(node)
    return false unless node.is_a? GraphNode
    @connections << node
  end
  def equal?(other)
    return false unless other.is_a? GraphNode
    @name == other.name && @id == other.id
  end
  def to_s
    "<GraphNode:#{name}>"
  end
  def to_str
    to_s
  end
end
#   A simple function as a default function performed for each node in dfs()
def goalNode?(node)
  node.name == 'Goal'
end
#   Given a start node and a function or code block this performs a depth first search and will exit upon function or code block returning true, or returns :goal_node_not_found when it has visited the whole graph.
#
#   visited is a set containing all nodes that has been checked.
#   frontier is a queue were new nodes are prepended in reverse order, making this a depth first search.
def dfs(start, goal = :goalNode?)
  require 'set'
  visited = Set.new
  frontier = []
  frontier << start
  until frontier.empty?
    current = frontier.shift
    next if visited.include? current
    visited << current
    found = false
    found = if block_given?
              yield(current)
            else
              send(goal, current)
            end
    if !found
      current.connections.reverse_each do |node|
        frontier.unshift node
      end
    else
      return current
    end
  end
  :goal_node_not_found
end
#   A small test that will use dfs() for root node First, then for the Second node.
#   The dfs accepts a code block, and here we just print each visited node and will never find the goal-node.
#
#   The tests output:
#   Building Graph for tests...
#   Testing from root node 'First'
#     <GraphNode:First>
#     <GraphNode:Second>
#     <GraphNode:Fourth>
#     <GraphNode:Fifth>
#     <GraphNode:Third>
#     <GraphNode:Goal>
#     <GraphNode:Sixth>
#   goal_node_not_found
#   Testing from second node 'Second'
#     <GraphNode:Second>
#     <GraphNode:First>
#     <GraphNode:Third>
#     <GraphNode:Goal>
#     <GraphNode:Sixth>
#     <GraphNode:Fourth>
#     <GraphNode:Fifth>
#   goal_node_not_found
def test
  puts 'Building Graph for tests...'
  #         Simple graph
  #
  #            First
  #           /     \
  #       second    third
  #      /     |    |    \
  #   fourth fifth  goal sixth
  #
  # Construct graph
  first = GraphNode.new 'First'
  second = GraphNode.new 'Second'
  third = GraphNode.new 'Third'
  fourth = GraphNode.new 'Fourth'
  fifth = GraphNode.new 'Fifth'
  sixth = GraphNode.new 'Sixth'
  goal = GraphNode.new 'Goal'
  first.connect second
  first.connect third
  second.connect first
  second.connect fourth
  second.connect fifth
  third.connect first
  third.connect goal
  third.connect sixth
  fourth.connect second
  fifth.connect second
  goal.connect third
  sixth.connect third
  # Perform tests
  puts "Testing from root node 'First'"
  puts(dfs(first) { |node| puts '  ' + node })
  puts "Testing from second node 'Second'"
  puts(dfs(second) { |node| puts '  ' + node })
end
test if $PROGRAM_NAME == __FILE__
  

Applications


  • Finding connected components and strongly connected components
  • Topological sorting.
  • Finding 2-(edge or vertex)-connected components.
  • Finding 3-(edge or vertex)-connected components.
  • Finding the bridges of a graph.
  • Generating words in order to plot the Limit Set of a Group.
  • Planarity testing
  • Solving puzzles with only one solution, such as mazes.
  • Maze generation may use a randomized depth-first search.
  • Finding biconnectivity in graphs.