Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally print the nodes in the path.
Example :
Algorithm - Bubble sort
Algorithm : DFS(G)
//Implements a depth-first search traversal of a given graph
//Input : Graph G = (V,E)
//Output : Graph G with its vertices marked with consecutive integers in the order they have been first encountered by the DFS traversal
{
mark each vertex in V with 0 as a mark of being “unvisited”.
count ← 0
for each vertex v in V
do
if v is marked with 0 dfs(v)
}
Following are the implementation of DFS into programs
#include
void DFS(int a[20][20] , int u , int visited[20] , int n)
{
int v;
visited[u] = 1;
for(v=1; v<=n; v++)
{
if(a[u][v]==1 && visited[v]==0)
DFS(a,v,visited,n);
}
}
void main()
{
int n,a[20][20] , i , j , visited[20] , source;
clrscr();
printf("Enter the number of vertices: ");
scanf( "%d", &n );
printf("\nEnter the adjacency matrix\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d", &a[i][j]);
for(i=1; i<=n; i++)
visited[i] = 0;
printf("\nEnter the source node: ");
scanf( "%d" , &source);
DFS(a , source , visited , n);
for(i=1; i<=n; i++)
{
if(visited[i] == 0)
{
printf("\nGraph is not connected");
getch( );
exit(0);
}
}
printf("\nGraph is connected\n");
getch( );
}
Code
// Java program to print DFS
// mtraversal from a given given
// graph
import java.io.*;
import java.util.*;
// This class represents a
// directed graph using adjacency
// list representation
class Graph {
private int V; // No. of vertices
// Array of lists for
// Adjacency List Representation
private LinkedList adj[];
// Constructor
@SuppressWarnings("unchecked") Graph(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 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);
}
// Driver Code
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, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println(
"Following is Depth First Traversal "
+ "(starting from vertex 2)");
g.DFS(2);
}
}
Code
# Python3 program to print DFS traversal
# from a given given graph
from collections import defaultdict
# This class represents a directed graph using
# adjacency list representation
class Graph:
# Constructor
def __init__(self):
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)
# A function used by DFS
def DFSUtil(self, v, visited):
# Mark the current node as visited
# and print it
visited.add(v)
print(v, end=' ')
# Recur for all the vertices
# adjacent to this vertex
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour, visited)
# The function to do DFS traversal. It uses
# recursive DFSUtil()
def DFS(self, v):
# Create a set to store visited vertices
visited = set()
# Call the recursive helper function
# to print DFS traversal
self.DFSUtil(v, visited)
# Driver code
# Create a graph given
# in the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print("Following is DFS from (starting from vertex 2)")
g.DFS(2)
Code
Sample Output
Following is Depth First Traversal (starting from vertex 2)
2 0 1 3
Visualized
Note: For better Visualized Understanding visit our algorithm Visualizer