DFS (Depth-First Search) Algorithm Code in C/C++

Depth-First Search (DFS) is a graph traversal algorithm that explores vertices or nodes of a graph in depth before visiting the neighboring vertices. It starts at a given vertex and systematically explores as far as possible along each branch before backtracking.

The DFS algorithm follows these steps:

1. Start by selecting a source vertex to begin the traversal.

2. Mark the source vertex as visited and process it. This may involve performing a specific action on the vertex, such as printing its value.

3. Explore an unvisited neighbor of the current vertex. If there are multiple unvisited neighbors, select one of them arbitrarily.

4. Repeat step 3 recursively for the chosen neighbor. Mark it as visited and process it.

5. If there are no unvisited neighbors, backtrack to the previous vertex (i.e., return from the recursive call).

6. Repeat steps 3-5 until all vertices have been visited.

DFS can be implemented using recursion or a stack data structure. The recursive implementation uses the call stack implicitly to keep track of the visited vertices and backtracks when necessary. The iterative implementation, using a stack, simulates the call stack explicitly.

DFS is useful for various graph-related problems, such as finding connected components, detecting cycles, performing topological sorting, and solving maze problems.

It's important to note that DFS doesn't guarantee the shortest path between two vertices. It may traverse long paths before exploring shorter ones. If a complete traversal of all vertices is required, DFS can ensure that every vertex is visited exactly once.

However, in the case of a disconnected graph, it's necessary to apply DFS to each unvisited vertex to cover all components.

Overall, DFS is a fundamental graph traversal algorithm that provides a way to explore and analyze graphs in a systematic manner.

#include <stdio.h> #define MAX_NODES 100 int visited[MAX_NODES]; int adjacencyMatrix[MAX_NODES][MAX_NODES]; int numNodes; void initialize() { int i, j; for (i = 0; i < MAX_NODES; i++) { visited[i] = 0; for (j = 0; j < MAX_NODES; j++) { adjacencyMatrix[i][j] = 0; } } } void addEdge(int startNode, int endNode) { adjacencyMatrix[startNode][endNode] = 1; adjacencyMatrix[endNode][startNode] = 1; } void depthFirstSearch(int currentNode) { int i; printf("%d ", currentNode); visited[currentNode] = 1; for (i = 0; i < numNodes; i++) { if (adjacencyMatrix[currentNode][i] == 1 && visited[i] == 0) { depthFirstSearch(i); } } } int main() { int i, j; int startNode; printf("Enter the number of nodes: "); scanf("%d", &numNodes); initialize(); printf("Enter the adjacency matrix:\n"); for (i = 0; i < numNodes; i++) { for (j = 0; j < numNodes; j++) { scanf("%d", &adjacencyMatrix[i][j]); } } printf("Enter the starting node: "); scanf("%d", &startNode); printf("DFS traversal starting from node %d: ", startNode); depthFirstSearch(startNode); return 0; }

By Md. Rahat (CSE, BU)