Depth First Search (DFS) in a Graph

Depth-first search or DFS is also a searching technique like BFS. As its name suggests, it first explores the depth of the graph before the breadth i.e., it traverses along the increasing depth and upon reaching the end, it backtracks to the node from which it was started and then do the same with the sibling node.

backtracking in dfs

Similar to the BFS, we also mark the vertices white, gray and black to represent unvisited, discovered and complete respectively.

full steps in dfs

animation of dfs

Code for DFS

Similar to the BFS, we start by making all the nodes white.

DFS(G)
for i in G.V
i.color = white

Now we need to explore each of these vertices deeper. So, we will iterate again and call a function which will visit deeper for each node.

for i in G.V
if i.color == white
DFS-VISIT(G, i)

The DFS-VISIT will traverse over each of the nodes deeply. Now for each of the nodes passed to this function, the adjacent nodes are one level deeper. So, we will again iterate over the adjacent nodes and call DFS-VISIT function again on them.

DFS-VISIT(G, i)
  i.color = gray // we just discovered this vertex
  for v in G.Adj[u]
    if v.color == white
      DFS-VISIT(G, v)
  u.color = black

DFS(G)
  for i in G.V
    i.color = white

  for i in G.V
    if i.color == white
      DFS-VISIT(G, i)

DFS-VISIT(G, i)
  i.color = gray
  for v in G.Adj[i]
    if v.color == white
      DFS-VISIT(G, v)
  i.color = black

C
Python
Java

#include <stdio.h>
#include <stdlib.h>
enum color{White, Gray, Black};

/*
  Node for linked list of adjacent elements.
  This will contain a pointer for next node.
  It will not contain the real element but the index of
  element of the array containing all the vertices V.
*/
typedef struct list_node {
  int index_of_item;
  struct list_node *next;
}list_node;

/*
  Node to store the real element.
  Contain data and pointer to the
  first element (head) of the adjacency list.
*/
typedef struct node {
  int data;
  enum color colr;
  list_node *head;
}node;

/*
  Graph will contain number of vertices and
  an array containing all the nodes (V).
*/
typedef struct graph{
  int number_of_vertices;
  node heads[]; // array of nodes to store the list of first nodes of each adjacency list
}graph;

node* new_node(int data) {
  node *z;
  z = malloc(sizeof(node));
  z->data = data;
  z->head = NULL;
  z->colr = White;

  return z;
}

list_node* new_list_node(int item_index) {
  list_node *z;
  z = malloc(sizeof(list_node));
  z->index_of_item = item_index;
  z->next = NULL;

  return z;
}

// make a new graph
graph* new_graph(int number_of_vertices) {
  //number_of_vertices*sizeof(node) is the size of the array heads
  graph *g = malloc(sizeof(graph) + (number_of_vertices*sizeof(node)));
  g->number_of_vertices = number_of_vertices;

  //making elements of all head null i.e.,
  //their data -1 and next null
  int i;
  for(i=0; i<number_of_vertices; i++) {
    node *z = new_node(-1); //*z is pointer of node. z stores address of node
    g->heads[i] = *z; //*z is the value at the address z
  }

  return g;
}

// function to add new node to graph
void add_node_to_graph(graph *g, int data) {
  // creating a new node;
  node *z = new_node(data);
  //this node will be added into the heads array of the graph g
  int i;
  for(i=0; i<g->number_of_vertices; i++) {
    // we will add node when the data in the node is -1
    if (g->heads[i].data < 0) {
      g->heads[i] = *z; //*z is the value at the address z
      break; //node is added
    }
  }
}

// function to check of the node is in the head array of graph or not
int in_graph_head_list(graph *g, int data) {
  int i;
  for(i=0; i<g->number_of_vertices; i++) {
    if(g->heads[i].data == data)
      return 1;
  }
  return 0;
}

// function to add edge
void add_edge(graph *g, int source, int dest) {
  //if source or edge is not in the graph, add it
  if(!in_graph_head_list(g, source)) {
    add_node_to_graph(g, source);
  }
  if(!in_graph_head_list(g, dest)) {
    add_node_to_graph(g, dest);
  }

  int i,j;
  // iterating over heads array to find the source node
  for(i=0; i<g->number_of_vertices; i++) {
    if(g->heads[i].data == source) { //source node found

      int dest_index; //index of destination element in array heads
      // iterating over heads array to find node containg destination element
      for(j=0; j<g->number_of_vertices; j++) {
        if(g->heads[j].data == dest) { //destination found
          dest_index = j;
          break;
        }
      }

      list_node *n = new_list_node(dest_index); // new adjacency list node with destination index
      if (g->heads[i].head == NULL) { // no head, first element in adjaceny list
        g->heads[i].head = n;
      }
      else { // there is head which is pointer by the node in the head array
        list_node *temp;
        temp = g->heads[i].head;

        // iterating over adjaceny list to insert new list_node at last
        while(temp->next != NULL) {
          temp = temp->next;
        }
        temp->next = n;
      }
      break;
    }
  }
}

