Prerequisites:
Before starting this tutorial, please complete below tutorials
1. Recursion
Example - How DFS (Depth First Search) traversal works :
Suppose someone needs to visit a set of cities connected via roads . He needs a plan so that he could easily visit all cities. Below is the diagram of city road network.
Suppose he defines an order to visit the cities in the given diagram using map as
LEFT->DOWN->RIGHT. Then below will be his tour:
1. He starts from city 1. Since no city in the left side so he goes down to city 3 then city 5. Once he visits cities he marks them visited. Below diagram highlights the same.
2. Once he reaches to city 5 no path exists to travel. So he returns back and mark city 5 as processed. While returning back to city 3 he finds another route which is right to city 3. So he again makes a move and visits city 6. Below diagram shows the visiting order.
3. On city 6 he doesn't find any path to visit, so he returns back by processing city 6. Then he reaches to city 3 where all paths has been visited so he returns back from city 3 by marking city 3 as processed. He reaches to city 1 where he finds another path to visit which goes right down to city 4 and onwards.
4. Same order is followed to visit cities where he reaches to city 7 and returns back from city 7 by making city 7 as processed then he gain return backs from city 4 by making city 4 as processed. Then he goes to city 1 where he finds a path right to city 1 and visits city 2 which is given below:
5. At last city 2 is processed then he goes to city 1 where no path is remaining to visit, so city 1 is also processed as given below:
The mechanism to visit all the cities in the above mentioned example is called depth first search(DFS) methodology where all possible path are visited recursively.
Definition:
As mentioned in the above example, Depth First Search(DFS) is an graph traversal algorithm where a node is only processed if all its adjacent vertices are recursively processed.
Recursively processed means once any adjacent vertex is selected for processing this adjacent vertex is supposed as source/parent vertex and the same process of DFS is applied on it where all its adjacent vertices are targeted to process.
This process is continued on till it reaches to the leaf node where no path or adjacent vertex exists. This leaf node is processed first and then traversal process backtracks to process remaining adjacent vertices of upper level parents. Once all adjacent vertices(all paths from adjacent vertices) of a parent vertex are processed that parent vertex is also processed.
In other words Depth First Search can be defined as below:
Depth First Search (DFS) is a fundamental algorithm used in graph theory for traversing or searching tree or graph data structures. The algorithm starts at a root node(or any selected node called source vertex) and explores as far as possible along each branch before backtracking. Here’s a detailed explanation:
How DFS Works
- Start at the root node (or an arbitrary node in the case of a graph called source node).
- Visit the node and mark it as visited.
-
Explore each adjacent node to the current node:
- If an adjacent node has not been visited, recursively apply DFS to that node.
- If an adjacent node has already been visited, continue to the next adjacent node.
- Backtrack when there are no more adjacent unvisited nodes. This vertex is called processed vertex.
Implementation
Below is the algorithm to apply DFS on Given graph G(V,E)|(V is set of vertices and E is set of edges of the graph) where DFS starts at node sourceNode.
DFS(G(V,E), sourceNode)
{
1. for all vertices v adjacent to sourceNode
2. if (v is unvisited)
3. {
4. set v is visited
5. DFS(G(V,E),v)
6. }
7. set sourceNode is processed
8. return
}
We are taking below example to implement it through java code where source vertex will be A.
Below is the java code implementation for the above mentioned DFS traversal algorithm
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.List;
public class DFSTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Hashtable<Character,List<Character>> graph=new Hashtable<Character, List<Character>>();
List<Character> children =new ArrayList<Character>();
children.add('B');
children.add('C');
graph.put('A', children);
children =new ArrayList<Character>();
children.add('A');
children.add('D');
children.add('E');
graph.put('B', children);
children =new ArrayList<Character>();
children.add('A');
children.add('F');
graph.put('C', children);
children =new ArrayList<Character>();
children.add('B');
graph.put('D', children);
children =new ArrayList<Character>();
children.add('B');
children.add('F');
graph.put('E', children);
children =new ArrayList<Character>();
children.add('C');
children.add('E');
graph.put('F', children);
DFS dfs=new DFS(graph);
dfs.applyDFS('A');
}
}
class DFS
{
Hashtable<Character,List<Character>> graph;
HashSet<Character> visitedNodes;
public DFS(Hashtable<Character,List<Character>> g)
{
graph=g;
visitedNodes=new HashSet<Character>();
}
public void applyDFS(char source)
{
if(!visitedNodes.contains(source))
{
visitedNodes.add(source);
}
for(char v:graph.get(source))
{
if(!visitedNodes.contains(v))
{
visitedNodes.add(v);
applyDFS(v);
}
}
System.out.println("Processed Node="+source);
}
}
Properties of DFS
- Time Complexity: , where is the number of vertices and is the number of edges.
- Space Complexity: due to the recursion stack or the explicit stack used.
-
Applications:
- Finding connected components in a graph.
- Topological sorting.
- Pathfinding and maze solving.
- Detecting cycles in a graph.
- Solving puzzles with a single solution (like a maze).
DFS is particularly useful for problems that require exploring all possible paths in a structure, such as finding all possible solutions to a problem or searching through all nodes in a network.