Data Structure and Algorithm
Depth First Search  DFS Data Structure and Algorithm
 Depth First Search
 DFS Algorithm
 Types of DFS Traversal
 Working Principle of DFS
 Implementation of DFS in C
 Applications of DFS
 Run C Programming Online Compiler
Imagine being trapped in a maze, with confusing paths at every turn. That’s where Depth First Search (DFS) comes in handy! It’s like having a smart guide who carefully explores each path until finding the way out. DFS is commonly used for tasks such as graph traversal, cycle detection, pathfinding, and topological sorting. It is an essential component of many graph algorithms and is widely employed in various applications across computer science and related fields.
¶Depth First Search
Depth First Search (DFS
) is a basic but powerful way to explore a graph. It starts at a point and goes as far as it can along each branch before coming back and trying a different path. Think of it like exploring a maze, always going down one path until you hit a dead end, then backtracking to try another route. With DFS, we can systematically uncover all the connections and paths in a graph.
Depth First Search Visualization by : isthisfft
¶DFS Algorithm
It starts at a selected vertex and explores as far as possible along each branch before backtracking. DFS can be implemented using recursion or a stack data structure. Here’s a basic outline of the DFS algorithm:
 Choose a starting vertex and mark it as visited.
 Visit the starting vertex and explore its adjacent vertices.
 For each unvisited adjacent vertex, recursively apply DFS.
 Continue exploring vertices until all reachable vertices are visited or no unvisited vertices remain.
 If all reachable vertices are visited, backtrack to the previous vertex and explore other branches.
¶Types of DFS Traversal
Depth First Search (DFS) traversal can be categorized based on the order in which vertices are visited :
¶Preorder Traversal:
In preorder traversal, the current vertex is visited before visiting its adjacent vertices. This means that the vertex is processed as soon as it is encountered during the traversal. It starts at the root of the tree and recursively explores the left subtree first, followed by the right subtree. In the example provided, the preorder traversal visits node 1 first, then explores its left subtree (nodes 2, 4, and 5), and finally explores its right subtree (node 3).
Preorder traversal output: 1, 2, 4, 5, 3
¶Postorder Traversal:
In postorder traversal, the current vertex is visited after visiting all its adjacent vertices. This means that the vertex is processed only after all its children (or adjacent vertices) have been visited. It starts at the root of the tree and recursively explores the left subtree first, followed by the right subtree. The node’s value is processed after visiting its children. In the example provided, the postorder traversal visits the left subtree of node 1 first (nodes 4 and 5), then the right subtree (node 3), and finally processes node 1.
Postorder traversal output: 4, 5, 2, 3, 1
¶Inorder Traversal:
In inorder traversal, the current node is visited between recursively traversing its left and right subtrees. The order of operations typically involves traversing the left subtree, processing the node’s value, and then traversing the right subtree. In binary search trees, inorder traversal visits nodes in nondecreasing order of their values. In the example provided, the inorder traversal first visits the left subtree of node 1 (nodes 4 and 2), then processes node 1, and finally visits its right subtree (nodes 5 and 3).
Inorder traversal output: 4, 2, 5, 1, 3
¶Working Principle of DFS
The working principle of Depth First Search (DFS) revolves around systematically exploring a graph’s vertices and edges. It starts at a selected vertex and explores as far as possible along each branch before backtracking. Lets understand how dfs works through an example on the following graph:
 Start at a Vertex:
Choose a starting vertex to begin the traversal.
Here, we choose the node A
as the starting node and start our traversal.
 Explore Adjacent Vertices:
Visit the starting vertex and explore its adjacent vertices one by one. For each unvisited adjacent vertex, recursively apply DFS .
Here, the adjacent vertices of the starting node A
are B
and C
. So, in turn we apply DFS
on each of them.
 Mark Visited:
Mark each visited vertex to avoid revisiting it.
We mark the starting node A
since we have already visited it.
 Repeat Exploration:
Continue exploring vertices recursively or using the stack until all reachable vertices are visited or no unvisited vertices remain.
After visiting vertex B
, we explore its adjacent vertices. Starting with vertex E
, we continue traversing until there are no more unvisited nodes. Upon reaching the end, we backtrack to vertex B
. Next, we explore vertices D
, C
, and F
using the same process.
 Backtrack if Necessary: If all reachable vertices are visited, backtrack to the previous vertex and explore other branches.
¶The Order of Nodes in DFS Traversal
There may be multiple possible order of dfs traversal of a graph. One possible order of the nodes in the DFS traversal of the mentioned graph:
A
>B
>E
>D
>C
>F
¶Implementation of DFS in C
Lets see an implementation of DFS in C using adjacency matrix,
#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 100
// Adjacency list representation of the graph
int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];
int numNodes = 6; // Number of nodes in the graph
// Function to perform Depth First Search
void dfs(int v) {
visited[v] = true;
printf("%d ", v);
// Traverse all adjacent vertices of vertex v
for (int i = 0; i < numNodes; i++) {
if (graph[v][i] && !visited[i]) {
dfs(i);
}
}
}
int main() {
// Sample graph (adjacency matrix)
int numEdges = 7;
int edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}};
// Populate the adjacency matrix
for (int i = 0; i < numEdges; i++) {
int u = edges[i][0];
int v = edges[i][1];
graph[u][v] = 1;
graph[v][u] = 1; // If the graph is undirected
}
// Initialize visited array
for (int i = 0; i < MAX_NODES; i++) {
visited[i] = false;
}
printf("Depth First Traversal: ");
for (int i = 0; i < numNodes; i++) {
if (!visited[i]) {
dfs(i);
}
}
return 0;
}
Depth First Traversal: 0 1 3 5 4 2
¶Applications of DFS
Depth First Search (DFS) finds numerous applications across various domains due to its versatility and simplicity. Here are some common applications of DFS:

Graph Traversal: DFS is primarily used for traversing graphs, visiting each vertex and edge in a systematic manner. It helps identify connected components, cycles, and paths between nodes.

Maze Solving: DFS is employed to navigate through mazes, systematically exploring each pathway until reaching the exit. It ensures thorough exploration of all possible routes.

Topological Sorting: DFS can perform topological sorting of directed acyclic graphs (DAGs), crucial in scheduling tasks with dependencies or resolving build dependencies.

Detecting Cycles: DFS can detect cycles in a graph by identifying back edges during traversal. This is valuable for applications where cycles need to be avoided, such as in network routing or deadlock detection.

Pathfinding: DFS can be used to find paths between nodes in a graph, including shortest paths if appropriate criteria are applied. This is useful in routing algorithms, puzzlesolving, and navigation systems.

Solving Puzzles: DFS is employed in solving various puzzles and games, such as Sudoku, Minesweeper, and the Eight Queens problem. It systematically explores possible solutions until a valid one is found.

Network Analysis: DFS can analyze networks, such as social networks or computer networks, by exploring connections between nodes and identifying patterns or clusters within the network.

Generating Mazes: DFS can be used to generate mazes, where each cell in the maze is a vertex and edges represent passages between adjacent cells. It ensures that all cells are reachable and that the maze has no unreachable areas or loops.

Artificial Intelligence: DFS is used in AI algorithms, such as depthlimited search and iterative deepening depthfirst search, for solving problems in areas like planning, scheduling, and game playing.
¶Run C Programming Online Compiler
To make your learning more effective, exercise the coding examples in the text editor below.
Graph Data Structure with Practical Examples
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
11

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
9

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development