void print_graph(graph *g) {
  int i;
  for(i=0; i<g->number_of_vertices; i++) {
    list_node *temp;
    temp = g->heads[i].head;
    printf("%d\t",g->heads[i].data);
    while(temp != NULL) {
      printf("%d\t",g->heads[temp->index_of_item].data);
      temp = temp->next;
    }
    printf("\n");
  }
}

void dfs_visit(graph *g, node *i) {
  i->colr = Gray;

  list_node *temp;
  temp = i->head;
  while(temp != NULL) {
    if (g->heads[temp->index_of_item].colr == White) {
      dfs_visit(g, &g->heads[temp->index_of_item]);
    }
    temp = temp->next;
  }
  i->colr = Black;
  printf("%d\n",i->data);
}

void dfs(graph *g) {
  int i;
  for(i=0; i<g->number_of_vertices; i++) {
    g->heads[i].colr = White;
  }

  for(i=0; i<g->number_of_vertices; i++) {
    if (g->heads[i].colr == White) {
      dfs_visit(g, &g->heads[i]);
    }
  }
}

int main() {
  graph *g = new_graph(7);
  add_edge(g, 1, 2);
  add_edge(g, 1, 5);
  add_edge(g, 1, 3);
  add_edge(g, 2, 6);
  add_edge(g, 2, 4);
  add_edge(g, 5, 4);
  add_edge(g, 3, 4);
  add_edge(g, 3, 7);
  dfs(g);
  return 0;
}

from graph_directed import Graph #importing graph from previous chapter but directed version
from graph_directed import Node #see code of previous chapter
from graph_directed import Color

def dfs_visit(g, i):
    i.color = Color.Gray

    temp = i.head
    while(temp != None):
        if(g.heads[temp.index_of_item].color == Color.White):
            dfs_visit(g, g.heads[temp.index_of_item])
        temp = temp.next
    i.color = Color.Black
    print(i.data)

def dfs(g):
    for i in range(0, g.number_of_vertices):
        g.heads[i].color = Color.White

    for i in range(0, g.number_of_vertices):
        if(g.heads[i].color == Color.White):
            dfs_visit(g, g.heads[i])

if __name__ == '__main__':
    g = Graph(7)

    g.add_edge(1, 2)
    g.add_edge(1, 5)
    g.add_edge(1, 3)
    g.add_edge(2, 6)
    g.add_edge(2, 4)
    g.add_edge(5, 4)
    g.add_edge(3, 4)
    g.add_edge(3, 7)

    dfs(g)

/*
  Node for linked list of adjacent elements.
  This will contain a pointer for next node.
  It will not contain the real element but the index of
  element of the array containing all the vertices V.
*/
class ListNode {
  private int indexOfItem;
  private ListNode next;

  public ListNode(int itemIndex) {
    indexOfItem = itemIndex;
    next = null;
  }

  public ListNode getNext() {
    return next;
  }

  public void setNext(ListNode n) {
    next = n;
  }

  public int getIndexOfItem() {
    return indexOfItem;
  }
}

/*
  Node to store the real element.
  Contain data and pointer to the
  first element (head) of the adjacency list.
*/
class Node {
  public static enum Color {
    White,
    Black,
    Gray
  }

  private int data;
  private Color color;
  private ListNode head;

  public Node(int d) {
    data = d;
    head = null;
    color = Color.White;
  }

  public int getData() {
    return data;
  }

  public ListNode getHead() {
    return head;
  }

  public void setHead(ListNode n) {
    head = n;
  }

  public Color getColor() {
    return color;
  }

  public void setColor(Color c) {
    color = c;
  }
}

/*
  Graph will contain number of vertices and
  an array containing all the nodes (V).
*/
class Graph {
  private int numberOfVertices;
  private Node[] heads;
  /*
  array heads      Adjacency list. contain index and next
  contain data
  and head of
  adjacency list
   ____            ____    ____    ____
  |node|    ----> |list|->|    |->|    |
  |____|          |node|  |____|  |____|
   ____            ____    ____    ____
  |    |    ----> |    |->|    |->|    |
  |____|          |____|  |____|  |____|
   ____            ____    ____    ____
  |    |    ----> |    |->|    |->|    |
  |____|          |____|  |____|  |____|
   ____            ____    ____    ____
  |    |    ----> |    |->|    |->|    |
  |____|          |____|  |____|  |____|

  */

