Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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.
Algorithm
The strategy which DFS uses is to explore all nodes of graph whenever possible. DFS investigates edges that come out of the most recently discovered vertex. Only those paths going to unexplored vertices will be explored using stacks.
It randomly start from a node in the graph and using stack it trace all the possible nodes. When all of the’s edges are explored, the search returns(backtracks) until it reaches a node which has an unexplored neighbor.
Pseudocode for 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.
Steps:
-
Initiate an empty stack for size of total number nodes, S.
-
For each vertex V, define V visited to be false.
-
Push the first node to be visited onto Stack S.
-
While S is not empty:
Pop the first element in S, V.
If V.visited = false, then:
V.visited = true
for each unvisited neighbor w of V:
Push w into S. -
End process when all nodes have been visited.
Note: we do not need an explicit stack as we can use the existing system stack
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.
