AI Notes

Depth-First Search (DFS) - Complete BTech Guide

Master DFS algorithm for artificial intelligence. Learn depth-first search implementation, backtracking, complexity analysis, and interview preparation with code examples. AI search algorithms explained for BTech students 2024.

Introduction

Depth-First Search (DFS) is one of the most fundamental graph traversal algorithms in artificial intelligence and computer science. Unlike breadth-first search which explores all neighbors at the current depth, DFS explores as far as possible along each branch before backtracking. This behavior makes it exceptionally useful for problems involving backtracking, cycle detection, and topological sorting.

In AI applications, DFS is crucial for problem-solving in game development, constraint satisfaction problems, and logical reasoning systems. Understanding DFS is essential for any BTech student preparing for technical interviews and AI system design.

What is Depth-First Search?

DFS is a graph traversal algorithm that explores vertices in a depth-wise manner using a stack (either explicit or implicit through recursion). The algorithm proceeds as follows:

Start at a source vertex
Mark it as visited
Recursively visit all unvisited neighbors
Backtrack when reaching a dead-end
Continue until all reachable vertices are explored

Visual Representation

DFS Traversal Order (Starting from A)

/|\

B C D

/| |

E F G

Traversal: A → B → E → F → C → D → G

(Assuming left-to-right order)

Stack Evolution

1. Push A: [A]

2. Push B: [A, B]

3. Push E: [A, B, E]

4. Pop E, Push F: [A, B, F]

5. Pop F, Pop B, Push C: [A, C]

And so on...

DFS Algorithm Implementation

Recursive Approach

The most intuitive implementation uses recursion:

Example

def dfs_recursive(graph, vertex, visited=None): """ Recursive DFS implementation Args: graph: Dictionary representing adjacency list vertex: Starting vertex visited: Set of visited vertices Returns: List of vertices in DFS order """ if visited is None: visited = set() visited.add(vertex) print(f"Visiting: {vertex}") for neighbor in graph.get(vertex, []): if neighbor not in visited: dfs_recursive(graph, neighbor, visited) return visited # Example usage graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } visited = dfs_recursive(graph, 'A') print(f"Visited vertices: {visited}") # Output: # Visiting: A # Visiting: B # Visiting: D # Visiting: E # Visiting: F # Visiting: C # Visited vertices: {'A', 'B', 'C', 'D', 'E', 'F'}

Iterative Approach (Stack-based)

For problems where recursion depth might be an issue, use an explicit stack:

Example

def dfs_iterative(graph, start): """ Iterative DFS using explicit stack Args: graph: Dictionary representing adjacency list start: Starting vertex Returns: List of vertices in DFS order """ visited = set() stack = [start] traversal_order = [] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) traversal_order.append(vertex) print(f"Visiting: {vertex}") # Add neighbors to stack (reverse order for left-to-right traversal) for neighbor in reversed(graph.get(vertex, [])): if neighbor not in visited: stack.append(neighbor) return traversal_order # Example usage result = dfs_iterative(graph, 'A') print(f"Traversal order: {result}") # Output: # Visiting: A # Visiting: B # Visiting: D # Visiting: E # Visiting: F # Visiting: C # Traversal order: ['A', 'B', 'D', 'E', 'F', 'C']

Detecting Cycles Using DFS

One important application of DFS is cycle detection in graphs:

Example

def has_cycle(graph, n): """ Detect cycle in undirected graph using DFS Args: graph: Dictionary representing adjacency list n: Number of vertices Returns: Boolean indicating if cycle exists """ visited = [False] * (n + 1) def dfs_cycle(vertex, parent): visited[vertex] = True for neighbor in graph.get(vertex, []): if not visited[neighbor]: if dfs_cycle(neighbor, vertex): return True elif neighbor != parent: # Back edge found return True return False for i in range(1, n + 1): if not visited[i]: if dfs_cycle(i, -1): return True return False # Example cycle_graph = { 1: [2, 3], 2: [1, 4], 3: [1], 4: [2, 5], 5: [4] } print(f"Has cycle: {has_cycle(cycle_graph, 5)}") # Output: Has cycle: False

Topological Sorting with DFS

DFS is ideal for topological sorting in Directed Acyclic Graphs (DAG):

Example

