Graph Traversal Algorithms in DSA: A Complete Guide

Posted by tintin_2003 on 2025-10-17 20:17:04 |

Share: Facebook | Twitter | Whatsapp | Linkedin Visits: 67

Graph Traversal Algorithms in DSA: A Complete Guide

Introduction

Graph traversal algorithms are fundamental techniques in Data Structures and Algorithms (DSA) used to visit all vertices in a graph systematically. These algorithms form the backbone of many complex problems like pathfinding, network analysis, social network connections, and recommendation systems.

In this comprehensive guide, we'll explore the two primary graph traversal algorithms:

1. Breadth-First Search (BFS)
2. Depth-First Search (DFS)

Understanding Graphs

Before diving into traversal algorithms, let's understand what a graph is:

• A graph consists of vertices (nodes) and edges (connections between nodes)
• Graphs can be directed (edges have direction) or undirected (bidirectional edges)
• Graphs can be weighted (edges have values) or unweighted

Graph Representation

We'll use an adjacency list representation, where each vertex stores a list of its neighbors. This is memory-efficient for sparse graphs.

1. Breadth-First Search (BFS)

Concept

BFS explores a graph level by level, starting from a source vertex. It visits all neighbors at the current depth before moving to vertices at the next depth level.

Key Characteristics:

• Uses a queue data structure (FIFO - First In, First Out)
• Guarantees the shortest path in unweighted graphs
• Time Complexity: O(V + E) where V = vertices, E = edges
• Space Complexity: O(V) for the queue and visited set

Algorithm Steps:

1. Start at a source vertex and mark it as visited
2. Add the source to a queue
3. While the queue is not empty:
   • Dequeue a vertex
   • Process it
   • Enqueue all unvisited neighbors and mark them as visited

Python Implementation

from collections import deque, defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v):
        """Add an edge from vertex u to vertex v"""
        self.graph[u].append(v)
    
    def bfs(self, start):
        """Breadth-First Search traversal"""
        visited = set()
        queue = deque([start])
        visited.add(start)
        traversal_order = []
        
        while queue:
            vertex = queue.popleft()
            traversal_order.append(vertex)
            
            # Visit all neighbors
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return traversal_order
    
    def bfs_shortest_path(self, start, end):
        """Find shortest path using BFS"""
        if start == end:
            return [start]
        
        visited = {start}
        queue = deque([(start, [start])])
        
        while queue:
            vertex, path = queue.popleft()
            
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    new_path = path + [neighbor]
                    
                    if neighbor == end:
                        return new_path
                    
                    visited.add(neighbor)
                    queue.append((neighbor, new_path))
        
        return None  # No path found

# Example Usage
print("=" * 50)
print("BREADTH-FIRST SEARCH (BFS) DEMONSTRATION")
print("=" * 50)

g_bfs = Graph()
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (3, 5)]

for u, v in edges:
    g_bfs.add_edge(u, v)

print("\nGraph Structure (Adjacency List):")
for vertex in sorted(g_bfs.graph.keys()):
    print(f"{vertex} -> {g_bfs.graph[vertex]}")

start_vertex = 0
print(f"\nBFS Traversal starting from vertex {start_vertex}:")
bfs_result = g_bfs.bfs(start_vertex)
print(f"Order: {' -> '.join(map(str, bfs_result))}")

print("\nShortest Path from 0 to 5:")
path = g_bfs.bfs_shortest_path(0, 5)
if path:
    print(f"Path: {' -> '.join(map(str, path))}")
    print(f"Length: {len(path) - 1} edges")
else:
    print("No path found")

Expected Output

==================================================
BREADTH-FIRST SEARCH (BFS) DEMONSTRATION
==================================================

Graph Structure (Adjacency List):
0 -> [1, 2]
1 -> [2, 3]
2 -> [4]
3 -> [4, 5]

BFS Traversal starting from vertex 0:
Order: 0 -> 1 -> 2 -> 3 -> 4 -> 5

