KEMBAR78
Depth-First Search (DFS) Algorithm | PDF | Graph Theory | Computer Programming
Scribd
Upload
17 views7 pages

Depth-First Search (DFS) Algorithm

Depth-First Search (DFS) is an algorithm for traversing tree or graph structures by exploring as far as possible along each branch before backtracking, using a stack data structure. The algorithm marks visited vertices to avoid cycles and can be implemented recursively or iteratively. DFS is optimal for tasks like topological sorting, pathfinding, cycle detection, and finding connected components.

Uploaded by

avi003
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
17 views7 pages

Depth-First Search (DFS) Algorithm

Depth-First Search (DFS) is an algorithm for traversing tree or graph structures by exploring as far as possible along each branch before backtracking, using a stack data structure. The algorithm marks visited vertices to avoid cycles and can be implemented recursively or iteratively. DFS is optimal for tasks like topological sorting, pathfinding, cycle detection, and finding connected components.

Uploaded by

avi003
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 7

Depth-First Search (DFS)

Algorithm
A Comprehensive Guide to Graph Traversal
What is Depth-First Search?

Depth-First Search (DFS) is an algorithm for


traversing or searching tree or graph data
structures.

Explores as far as possible along each branch before


backtracking

Uses a stack data structure (explicit or call stack via


recursion)

Marks visited vertices to avoid cycles in graphs

Follows the principle: "Go deep, then backtrack"


How DFS Works

1 Start at a source vertex and mark it as visited

2 Explore an adjacent unvisited vertex, mark it, and continue


from there

3 If no unvisited adjacent vertices remain, backtrack to the


previous vertex

4 Continue until all vertices reachable from the source are


visited

5 Use a boolean visited array to track visited vertices and avoid


cycles
DFS Algorithm Implementation

// Recursive DFS implementation

DFS can be implemented using recursion or an explicit stack


function DFS(graph, start):
visited = array of false values for all vertices
Recursive implementation uses the call stack implicitly DFSUtil(graph, start, visited)

function DFSUtil(graph, vertex, visited):


Iterative implementation uses an explicit stack data structure // Mark current vertex as visited

visited[vertex] = true
Both approaches use a visited array to avoid cycles
// Print or process the current vertex
Recursive approach is cleaner but may cause stack overflow for
deep graphs print vertex

// Recur for all adjacent vertices


for each adjacent in graph[vertex]:
if visited[adjacent] is false:
DFSUtil(graph, adjacent, visited)

// Iterative DFS using explicit stack


DFS Example Problem

Problem: Graph Traversal

Given a graph with vertices 0-4 and edges as shown, perform DFS
starting from vertex 0.

1 Start at vertex 0: Mark as visited. Output: 0

2 Move to vertex 1: Mark as visited. Output: 1

3 Move to vertex 2: Mark as visited. Output: 2

4 Move to vertex 3: Mark as visited. Output: 3

5 Backtrack to vertex 2, then move to vertex 4: Mark as visited. Output:


4

Final DFS Traversal Output: 0 → 1 → 2 → 3 → 4


DFS vs BFS Comparison

Characteristic DFS BFS

Data Structure Stack Queue

Traversal Pattern Deep, then backtrack Level by level

Less (proportional to More (stores all nodes at a


Memory Usage
depth) level)

Path finding, topological Shortest path


Optimal For
sorting (unweighted)

Implementation Simpler with recursion Typically iterative


Applications of DFS

Topological Sorting

Ordering tasks based on their dependencies

Pathfinding

Finding paths between nodes in mazes or game maps

Cycle Detection

Identifying cycles in directed and undirected graphs

Connected Components

Finding strongly connected components in a graph

You might also like