def topological_sort(graph, n): """ Perform topological sort using DFS Args: graph: Dictionary representing adjacency list n: Number of vertices Returns: List of vertices in topological order """ visited = [False] * (n + 1) stack = [] def dfs_topo(vertex): visited[vertex] = True for neighbor in graph.get(vertex, []): if not visited[neighbor]: dfs_topo(neighbor) stack.append(vertex) for i in range(1, n + 1): if not visited[i]: dfs_topo(i) return stack[::-1] # Example: Course prerequisites topo_graph = { 1: [2, 3], 2: [3, 4], 3: [4], 4: [] } order = topological_sort(topo_graph, 4) print(f"Topological order: {order}") # Output: Topological order: [1, 2, 3, 4]

Complexity Analysis

Aspect	Value	Notes
Time Complexity	O(V + E)	V = vertices, E = edges
Space Complexity	O(V)	For recursion stack/visited set
Best Case	O(V)	Tree structure
Worst Case	O(V + E)	Densely connected graph
Auxiliary Space	O(h)	h = height of recursion

DFS vs BFS Comparison

Property	DFS	BFS
Data Structure	Stack	Queue
Memory	O(h) where h is height	O(w) where w is max width
Space Efficient	Generally yes	Can use more memory
Path Finding	Not optimal	Finds shortest path
Backtracking	Natural	Requires modification
Cycle Detection	Efficient	Also efficient
Implementation	Recursive/Stack	Iterative/Queue
Best For	Mazes, puzzles	Shortest path, level-order

Interview Q&A

Q1: What is the main difference between DFS and BFS?

A: DFS uses a stack and explores deeply before backtracking, while BFS uses a queue and explores level by level. DFS is memory-efficient for deep graphs, while BFS finds the shortest path in unweighted graphs. DFS is ideal for backtracking problems; BFS is ideal for shortest path problems. Both have O(V+E) time complexity but different space characteristics.

Q2: When would you use DFS over BFS?

A: Use DFS when:

You need to explore all possible solutions (backtracking)
You need topological sorting
Memory is limited (shallower recursion)
You're solving puzzles or constraint satisfaction
Detecting cycles in directed graphs
Finding strongly connected components

Use BFS when:

You need the shortest path
You want level-order traversal
Graph is shallow but wide
You need to find connected components
Implementing bipartite checking

Q3: Explain how DFS handles cycles in a graph.

A: In DFS, we maintain a visited set. When exploring neighbors, if a neighbor is already visited and it's not the parent (in undirected graphs), a cycle exists. In directed graphs, we can use three states: unvisited (white), visiting (gray), visited (black). A back edge (pointing to a gray node) indicates a cycle.

Q4: What is the time complexity of DFS and why?

A: Time complexity is O(V + E): each vertex is visited exactly once (V), and each edge is examined exactly once (E). Space complexity is O(V) for the visited set and O(h) for the recursion stack, where h is the height of the call tree.

Q5: How would you implement DFS for a problem with millions of nodes?

A: Use iterative approach instead of recursion to avoid stack overflow. Implement with explicit stack. Use lazy loading for graph data to save memory. Implement early termination when solution is found. For very large graphs, consider distributed DFS or bidirectional search if applicable.

Q6: Describe how DFS is used in solving the N-Queens problem.

A: DFS with backtracking: Start from row 0, try placing a queen in each column, check if placement is safe (no conflicts), recursively solve for next row, if no solution found, backtrack and try next column, continue until all queens placed or all options exhausted. This explores the solution space depth-first.

Quick Revision Notes

Definition: Graph traversal using stack (explicit/implicit)
Time Complexity: O(V + E)
Space Complexity: O(V) visited set + O(h) recursion
Key Feature: Explores deeply before backtracking
Best for: Backtracking, cycle detection, topological sorting, puzzles
Implementation: Recursive (cleaner) or iterative (safer for deep graphs)
Base Cases: Single vertex, disconnected components
Common Mistakes: Not marking visited, infinite loops, stack overflow from recursion
Applications: Game solving, constraint satisfaction, strongly connected components
Related Algorithms: BFS, Dijkstra's, A*, topological sort

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Depth-First Search (DFS) - Complete BTech Guide.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.

Search Terms

artificial-intelligence, artificial intelligence, artificial, intelligence, search, algorithms, depth, first

Continue learning this concept

