Traversal (BFS/DFS)

In life and in graphs, you either go deep and get lost or go wide and stay grounded. Both paths reveal something new.

Imagine you're in a maze. How do you find the exit? You have two primary strategies:

1. Depth-First Search (DFS): Pick a path and follow it as deep as you can. If you hit a dead end, backtrack and try a new path from the last junction you were at.
2. Breadth-First Search (BFS): Explore all paths from your current spot one step at a time, radiating outwards layer by layer.

These two traversal algorithms, DFS and BFS, are the absolute foundation of almost every graph problem you will ever encounter.

Problem: Find if Path Exists in Graph (LeetCode Link): You are given a graph and two nodes, source and destination. Return true if a path exists from source to destination, or false otherwise. 💡 HintDoes it matter if you go deep or wide? As long as you explore systematically, you'll find the destination if it's reachable.

Depth-First Search (DFS)

DFS goes as deep as possible down one path before backtracking. It's the more intuitive, "natural" way we often solve mazes. The key to implementing it is a Stack (or recursion, which internally uses a call stack).

Walkthrough: Implementing DFS with a Stack

1. Initialize: Create a visited set and a stack. Push the start_node onto the stack.
2. Loop: While the stack is not empty:
   • Pop a node from the stack.
   • If this node is our destination, we've found a path! Return true.
   • If this node has not been visited:
     • Mark it as visited.
     • Push all its unvisited neighbors onto the stack.
3. No Path: If the loop finishes, it means we never found the destination. Return false.

def dfs(graph, start_node, end_node):
    visited = set()
    stack = [start_node]
    while stack:
        node = stack.pop()
        if node == end_node:
            return True
        if node not in visited:
            visited.add(node)
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    stack.append(neighbor)
    return False

public boolean dfs(Map<Integer, List<Integer>> graph, int startNode, int endNode) {
    Set<Integer> visited = new HashSet<>();
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(startNode);
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (node == endNode) return true;
        if (!visited.contains(node)) {
            visited.add(node);
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
    return false;
}

bool dfs(const map<int, vector<int>>& graph, int startNode, int endNode) {
    unordered_set<int> visited;
    stack<int> s;
    s.push(startNode);
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        if (node == endNode) return true;
        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            if (graph.count(node)) {
                for (int neighbor : graph.at(node)) {
                    if (visited.find(neighbor) == visited.end()) {
                        s.push(neighbor);
                    }
                }
            }
        }
    }
    return false;
}

Breadth-First Search (BFS)

BFS explores layer by layer. It finds all nodes at distance 1, then all nodes at distance 2, and so on. This is useful for finding the shortest path. The key to implementing it is a Queue.

Walkthrough: Implementing BFS with a Queue

The implementation is nearly identical to DFS. You just swap the stack for a queue!

1. Initialize: Create a visited set and a queue. Add the start_node to the queue.
2. Loop: While the queue is not empty:
   • Dequeue a node.
   • If this node is our destination, return true.
   • If this node has not been visited:
     • Mark it as visited.
     • Enqueue all its unvisited neighbors.
3. No Path: If the loop finishes, return false.

from collections import deque

def bfs(graph, start_node, end_node):
    visited = set()
    queue = deque([start_node])
    while queue:
        node = queue.popleft()
        if node == end_node:
            return True
        if node not in visited:
            visited.add(node)
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    queue.append(neighbor)
    return False

public boolean bfs(Map<Integer, List<Integer>> graph, int startNode, int endNode) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new ArrayDeque<>();
    queue.add(startNode);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        if (node == endNode) return true;
        if (!visited.contains(node)) {
            visited.add(node);
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                }
            }
        }
    }
    return false;
}

bool bfs(const map<int, vector<int>>& graph, int startNode, int endNode) {
    unordered_set<int> visited;
    queue<int> q;
    q.push(startNode);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        if (node == endNode) return true;
        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            if (graph.count(node)) {
                for (int neighbor : graph.at(node)) {
                    if (visited.find(neighbor) == visited.end()) {
                        q.push(neighbor);
                    }
                }
            }
        }
    }
    return false;
}

When to Use Which?

• Use BFS to find the shortest path in an unweighted graph. Because it explores layer by layer, the first time it reaches the destination, it has done so by the shortest possible path.
• Use DFS if you just need to find a path, or if you need to explore a graph's structure deeply (e.g., for cycle detection or topological sort). It's often simpler to implement recursively.

More Problems & Variations

1. Number of Provinces (LeetCode Link): Given a list of connections between cities, count how many connected components (provinces) there are. 💡 HintUse a main loop that iterates from city 0 to N-1. If a city hasn't been visited yet, increment a counter and start a traversal (DFS or BFS) from that city to find and mark all cities in its component.
2. Clone Graph (LeetCode Link): Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. 💡 HintYou need to traverse the original graph while building the new one. Use a hash map to store a mapping from original nodes to their corresponding new nodes to avoid creating duplicate nodes.
3. Course Schedule (LeetCode Link): A classic cycle detection problem. Can you finish all courses if some have prerequisites? 💡 HintThis is equivalent to asking, "Is there a cycle in this directed graph?" A DFS-based approach is perfect for this. You need to keep track of the nodes in the current recursion path in addition to the globally visited nodes.

Bonus Point: Weighted Shortest Path

BFS is fantastic for unweighted graphs, but what if the edges have weights or costs (e.g., distance, time)? For that, you need more advanced algorithms. Dijkstra's algorithm is the classic solution, which is essentially a BFS where the queue is replaced by a priority queue that always explores the path with the lowest current cost. For even more complex scenarios, like finding a path on a map with a target destination, the A* algorithm improves upon Dijkstra's by using a heuristic to guide its search toward the goal.