Graph Traversals (BFS, DFS)

Graph Traversals (BFS, DFS)

Problem Scenario / Typical Use Case

Imagine you are analyzing a social network graph, and you need to explore all friends of a user or find the shortest connection path between two users.

Naively checking all nodes without structure is inefficient. Graph Traversals provide systematic ways to explore nodes and edges efficiently, either level by level (BFS) or depth-first (DFS).

Basic Idea

Graph traversal methods include:

1. Breadth-First Search (BFS): Explore nodes level by level, using a queue. Ideal for shortest-path problems in unweighted graphs.
2. Depth-First Search (DFS): Explore nodes deep into a path first, using recursion or a stack. Useful for pathfinding, cycle detection, and topological sorting.

Typical operations include:

• Visiting all nodes in a graph.
• Detecting connected components.
• Pathfinding in mazes or networks.
• Checking for cycles or reachability.

Advantages

• Systematic exploration: Ensures all nodes and edges are visited.
• Versatile: BFS and DFS suit different problem types (shortest paths vs. exhaustive path exploration).
• Foundation for complex algorithms: Used in topological sort, Dijkstra, and more.

Limitations / Considerations

• Requires graph representation (adjacency list or matrix).
• DFS can hit stack limits on large graphs; iterative DFS may be safer.
• BFS requires a queue which may consume significant memory for wide graphs.

Practical Examples / Thought Triggers

1. Friend Recommendations: BFS to find friends at distance 2 or 3.
2. Maze Solving / Pathfinding: DFS or BFS to explore possible paths.
3. Connected Components: Count isolated groups in social or network graphs.

Thought Triggers:

• Should I use BFS or DFS based on the problem goal (shortest path vs. full exploration)?
• Can traversal results be combined with other patterns like backtracking or dynamic programming?
• How should I handle visited nodes efficiently to avoid cycles or repeated visits?

Implementation Example

Here’s a Python example for BFS traversal on a graph:

from collections import deque

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

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            result.append(node)
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)
    return result

# Example usage
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 5],
    4: [2],
    5: [3]
}
print(bfs(graph, 1))
# Output: [1, 2, 3, 4, 5]

This demonstrates systematic level-by-level exploration using BFS.

Related Articles

• Backtracking & Recursive Search: DFS is a natural recursive traversal.
• Topological Sort: DFS is often used to determine ordering in DAGs.
• Graph-Based DP: Traversals are often the first step before applying DP on graphs.