Published: December 27, 2024
Reading Time: 7 minutes
Depth First Search (DFS) is a recursive algorithm used to traverse or search through all the vertices in graphs and tree data structures. A recursive algorithm solves a problem by calling itself with smaller instances until reaching a base case that halts recursion.
In simple terms, traversal means visiting every node in a graph systematically. DFS program in C stands out as one of the fundamental techniques for graph and tree traversal. DFS follows a single path starting from the root or any specified node and goes as far as it can. It explores all descendants or adjacent nodes in one direction before backtracking to explore other paths. This depth-wise exploration makes it unique for problems that include connectivity, pathfinding, and even solving puzzles.
Depth First Search (DFS) is a traversal technique used to explore all nodes or vertices in non-linear data structures like graphs and trees. In a graph, DFS explores one path as deeply as possible before backtracking, ensuring all vertices connected to the starting node are visited. In contrast, DFS for a tree follows a similar approach but assumes no cycles and a hierarchical structure, making it simpler than graph traversal. This method is widely used for tasks like pathfinding, graph traversal, and solving connectivity problems.
The depth first search C program classifies each vertex in a graph into two categories:
The goal of DFS is to visit every vertex in the graph while ensuring no vertex is visited more than once. So, it effectively avoids cycles.
Consider an undirected graph with 8 vertices (numbered 0-7).
DFS(G, u):
u.visited = true
for each v ∈ G.Adj[u]:
if v.visited == false:
DFS(G, v)
init():
for each u ∈ G:
u.visited = false
for each u ∈ G:
DFS(G, u)
The pseudocode for DFS is shown above. In the init() function, the DFS function is executed for every node in the graph. This is particularly important because graphs may contain disconnected components, which means some vertices might not be reachable from others. By running the DFS algorithm on each node, it makes sure that every vertex in the graph is visited. This is regardless of whether the graph is connected or has isolated parts. It guarantees complete traversal of the graph.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h> // Added this line for malloc
// Graph DFS Implementation
#define MAX_VERTICES 8
// Adjacency Matrix Representation
int graph[MAX_VERTICES][MAX_VERTICES] = {
{0, 1, 1, 0, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 0, 0, 0},
{1, 0, 0, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 1, 0},
{0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 1, 0}
};
bool visited[MAX_VERTICES] = {false};
// Graph DFS Function
void graphDFS(int vertex) {
// Mark current vertex as visited
visited[vertex] = true;
printf("%d ", vertex);
// Explore all adjacent vertices
for (int i = 0; i < MAX_VERTICES; i++) {
if (graph[vertex][i] == 1 && !visited[i]) {
graphDFS(i);
}
}
}
// Tree DFS Implementation
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Create a new tree node
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Tree DFS (Pre-order Traversal)
void treeDFS(struct TreeNode* root) {
if (root == NULL) return;
// Visit root
printf("%d ", root->data);
// Traverse left subtree
treeDFS(root->left);
// Traverse right subtree
treeDFS(root->right);
}
int main() {
// Graph DFS Demonstration
printf("Graph DFS Traversal: ");
graphDFS(0); // Start DFS from vertex 0
printf("\n");
// Reset visited array for multiple traversals
for (int i = 0; i < MAX_VERTICES; i++) {
visited[i] = false;
}
// Tree DFS Demonstration
// Create a sample tree
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Tree DFS (Pre-order) Traversal: ");
treeDFS(root);
printf("\n");
return 0;
}
Graph DFS Traversal: 0 1 3 6 4 7 2 5
Tree DFS (Pre-order) Traversal: 1 2 3 4 5 6 7
The program demonstrates two implementations of DFS:
Graph DFS Implementation:
Tree DFS Implementation:
The DFS algorithm has diverse applications in graphing and beyond:
DFS can determine whether a path exists between two nodes. It explores all possible routes in weighted or unweighted graphs.
It helps verify if a graph can be divided into two sets such that no vertices within the same set are adjacent.
DFS is integral to algorithms like Kosaraju's and Tarjan's for identifying strongly connected components in directed graphs.
By tracking visited nodes and recursion stacks, DFS can detect cycles in both directed and undirected graphs.
In directed acyclic graphs (DAGs), DFS enables topological sorting, which is essential for scheduling and dependency management.
The DFS algorithm in C is used to explore solutions in problems like mazes, Sudoku, and other puzzles.
Depth First Search (DFS) is a foundational concept with applications in multiple domains like networking, AI, and problem-solving in software systems. For budding software engineers, mastering DFS is essential because it builds critical thinking and problem-solving skills required to tackle complex, real-world scenarios. Writing a DFS program in C goes beyond coding and goes into understanding data structures like graphs and trees, which are at the core of modern computing. This hands-on experience strengthens your ability to approach challenges logically and optimize solutions. Both of these skills are critical as you step into a professional software development career.
DFS explores all vertices of a graph by traversing as deeply as possible along each branch before backtracking.
DFS focuses on depth-first exploration. BFS (Breadth First Search) explores all neighbours at the current depth before moving deeper.
Recursion naturally mirrors the backtracking process of DFS. Therefore, it makes the implementation simpler and more intuitive for traversing graph paths.
Yes, DFS can identify cycles by checking for back edges in directed graphs or revisiting nodes in undirected graphs.
DFS is used for pathfinding, cycle detection, finding connected components, solving puzzles, and performing topological sorting in tasks like dependency resolution.
About NxtWave CCBP
NxtWave offers comprehensive programming courses including the CCBP 4.0 Academy program designed to make students job-ready with hands-on experience in data structures, algorithms, and software development.
Contact Information: