Graph Traversals: Depth First Search (DFS) & Breadth First Search (BFS)

Graph traversal means visiting all the nodes (vertices) in a graph in a systematic way. DFS and BFS are two fundamental graph traversal techniques used widely in computer science.

Depth First Search (DFS)

DFS explores as deep as possible along each branch before backtracking. It uses recursion or stack data structure.

How DFS Works

• Start from a source node.
• Visit the node and mark it as visited.
• Recursively visit all unvisited adjacent nodes.
• Backtrack when no unvisited adjacent node is left.

DFS Python Example (Recursive)

def dfs(graph, node, visited):
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

# Usage Example
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
visited = set()
dfs(graph, 'A', visited)

Breadth First Search (BFS)

BFS explores neighbor nodes level by level using a queue data structure, visiting all nodes at the current depth before going deeper.

How BFS Works

• Start from a source node.
• Visit the node, enqueue it and mark as visited.
• Dequeue a node and enqueue all its unvisited neighbors.
• Repeat until the queue is empty.

BFS Python Example

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Usage Example
bfs(graph, 'A')

Applications of DFS & BFS

• Cycle detection in graphs.
• Finding connected components.
• Pathfinding and shortest path algorithms.
• Topological sorting of DAGs.
• Solving puzzles like mazes and Sudoku.