What is a depth-first search (DFS) in C and how is it implemented?

Table of Contents

• Introduction
• Understanding Depth-First Search (DFS)
  • Key Characteristics of DFS
• DFS Implementation in C
  • Code Example: Recursive DFS in C
  • Explanation
  • Output:
• Iterative DFS Using Stack
  • Code Example: Iterative DFS in C
  • Explanation
  • Output:
• Practical Use Cases of DFS
  • Example: Cycle Detection Using DFS
• Conclusion

Introduction

Depth-First Search (DFS) is a fundamental algorithm used to traverse graphs and trees. Starting at a specified node, DFS explores as far as possible along a branch before backtracking, making it useful for solving graph-related problems like cycle detection, pathfinding, and connected components identification.

This guide will explain how DFS works and show how to implement it in C using both recursion and a stack-based iterative approach.

Understanding Depth-First Search (DFS)

DFS works by diving deep into a graph, visiting each node once before backtracking when no unvisited nodes remain in a branch. This depth-first traversal makes DFS suitable for graph problems where exploring one branch fully before others is required.

Key Characteristics of DFS

• Traversal Mechanism: DFS follows one path from the starting node to its deepest point, then backtracks.
• Time Complexity: O(V + E), where V is the number of vertices, and E is the number of edges.
• Space Complexity: O(V), where V is the number of vertices (due to recursion or stack usage).

DFS Implementation in C

DFS can be implemented recursively or iteratively. The recursive approach uses function calls to traverse the graph, while the iterative method uses a stack. In both approaches, the graph can be represented as an adjacency list.

Code Example: Recursive DFS in C

Explanation

• Graph Representation: The graph is stored as an adjacency list, with each vertex containing a list of connected vertices.
• DFS Function: The recursive function marks the current vertex as visited and then recursively visits all its adjacent unvisited vertices.
• Main Function: Constructs the graph, adds edges, and performs DFS from a starting vertex.

Output:

Iterative DFS Using Stack

To avoid recursion, DFS can also be implemented iteratively using a stack.

Code Example: Iterative DFS in C

Explanation

• Stack-Based DFS: A stack is used to keep track of the vertices to be visited. Vertices are pushed onto the stack when encountered, and popped off as they are visited.
• No Recursion: This method avoids the recursion limit of the system by using an explicit stack.

Output:

Practical Use Cases of DFS

DFS is used in various applications, such as:

• Pathfinding: Finding paths in a maze or network.
• Cycle Detection: Detecting cycles in a graph.
• Topological Sorting: Sorting vertices in directed acyclic graphs (DAGs).
• Connected Components: Identifying connected components in undirected graphs.

Example: Cycle Detection Using DFS

By modifying the DFS algorithm, you can detect cycles in an undirected graph by checking whether an already visited vertex is encountered again during the traversal.

Conclusion

Depth-First Search (DFS) is a fundamental algorithm for traversing graphs. It can be implemented either recursively or iteratively using a stack. In C, DFS is commonly used for tasks like pathfinding, cycle detection, and solving puzzles. Understanding the different ways to implement DFS will help in solving a wide variety of graph-related problems efficiently.