Shortest Path from 0 to 5:
Path: 0 -> 1 -> 3 -> 5
Length: 3 edges

BFS Applications:

• Finding shortest path in unweighted graphs
• Level-order traversal of trees
• GPS navigation systems
• Social networking features (friends within n connections)
• Web crawlers

2. Depth-First Search (DFS)

Concept

DFS explores a graph by going as deep as possible along each branch before backtracking. It follows a path until it reaches a dead end, then backtracks to explore other paths.

Key Characteristics:

• Uses a stack data structure (LIFO - Last In, First Out) or recursion
• Does not guarantee shortest path
• Time Complexity: O(V + E)
• Space Complexity: O(V) for the recursion stack/visited set

Algorithm Steps:

1. Start at a source vertex and mark it as visited
2. Recursively visit all unvisited neighbors
3. Backtrack when all neighbors are visited

Python Implementation

class GraphDFS:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v):
        """Add an edge from vertex u to vertex v"""
        self.graph[u].append(v)
    
    def dfs_recursive(self, vertex, visited, traversal_order):
        """Recursive DFS helper function"""
        visited.add(vertex)
        traversal_order.append(vertex)
        
        for neighbor in self.graph[vertex]:
            if neighbor not in visited:
                self.dfs_recursive(neighbor, visited, traversal_order)
    
    def dfs(self, start):
        """Depth-First Search traversal (recursive)"""
        visited = set()
        traversal_order = []
        self.dfs_recursive(start, visited, traversal_order)
        return traversal_order
    
    def dfs_iterative(self, start):
        """Depth-First Search using stack (iterative)"""
        visited = set()
        stack = [start]
        traversal_order = []
        
        while stack:
            vertex = stack.pop()
            
            if vertex not in visited:
                visited.add(vertex)
                traversal_order.append(vertex)
                
                # Add neighbors in reverse order to match recursive DFS
                for neighbor in reversed(self.graph[vertex]):
                    if neighbor not in visited:
                        stack.append(neighbor)
        
        return traversal_order
    
    def has_cycle(self):
        """Detect cycle in directed graph using DFS"""
        visited = set()
        rec_stack = set()
        
        def has_cycle_util(vertex):
            visited.add(vertex)
            rec_stack.add(vertex)
            
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    if has_cycle_util(neighbor):
                        return True
                elif neighbor in rec_stack:
                    return True
            
            rec_stack.remove(vertex)
            return False
        
        for vertex in self.graph:
            if vertex not in visited:
                if has_cycle_util(vertex):
                    return True
        return False

# Example Usage
print("\n" + "=" * 50)
print("DEPTH-FIRST SEARCH (DFS) DEMONSTRATION")
print("=" * 50)

g_dfs = GraphDFS()
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (3, 5)]

for u, v in edges:
    g_dfs.add_edge(u, v)

print("\nGraph Structure (Adjacency List):")
for vertex in sorted(g_dfs.graph.keys()):
    print(f"{vertex} -> {g_dfs.graph[vertex]}")

start_vertex = 0
print(f"\nDFS Traversal (Recursive) starting from vertex {start_vertex}:")
dfs_result = g_dfs.dfs(start_vertex)
print(f"Order: {' -> '.join(map(str, dfs_result))}")

print(f"\nDFS Traversal (Iterative) starting from vertex {start_vertex}:")
dfs_iterative_result = g_dfs.dfs_iterative(start_vertex)
print(f"Order: {' -> '.join(map(str, dfs_iterative_result))}")

print("\nCycle Detection:")
print(f"Does the graph have a cycle? {g_dfs.has_cycle()}")

# Test with a cyclic graph
g_cyclic = GraphDFS()
g_cyclic.add_edge(0, 1)
g_cyclic.add_edge(1, 2)
g_cyclic.add_edge(2, 0)
print(f"Cyclic graph test: {g_cyclic.has_cycle()}")

