# Depth First Search

#### Graph Algorithms Search Algorithms 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.

### 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
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:

1. Initiate an empty stack for size of total number nodes, S.

2. For each vertex V, define V visited to be false.

3. Push the first node to be visited onto Stack S.

4. 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.

5. 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;
};
//main program
int main()
{
//input no of nodes: Num
int Num;
printf("Enter number of nodes\n");
scanf("%d",&Num);
for(int i=0;i<Num;i++)
{
for(int j=0;j<Num;j++)
{
}
}
//DFS traversing
//create a stack
struct node *Stack=NULL;
//create status array and set it to ready state
int status[Num];
for(int i=0;i<Num;i++)
{
}
push(&Stack,0);
status=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;
for(int i=0;i<Num;i++)
{
{
push(&Stack,i);
status[i]=waiting;
}
}
}
printf("\n");
}
//stack functions
{
struct node* temp;
return 1;
return 0;
}
{
return 1;
struct node* temp;
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, bool>& visited) {        // the 'visited' state for each node
if (visited[current]) return;
visited[current] = true;
for (auto neighbour : adjList[current]) {
}
}
}
int main() {
/*
Do a depth-first search in this graph:
1--2--4
| /
|/
3
5--6--7
|
8
*/
std::map<int, bool> visited;
// Set all nodes as unvisited at first
for (int i = 1; i <= 8; i++) visited[i] = false;
// Perform a dfs from the node 1
// 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
// Constructor of the class
Dfs(int v) {
V = v;
for (int i = 0; i < v; ++i) {
}
}
//Function to add an edge into the Graph
void addEdge(int v, int w) {
}
// 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
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);
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
class Dfs(private val vertices: Int) {
// Array of lists for Adjacency List Representation
// Function to add an edge into the Graph
fun addEdge(vertex: Int, weight: Int) {
}
// 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 // Check if 7 is in the set // s = 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. #### Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.