Depth First Search (commonly called as DFS) was first studied in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes. It is one of the most commonly preferred algorithms used for traversing or search in tree or graph data structures by using the idea of backtracking. DFS is also known as Depth First Traversal in case we are using the algorithm in tree data structures (Note: A tree is a special kind of graph with no cycles). The algorithm starts at a node of a graph and goes as far as possible in a given path, then backtracks until it finds an unexplored path, and then explores the rest of it. The process is repeatedly followed until all the nodes in the graph are explored.
Table of content
Most of the concepts in computer science can be visualized and represented in terms of graph data structure. DFS is one such useful algorithm for analysing these problems easily.
boolean[] visited = new boolean[total_nodes_in_graph]
//Default value will be false for all the elements
visited[S] = True
visited[A]
is True go to step 5, else go to step 7.visited[A] = True
.Note:
Consider the following graph structure where S is the Source node to begin DFS with:
The goal here is to find whether the node E is present in the graph. Just by seeing the graph, we can say that node E is not present. Lets see how DFS works to identify this.
Step 1: We push S to the STACK
Step 2: Mark S as Visited.
Step 3: While the stack is not empty, repeat the below steps:
STACK = [ ]
S != E
. Hence, continue with the below steps.STACK = [C, B, A]
Pop the top element i.e., node A out of STACK.
Here A != E
. Hence, we proceed with the below steps.Mark A as visited. Stack now becomes STACK = [C, B]
Push all the adjacent nodes of A which are not visited yet into STACK.
STACK = [C, B, D]
Pop the top element i.e., node D out of STACK. Mark D as visited. After popping D, stack is now: STACK = [C, B]
Here A != E
. Hence, we proceed with the below steps. Push all the adjacent nodes of D which are not visited yet into STACK.
STACK = [C, B, C, B]
Pop the top element i.e., node B out of STACK.
Here B != E
. Hence proceed with the below steps.Mark B as visited. STACK = [C, B, C]
Push all the adjacent nodes of B which are not visited yet into STACK.
STACK = [C, B, C]
Pop the top element i.e., node C out of STACK.
Here C != E
. Hence proceed with the below steps.Mark C as visited. Stack becomes STACK = [C, B]
Push all the adjacent nodes of C which are not visited yet into STACK.
STACK = [C, B]
Now, we pop B from STACK and see that it was visited earlier. After popping B, stack is STACK = [C]
STACK = [ ]
This is how a depth-first search works, by traversing the nodes depth-wise. We stop DFS and return true
when we find the required node (key). We return false
when we have not found the key despite of exploring all the nodes.
/**
* Pseudo code for recursive DFS
* @Parameters: adjacent list G, source node,
* visited array, key (node to be searched)
*/
DFS(adjacent[][], source, visited[], key) {
if(source == key) return true //We found the key
visited[source] = True
FOR node in adjacent[source]:
IF visited[node] == False:
DFS(adjacent, node, visited)
END IF
END FOR
return false // If it reaches here, then all nodes have been explored
//and we still havent found the key.
}
/**
* Pseudo code for iterative DFS
* @Parameters: Graph G, source node s, key
*/
DFS(G, s, key):
stack = new Stack()
stack.push( s ) //Push s to stack
mark s as visited
while ( stack is not empty):
//Pop node from stack and start to visit its children
v = stack.pop()
if(v == key) return true //We found the key
//Push all the unvisited neighbours of v to stack
for all neighbours w of v in Graph G:
//unvisited neighbors
if w is not visited :
stack.push( w )
mark w as visited
return false // If it reaches here, then all nodes have been explored
//and we still havent found the key.
Implementation of Depth-first Search in C:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int vertex;
struct node* next;
};
struct node* createNode(int v);
struct Graph
{
int numVertices;
int* visited;
struct node** adjLists; // we need int** to store a two dimensional array. Similarly, we need struct node** to store an array of Linked lists
};
struct Graph* createGraph(int);
void addEdge(struct Graph*, int, int);
void printGraph(struct Graph*);
void DFS(struct Graph*, int);
int main()
{
struct Graph* graph = createGraph(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
printGraph(graph);
DFS(graph, 2);
return 0;
}
void DFS(struct Graph* graph, int vertex) {
struct node* ptr = graph->adjLists[vertex];
graph->visited[vertex] = 1;
printf("Visited %d \n", vertex);
while(ptr!=NULL) {
int adj_vertex = ptr->vertex;
if(graph->visited[adj_vertex] == 0) {
DFS(graph, adj_vertex);
}
ptr = ptr->next;
}
}
struct node* createNode(int v)
{
struct node* new_node = malloc(sizeof(struct node));
new_node->vertex = v;
new_node->next = NULL;
return new_node;
}
struct Graph* createGraph(int vertices)
{
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
void addEdge(struct Graph* graph, int source, int destination)
{
// Add edge from src to dest
struct node* newNode = createNode(destination);
newNode->next = graph->adjLists[source];
graph->adjLists[source] = newNode;
// Add edge from destination to source
newNode = createNode(source);
newNode->next = graph->adjLists[destination];
graph->adjLists[destination] = newNode;
}
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->numVertices; v++)
{
struct node* ptr = graph->adjLists[v];
printf("\n Adjacency list of vertex %d\n ", v);
while (ptr)
{
printf("%d -> ", ptr->vertex);
ptr = ptr->next;
}
printf("\n");
}
}
Implementation of Depth-first Search in C++:
#include <iostream>
#include <vector>
void dfs(int u, vector<vector<int> > &adj, vector<bool> &visited) {
visited[u] = true;
for(int v : adj[u])
if(!visited[v])
dfs(v, adj, visited);
cout << “Done visiting node: “ << u + 1 << endl;
}
int main() {
int nodes, edges, u, v;
cin >> nodes >> edges;
vector<vector<int> > adj(nodes);
vector<bool> visited(nodes);
for(int i = 1; i <= edges; ++i) {
cin >> u >> v;
--u, --v; //there is an undirected edge between u and v (0 based)
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0, adj, visited); //assume root is always node 0
return 0;
}
Implementation of DFS in Java:
import java.io.*;
import java.util.*;
class Graph
{
private int numVertices;
private LinkedList<Integer> adjLists[];
private boolean visited[];
Graph(int vertices)
{
numVertices = vertices;
adjLists = new LinkedList[vertices];
visited = new boolean[vertices];
for (int i = 0; i < vertices; i++)
adjLists[i] = new LinkedList<Integer>();
}
void addEdge(int source, int destination)
{
adjLists[source].add(destination);
}
void DFS(int vertex)
{
visited[vertex] = true;
System.out.print(vertex + " ");
Iterator itr = adjLists[vertex].listIterator();
while (itr.hasNext())
{
int adj_node = itr.next();
if (!visited[adj_node])
DFS(adj_node);
}
}
public static void main(String args[])
{
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
System.out.println("Following is Depth First Traversal");
g.DFS(2);
}
}
Implementation of DFS in python:
def dfs(graph, vertex, visited=None):
if visited is None:
visited = set()
visited.add(vertex)
print(vertex)
for node in graph[vertex] :
if node not in visited:
dfs(graph, node, visited)
graph = {'0': set(['1', '2']),
'1': set(['0', '3', '4']),
'2': set(['0', ‘4’]),
'3': set(['1', ‘4’]),
'4': set([‘1’, '2', '3'])}
dfs(graph, '0')
Why can we not implement DFS using Queues? Why do we prefer stacks instead of other data structures?
What are the classifications of edges in DFS of a graph?
1 2 4 3 5 6
. If DFS is applied on this graph, a tree is obtained which is represented and connected by means of using green edges. The types of edges are as follows: Edge (u, v)
such that v is descendant but not part of the DFS tree. Edge from node 1 to node 6 is a forward edge.Edge (u, v)
such that v
is ancestor of edge u but not part of DFS tree. Edge from node 4 to node 1 is a back edge.
Can DFS be used for finding shortest possible path?
Why can we not use DFS for finding shortest possible path?
Is DFS a complete algorithm?
Is DFS a optimal algorithm?
When is it best to use DFS?
Log In using