Expected Output

==================================================
DEPTH-FIRST SEARCH (DFS) DEMONSTRATION
==================================================

Graph Structure (Adjacency List):
0 -> [1, 2]
1 -> [2, 3]
2 -> [4]
3 -> [4, 5]

DFS Traversal (Recursive) starting from vertex 0:
Order: 0 -> 1 -> 2 -> 4 -> 3 -> 5

DFS Traversal (Iterative) starting from vertex 0:
Order: 0 -> 1 -> 2 -> 4 -> 3 -> 5

Cycle Detection:
Does the graph have a cycle? False
Cyclic graph test: True

DFS Applications:

• Detecting cycles in graphs
• Topological sorting
• Finding connected components
• Solving maze problems
• Backtracking algorithms (Sudoku, N-Queens)

Complete Example: Comparing BFS and DFS

def create_sample_graph():
    """Create a more complex graph for comparison"""
    g = defaultdict(list)
    edges = [
        (1, 2), (1, 3),
        (2, 4), (2, 5),
        (3, 6), (3, 7),
        (4, 8), (5, 8),
        (6, 9), (7, 9)
    ]
    for u, v in edges:
        g[u].append(v)
    return g

print("\n" + "=" * 50)
print("BFS vs DFS COMPARISON")
print("=" * 50)

# Create graph
graph = create_sample_graph()

print("\nGraph Structure (Tree-like):")
print("         1")
print("       /   \\")
print("      2     3")
print("     / \\   / \\")
print("    4   5 6   7")
print("     \\ /   \\ /")
print("      8     9")

# BFS
g_bfs_compare = Graph()
g_bfs_compare.graph = graph
bfs_order = g_bfs_compare.bfs(1)

# DFS
g_dfs_compare = GraphDFS()
g_dfs_compare.graph = graph
dfs_order = g_dfs_compare.dfs(1)

print(f"\nBFS Traversal from vertex 1:")
print(f"{' -> '.join(map(str, bfs_order))}")
print("(Level by level: explores neighbors before going deeper)")

print(f"\nDFS Traversal from vertex 1:")
print(f"{' -> '.join(map(str, dfs_order))}")
print("(Goes deep first: explores one path completely before backtracking)")

Expected Output

==================================================
BFS vs DFS COMPARISON
==================================================

Graph Structure (Tree-like):
         1
       /   \
      2     3
     / \   / \
    4   5 6   7
     \ /   \ /
      8     9

BFS Traversal from vertex 1:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
(Level by level: explores neighbors before going deeper)

DFS Traversal from vertex 1:
1 -> 2 -> 4 -> 8 -> 5 -> 3 -> 6 -> 9 -> 7
(Goes deep first: explores one path completely before backtracking)

Key Differences: BFS vs DFS

When to Use Which?

Use BFS when:

• You need the shortest path in an unweighted graph
• The solution is likely to be closer to the source
• You need to explore nodes level by level
• Memory is not a constraint

Use DFS when:

• The solution is far from the source
• You need to visit all nodes anyway
• Memory is constrained (tree-like structure)
• You need to detect cycles or perform topological sorting

Time and Space Complexity Summary

Both BFS and DFS have:

• Time Complexity: O(V + E)

  • V: number of vertices
  • E: number of edges
  • We visit each vertex once and explore each edge once

• Space Complexity: O(V)

  • BFS: Queue can contain all vertices at a level
  • DFS: Recursion stack depth or explicit stack size

Conclusion

Graph traversal algorithms are essential tools in a programmer's toolkit. BFS and DFS each have their strengths and ideal use cases:

• BFS excels at finding shortest paths and exploring graphs level by level
• DFS is perfect for exploring all possibilities, detecting cycles, and solving backtracking problems

Understanding when and how to apply these algorithms is crucial for solving complex graph problems efficiently. Practice implementing both approaches to build intuition about which algorithm suits your specific problem best.

Happy coding! 🚀