# Depth First Search

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.

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

## 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
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};

/*
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
*/
typedef struct node {
int data;
enum color colr;
}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->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
}

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
}
}
}

// 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++) {
return 1;
}
return 0;
}

void add_edge(graph *g, int source, int dest) {
//if source or edge is not in the graph, add it
}
}

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
}
else { // there is head which is pointer by the node in the head array
list_node *temp;

// 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;
while(temp != NULL) {
temp = temp->next;
}
printf("\n");
}
}

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

list_node *temp;
while(temp != NULL) {
}
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++) {
}

for(i=0; i<g->number_of_vertices; i++) {
}
}
}

int main() {
graph *g = new_graph(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

while(temp != None):
temp = temp.next
i.color = Color.Black
print(i.data)

def dfs(g):
for i in range(0, g.number_of_vertices):

for i in range(0, g.number_of_vertices):

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

dfs(g)

/*
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
*/
class Node {
public static enum Color {
White,
Black,
Gray
}

private int data;
private Color color;

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

public int getData() {
return data;
}

}

}

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;
/*
contain data
____            ____    ____    ____
|node|    ----> |list|->|    |->|    |
|____|          |node|  |____|  |____|
____            ____    ____    ____
|    |    ----> |    |->|    |->|    |
|____|          |____|  |____|  |____|
____            ____    ____    ____
|    |    ----> |    |->|    |->|    |
|____|          |____|  |____|  |____|
____            ____    ____    ____
|    |    ----> |    |->|    |->|    |
|____|          |____|  |____|  |____|

*/

public Graph(int noOfVertices) {
numberOfVertices = noOfVertices;

//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
}
}

}

public int getNumberOfVertices() {
return numberOfVertices;
}

// method to add new node to graph
// 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
}
}
}

// function to check of the data is in the head array of graph or not
for(int i=0; i<numberOfVertices; i++) {
return true;
}
return false;
}

public void addEdge(int source, int dest) {
//if source or edge is not in the graph, add it
}
}

// 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
}
else { // there is head which is pointer by the node in the head array
ListNode temp;

// 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;
while(temp != null) {
temp = temp.getNext();
}
System.out.println("");
}
}
}

class DFS {

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

ListNode temp;
while(temp != null) {
}
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++) {
}

for(int i=0; i<g.getNumberOfVertices(); i++) {
}
}
}

public static void main(String[] args) {
Graph g = new Graph(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