Search AlgorithmsBreadth-First Search (BFS) - AI Algorithm GuideComplete BFS algorithm tutorial for artificial intelligence. Learn breadth-first search implementation, shortest path, complexity analysis, and interview preparation. Essential BTech notes on graph algorithms 2024.Search AlgorithmsGreedy Best-First Search - Heuristic AI AlgorithmLearn Greedy Best-First Search for AI. Understand heuristic-based search, priority queues, implementation, advantages and limitations. Technical interview guide 2024.Search AlgorithmsA* Search Algorithm - Complete AI GuideMaster A* pathfinding algorithm for artificial intelligence. Learn heuristic functions, admissibility, optimality, implementation with code. Technical interview preparation 2024.Search AlgorithmsInformed Search Strategies - AI AlgorithmsComplete tutorial on informed search strategies in artificial intelligence. Learn greedy search, best-first, A*, heuristic functions. BTech notes 2024.Search AlgorithmsIterative Deepening Search (IDS) - AI AlgorithmMaster Iterative Deepening Search (IDS) combining benefits of BFS and DFS. Learn depth-limited search, memory efficiency, implementation. Complete BTech guide 2024.Search AlgorithmsSearch Algorithms Comparison - AI TechniquesCompare BFS, DFS, UCS, A*, and search algorithms. Learn when to use each algorithm, complexity analysis, practical applications in AI systems.

PreviousBreadth-First Search (BFS) - AI Algorithm Guide NextGreedy Best-First Search - Heuristic AI Algorithm

AI Notes

Depth-First Search (DFS) - Complete BTech Guide

Introduction

What is Depth-First Search?

DFS is a graph traversal algorithm that explores vertices in a depth-wise manner using a stack (either explicit or implicit through recursion). The algorithm proceeds as follows:

Start at a source vertex
Mark it as visited
Recursively visit all unvisited neighbors
Backtrack when reaching a dead-end
Continue until all reachable vertices are explored

Visual Representation

DFS Traversal Order (Starting from A)

/|\

B C D

/| |

E F G

Traversal: A → B → E → F → C → D → G

(Assuming left-to-right order)

Stack Evolution

1. Push A: [A]

2. Push B: [A, B]

3. Push E: [A, B, E]

4. Pop E, Push F: [A, B, F]

5. Pop F, Pop B, Push C: [A, C]

And so on...

DFS Algorithm Implementation

Recursive Approach

The most intuitive implementation uses recursion:

Example

Iterative Approach (Stack-based)

For problems where recursion depth might be an issue, use an explicit stack:

Example

Detecting Cycles Using DFS

One important application of DFS is cycle detection in graphs:

Example

Topological Sorting with DFS

DFS is ideal for topological sorting in Directed Acyclic Graphs (DAG):

Example

Complexity Analysis

Aspect	Value	Notes
Time Complexity	O(V + E)	V = vertices, E = edges
Space Complexity	O(V)	For recursion stack/visited set
Best Case	O(V)	Tree structure
Worst Case	O(V + E)	Densely connected graph
Auxiliary Space	O(h)	h = height of recursion

DFS vs BFS Comparison

Property	DFS	BFS
Data Structure	Stack	Queue
Memory	O(h) where h is height	O(w) where w is max width
Space Efficient	Generally yes	Can use more memory
Path Finding	Not optimal	Finds shortest path
Backtracking	Natural	Requires modification
Cycle Detection	Efficient	Also efficient
Implementation	Recursive/Stack	Iterative/Queue
Best For	Mazes, puzzles	Shortest path, level-order

Interview Q&A

Q1: What is the main difference between DFS and BFS?

Q2: When would you use DFS over BFS?

A: Use DFS when:

You need to explore all possible solutions (backtracking)
You need topological sorting
Memory is limited (shallower recursion)
You're solving puzzles or constraint satisfaction
Detecting cycles in directed graphs
Finding strongly connected components

Use BFS when:

You need the shortest path
You want level-order traversal
Graph is shallow but wide
You need to find connected components
Implementing bipartite checking

Q3: Explain how DFS handles cycles in a graph.

Q4: What is the time complexity of DFS and why?

Q5: How would you implement DFS for a problem with millions of nodes?

Q6: Describe how DFS is used in solving the N-Queens problem.

Quick Revision Notes

Definition: Graph traversal using stack (explicit/implicit)
Time Complexity: O(V + E)
Space Complexity: O(V) visited set + O(h) recursion
Key Feature: Explores deeply before backtracking
Best for: Backtracking, cycle detection, topological sorting, puzzles
Implementation: Recursive (cleaner) or iterative (safer for deep graphs)
Base Cases: Single vertex, disconnected components
Common Mistakes: Not marking visited, infinite loops, stack overflow from recursion
Applications: Game solving, constraint satisfaction, strongly connected components
Related Algorithms: BFS, Dijkstra's, A*, topological sort

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Depth-First Search (DFS) - Complete BTech Guide.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.

Search Terms

artificial-intelligence, artificial intelligence, artificial, intelligence, search, algorithms, depth, first

Continue learning this concept

PreviousBreadth-First Search (BFS) - AI Algorithm Guide NextGreedy Best-First Search - Heuristic AI Algorithm