Graph Traversal: BFS and DFS Intuition

Graphs model relationships: courses connected by prerequisites, pages connected by links, cities connected by roads, or students connected to clubs. The challenge is that graphs can contain cycles, so traversal needs a memory of what has already been visited.

Adjacency list representation

Map<String, ArrayList<String>> graph = new HashMap<>();
graph.put("A", new ArrayList<>(List.of("B", "C")));
graph.put("B", new ArrayList<>(List.of("A", "D")));
graph.put("C", new ArrayList<>(List.of("A", "D")));
graph.put("D", new ArrayList<>(List.of("B", "C", "E")));
graph.put("E", new ArrayList<>(List.of("D")));

The key is a node. The value is the list of neighboring nodes. This model makes traversal code much easier to write than a pile of separate variables.

BFS: shortest number of edges

Breadth-first search uses a queue. It reaches all nodes at distance 1 before distance 2, which is why it can compute shortest paths in an unweighted graph.

public static Map<String, Integer> distances(
        Map<String, ArrayList<String>> graph, String start)
{
    Map<String, Integer> dist = new HashMap<>();
    Queue<String> q = new LinkedList<>();

    dist.put(start, 0);
    q.add(start);

    while (!q.isEmpty())
    {
        String current = q.remove();

        for (String next : graph.get(current))
        {
            if (!dist.containsKey(next))
            {
                dist.put(next, dist.get(current) + 1);
                q.add(next);
            }
        }
    }

    return dist;
}

The distance map also acts as the visited set. If a node already has a distance, it has already been discovered.

DFS: path exploration

Depth-first search follows one path deeply before backing up. It is often used for connected components, reachability, and backtracking-style search.

public static boolean hasPath(
        Map<String, ArrayList<String>> graph,
        String current,
        String target,
        Set<String> visited)
{
    if (current.equals(target))
        return true;

    visited.add(current);

    for (String next : graph.get(current))
    {
        if (!visited.contains(next)
                && hasPath(graph, next, target, visited))
            return true;
    }

    return false;
}

Common traps

• Marking a node visited after recursion instead of before recursion.
• Assuming every graph is connected.
• Using DFS for shortest unweighted paths when BFS is the better fit.
• Forgetting that neighbor order can change the traversal order but not the correctness.