1. Introduction
In this tutorial, we will explore another graph traversal technique: Depth First Search (DFS). This algorithm is designed to visit each vertex exactly once.
Consider a graph with vertices A, B, C, D, E, and F, connected by multiple directed edges. DFS navigates through the graph by exploring as far as possible along each branch before backtracking to visit other vertices. Depth First Search (DFS) originated as a strategy for solving mazes, first investigated in the 19th century.
There is a G(V,E) graph and the aim is to visit every V vertex exactly once. Depth-first search explores as far as possible along each branch before backtracking and visiting other branches. The runtime complexity of Depth First Search (DFS) is O(V+E). The run time complexity is same as Breadth-First search. The memory complexity of Depth-first search is way better than that of Breadth-First search. That is why usually Depth-first search is preferred.
2. Pseudocode
To implement Depth-first search, stack abstract data type is used. Following is the pseudocode using iterative method:
DFS(graph, start):
Initialize an empty stack (stack)
Push the start vertex onto the stack
While the stack is not empty:
Pop the top vertex from the stack (current)
If current is not in visited:
Mark current as visited
Process current (e.g., print or store it)
For each neighbor of current in graph:
If neighbor is not in visited:
Push neighbor onto the stackDepth First Search (DFS) can be implemented in various ways. In some implementations, we first check if a vertex has been visited before considering its neighbors. In others, we explore all the neighbors first and check whether each one has already been visited during traversal. Since the stack is used, we can solve this problem with recursion.
3. Depth first search visualization
The Depth-first search algorithm process can be visualized with the help of following figures:
4. Implementation
In this implementation, we have three classes, Vertex, DepthFirstSearch and App. The Vertex class represents the node of the graph. DepthFirstSearch is the implementation of the depth-first search algorithm. App is the class to test the algorithm.
Vertex.java
import java.util.ArrayList;
import java.util.List;
public class Vertex {
private String name;
private boolean visited;
private List<Vertex> adjacencyList;
public Vertex(String name) {
this.name = name;
this.adjacencyList = new ArrayList<>();
}
@Override
public String toString(){
return name;
}
public void addNeighbor(Vertex v){
adjacencyList.add(v);
}
public List<Vertex> getNeighbors(){
return adjacencyList;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
}
DepthFirstSearch.java
import java.util.Stack;
import java.util.List;
public class DepthFirstSearch {
private Stack<Vertex> stack;
public DepthFirstSearch(){
this.stack = new Stack<>();
}
public void dfs(List<Vertex> vertexList){
for(Vertex v : vertexList) {
if(!v.isVisited()){
v.setVisited(true);
dfsHelper(v);
}
}
}
private void dfsHelper(Vertex v) {
stack.add(v);
v.setVisited(true);
while(!stack.isEmpty()){
Vertex actualVertex = stack.pop();
System.out.println(actualVertex);
//consider all the neighbors
for(Vertex vertex: actualVertex.getNeighbors()){
if(!vertex.isVisited()){
vertex.setVisited(true);
stack.add(vertex);
}
}
}
}
}
App.java
import java.util.List;
import java.util.ArrayList;
public class App {
public static void main(String args[]){
Vertex v1 = new Vertex("A");
Vertex v2 = new Vertex("B");
Vertex v3 = new Vertex("C");
Vertex v4 = new Vertex("D");
Vertex v5 = new Vertex("E");
List<Vertex> list = new ArrayList<>();
v1.addNeighbor(v2);
v1.addNeighbor(v3);
v3.addNeighbor(v4);
v4.addNeighbor(v5);
list.add(v1);
list.add(v2);
list.add(v3);
list.add(v4);
list.add(v5);
DepthFirstSearch dfs = new DepthFirstSearch();
dfs.dfs(list);
}
}
Output
A
C
D
E
B5. Depth-first search using recursion
Following is the implementation of depth-first search using recursion:
import java.util.List;
public class DepthFirstSearch {
public void dfs(List<Vertex> vertexList){
for(Vertex v : vertexList) {
if(!v.isVisited()){
v.setVisited(true);
dfsHelper(v);
}
}
}
private void dfsHelper(Vertex vertex) {
System.out.println(vertex);
for(Vertex v: vertex.getNeighbors()){
if(!v.isVisited()){
v.setVisited(true);
dfsHelper(v);
}
}
}
}
6. Applications of Depth-first search
Depth First Search (DFS) has several practical applications across various domains in computer science and real-world problems. Some of the key applications include:
- Pathfinding and Maze Solving
DFS is commonly used to find paths in mazes or graphs. By exploring as far as possible along a branch before backtracking, it can help determine a path from a starting point to a goal, although it may not always find the shortest path. - Topological Sorting
In directed acyclic graphs (DAGs), DFS can be used for topological sorting. It helps order tasks in a way that each task precedes its dependent tasks, which is useful in scheduling problems, compiler optimizations, and dependency resolution. - Cycle Detection
DFS is used to detect cycles in both directed and undirected graphs. By tracking the visitation status of nodes (unvisited, visiting, visited), DFS can identify cycles in the graph, which is crucial in detecting deadlocks in resource allocation or validating the structure of a graph. - Connected Components
DFS is effective for finding all connected components in an undirected graph. It explores all vertices connected to a starting vertex, marking them as visited, and can be repeated for all unvisited vertices to discover all components in the graph. - Strongly Connected Components (SCC)
In a directed graph, DFS can be used to identify strongly connected components, where each vertex is reachable from every other vertex in the component. This is particularly useful in tasks like web crawlers and social network analysis. - Solving Puzzles and Games
DFS is used in puzzles like Sudoku, N-Queens, and other backtracking problems, where it tries all possible configurations until it finds a solution. It’s also applied in games like chess and checkers to explore all possible moves. - Finding Articulation Points and Bridges
In network theory, DFS can be used to find articulation points (vertices that, when removed, increase the number of connected components) and bridges (edges that, when removed, increase the number of connected components), both of which are important in network design and reliability analysis. - Tree Traversal
DFS is widely used for tree traversal, such as in-order, pre-order, and post-order traversal, which are fundamental operations for searching and manipulating tree-based data structures (e.g., binary trees, expression trees). - Web Crawling
In web crawlers, DFS can be used to explore and index the pages of a website. Starting from a root page, it recursively explores all the linked pages. - Artificial Intelligence (AI)
DFS is used in AI for exploring all possible states in a state space search. It’s applied in decision-making algorithms for problems like puzzle solving and game tree exploration, where all possible actions need to be evaluated. - File System Search
DFS can be used to traverse file systems, where it explores directories and files in a recursive manner. It’s used for tasks like searching for specific files or directories, copying, or deleting entire subdirectories.
6. Conclusion
Depth First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. Its recursive or iterative approach makes it versatile for solving a wide range of problems, such as pathfinding, cycle detection, topological sorting, and connected components. With a time complexity of O(V + E), where V is the number of vertices and E is the number of edges, DFS is efficient for traversing graphs represented as adjacency lists.
Understanding DFS provides a strong foundation for tackling complex graph-related problems and serves as a building block for more advanced algorithms. By mastering its concepts and applications, you’ll gain valuable insights into the inner workings of graph theory and problem-solving techniques in computer science.