Depth First Search - DFS Algorithm with Practical Examples

• Depth First Search
• DFS Algorithm
• Types of DFS Traversal
  • Pre-order Traversal:
  • Post-order Traversal:
  • In-order Traversal:
• Working Principle of DFS
  • The Order of Nodes in DFS Traversal
• 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 : -is-this-fft-

¶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:

1. Choose a starting vertex and mark it as visited.
2. Visit the starting vertex and explore its adjacent vertices.
3. For each unvisited adjacent vertex, recursively apply DFS.
4. Continue exploring vertices until all reachable vertices are visited or no unvisited vertices remain.
5. 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 :

¶Pre-order Traversal:

In pre-order 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 pre-order traversal visits node 1 first, then explores its left subtree (nodes 2, 4, and 5), and finally explores its right subtree (node 3).

Pre-order traversal output: 1, 2, 4, 5, 3

¶Post-order Traversal:

In post-order 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 post-order traversal visits the left subtree of node 1 first (nodes 4 and 5), then the right subtree (node 3), and finally processes node 1.

Post-order traversal output: 4, 5, 2, 3, 1

¶In-order Traversal:

In in-order 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, in-order traversal visits nodes in non-decreasing order of their values. In the example provided, the in-order 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).

In-order 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:

1. 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.

2. 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.

3. Mark Visited:

Mark each visited vertex to avoid revisiting it.

We mark the starting node A since we have already visited it.

4. 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.

5. 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;
}

¶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, puzzle-solving, 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 depth-limited search and iterative deepening depth-first 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.

Run C programming online