  public Graph(int noOfVertices) {
    numberOfVertices = noOfVertices;
    heads = new Node[numberOfVertices];

    //making elements of all head null i.e.,
    //their data -1 and next null
    for(int i=0; i<numberOfVertices; i++) {
      Node z = new Node(-1); //*z is pointer of node. z stores address of node
      heads[i] = z; //*z is the value at the address z
    }
  }

  public Node[] getHeads() {
    return heads;
  }

  public int getNumberOfVertices() {
    return numberOfVertices;
  }

  // method to add new node to graph
  public void addNodeToGraph(int data) {
    // creating a new node;
    Node z = new Node(data);
    //this node will be added into the heads array of the graph g
    for(int i=0; i<numberOfVertices; i++) {
      // we will add node when the data in the node is -1
      if(heads[i].getData() < 0) {
        heads[i] = z; //*z is the value at the address z
        break; //node is added
      }
    }
  }

  // function to check of the data is in the head array of graph or not
  public boolean inGraphHeadList(int data) {
    for(int i=0; i<numberOfVertices; i++) {
      if(heads[i].getData() == data)
        return true;
      }
      return false;
  }

  // function to add edge
  public void addEdge(int source, int dest) {
    //if source or edge is not in the graph, add it
    if(!inGraphHeadList(source)) {
      addNodeToGraph(source);
    }
    if(!inGraphHeadList(dest)) {
      addNodeToGraph(dest);
    }

    // iterating over heads array to find the source node
    for(int i=0; i<numberOfVertices; i++) {
      if(heads[i].getData() == source) { //source node found

        int destIndex=0; //index of destination element in array heads

        // iterating over heads array to find node containg destination element
        for(int j=0; j<numberOfVertices; j++) {
          if(heads[j].getData() == dest) { //destination found
            destIndex = j;
            break;
          }
        }

        ListNode n = new ListNode(destIndex); // new adjacency list node with destination index
        if(heads[i].getHead() == null) { // no head, first element in adjaceny list
          heads[i].setHead(n);
        }
        else { // there is head which is pointer by the node in the head array
          ListNode temp;
          temp = heads[i].getHead();

          // iterating over adjaceny list to insert new list_node at last
          while(temp.getNext() != null) {
            temp = temp.getNext();
          }
          temp.setNext(n);
        }
        break;
      }
    }
  }

  public void printGraph() {
    for(int i=0; i<numberOfVertices; i++) {
      ListNode temp;
      temp = heads[i].getHead();
      System.out.print(heads[i].getData()+"\t");
      while(temp != null) {
        System.out.print(heads[temp.getIndexOfItem()].getData()+"\t");
        temp = temp.getNext();
      }
      System.out.println("");
    }
  }
}

class DFS {

  public static void dfsVisit(Graph g, Node i) {
    i.setColor(Node.Color.Gray);

    ListNode temp;
    temp = i.getHead();
    while(temp != null) {
      if(g.getHeads()[temp.getIndexOfItem()].getColor() == Node.Color.White) {
        dfsVisit(g, g.getHeads()[temp.getIndexOfItem()]);
      }
      temp = temp.getNext();
    }
    i.setColor(Node.Color.Black);
    System.out.println(i.getData());
  }

  public static void dfs(Graph g) {
    for(int i=0; i<g.getNumberOfVertices(); i++) {
      g.getHeads()[i].setColor(Node.Color.White);
    }

    for(int i=0; i<g.getNumberOfVertices(); i++) {
      if(g.getHeads()[i].getColor() == Node.Color.White) {
        dfsVisit(g, g.getHeads()[i]);
      }
    }
  }

  public static void main(String[] args) {
    Graph g = new Graph(7);

    g.addEdge(1, 2);
    g.addEdge(1, 5);
    g.addEdge(1, 3);
    g.addEdge(2, 6);
    g.addEdge(2, 4);
    g.addEdge(5, 4);
    g.addEdge(3, 4);
    g.addEdge(3, 7);

    dfs(g);
  }
}

As BFS uses a queue, the DFS is using a stack for its implementation. The recursive calls of the DFS-VISIT are stored in a stack.

Analysis of DFS

Both loops in the DFS function is running in $O(|V|)$ time. In DFS-VISIT, the loop is executed once for each edge in the adjacency list. Also DFS-VISIT is only called if the vertex is white, so the loop will be executed only once for each vertex i.e., $O(|E|)$. Thus, the total time taken will be $O(|E|+|V|)$.

Graph is a vast topic and we have just went through an introduction with these chapters. But you can now learn any other algorithm related to graphs easily whenever you need them because you have gone through all the basics. We will also keep including new articles on BlogsDope to cover more and more topics. Even you can share your knowledge by contributing articles to BlogsDope.

For infrastructure technology, C will be hard to displace.

- Dennis Ritchie