BFS and DFS: Exploring Graphs Systematically

You are standing at Rajiv Chowk metro station in Delhi. A cousin visiting from Hauz Khas asks you two questions: "Can I even reach you from here without leaving the metro?" and "What's the fewest stations I'll have to pass through?" You could squint at a metro map and trace lines with your finger. But a route-finder app cannot squint — it needs a precise, repeatable procedure that works whether the network has seven stations or seven hundred. That procedure is what this chapter builds, from scratch, using two of the most important ideas in all of computer science: Breadth-First Search (BFS) and Depth-First Search (DFS).

What exactly is a graph?

Strip away the maps and colours, and a metro network is just two things: a set of stations and a set of direct connections between pairs of stations. In computer science we call the stations vertices (or nodes) and the direct connections edges. A collection of vertices joined by edges is called a graph. Since a metro line runs in both directions, we say this is an undirected graph — if station A connects to station B, you can travel A→B or B→A.

You may already know about trees from earlier data-structure chapters — family trees, folder structures, decision trees. A tree is actually a special, "well-behaved" graph: it is connected, and it has no cycles (no way to leave a node and eventually come back to it without retracing your steps). Real networks are rarely that polite. A metro network usually has loops — you can often get from one station to another by two or more different routes. This single fact — that graphs can have cycles while trees cannot — is the reason graph traversal needs a safeguard that tree traversal never bothered with, as you'll see shortly.

To work with a graph in code, the most common representation is the adjacency list: a dictionary where each vertex maps to the list of vertices it is directly connected to. Here is a small seven-station network we'll use as a running example throughout this chapter — think of it as a simplified fragment of the Delhi Metro, with single-letter codes for brevity:

adjacency = {
    'R': ['K', 'S'],   # Rajiv Chowk
    'K': ['R', 'C'],   # Kashmere Gate
    'S': ['R', 'N', 'I'],  # Central Secretariat
    'C': ['K'],        # Chandni Chowk
    'N': ['S', 'H'],   # New Delhi
    'I': ['S', 'H'],   # INA
    'H': ['N', 'I'],   # Hauz Khas
}

Notice this graph has a cycle: N connects to S and H, S connects to I, I connects to H, and H connects back to N. Follow N → S → I → H → N and you're back where you started. This loop (Central Secretariat ↔ New Delhi ↔ Hauz Khas ↔ INA ↔ Central Secretariat) means there are genuinely two different ways to reach Hauz Khas from Central Secretariat — via New Delhi, or via INA. Keep that in mind; it's exactly the situation that makes graph traversal trickier than tree traversal, and it's built into our example on purpose.

Figure 1: Our seven-station network. Red = start (Rajiv Chowk), green = target (Hauz Khas). Notice the four-edge loop S–N–H–I–S: Hauz Khas is reachable from Central Secretariat by two genuinely different routes.

Two disciplined ways to explore

Imagine you're standing at Rajiv Chowk with no map, only able to see which stations are one stop away. There are two fundamentally different, equally systematic strategies for exploring outward until you've seen the whole network:

• Go wide before you go deep. Visit every station one stop away first. Then, only once that's done, visit every station two stops away. Then three stops away, and so on — like ripples spreading outward from a stone dropped in water. This is Breadth-First Search.
• Go deep before you go wide. Pick a direction, follow it as far as it goes, and only turn back (backtrack) when you hit a dead end or a station you've already seen. Like exploring a maze by always taking the first unexplored corridor, and retracing your steps only when you're stuck. This is Depth-First Search.

Both strategies visit every reachable station exactly once — but in a different order, using a different underlying data structure, and, importantly, they behave differently when it comes to finding the shortest route. Let's trace both, precisely, on our example graph.

Breadth-First Search, traced step by step

BFS needs a data structure that always hands you the oldest item you added — first in, first out. This is called a queue, and it behaves exactly like a ticket counter line: the first person to join is the first person served. BFS keeps a queue of "stations discovered but not yet explored," plus a visited set so it never processes the same station twice.

Here is the complete, correct algorithm in Python:

from collections import deque

def bfs(graph, start):
    visited = {start}
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)      # mark visited HERE
                queue.append(neighbour)
    return order

print(bfs(adjacency, 'R'))

Let's trace it by hand, station by station, so you can see exactly why the output comes out the way it does. Read "queue" as the line waiting to be processed, front on the left:

1. Start: visited = {R}, queue = [R].
2. Remove R from the front. Record R. R's neighbours are K and S — neither visited, so mark both visited and add both to the queue. visited = {R,K,S}, queue = [K,S].
3. Remove K. Record K. K's neighbours are R (already visited, skip) and C (new — mark and enqueue). queue = [S,C].
4. Remove S. Record S. S's neighbours are R (skip), N (new), I (new). queue = [C,N,I].
5. Remove C. Record C. C's only neighbour is K (already visited). Nothing new. queue = [N,I].
6. Remove N. Record N. N's neighbours are S (skip) and H (new — mark and enqueue). queue = [I,H].
7. Remove I. Record I. I's neighbours are S (skip) and H — but H is already marked visited, because step 6 marked it the moment it was discovered through N. So I does not add H again. queue = [H].
8. Remove H. Record H. Both of H's neighbours (N, I) are already visited. queue = []. Done.

Final visiting order: R, K, S, C, N, I, H — exactly what the code prints. Group the stations by how many stops from R they took to reach: R is 0 stops away; K and S are 1 stop away; C, N, I are 2 stops away; H is 3 stops away. That grouping into "layers" is not a coincidence — it's the defining property of BFS: it always finds every station at distance d before it finds any station at distance d+1. That is exactly why BFS is the right tool when you want the fewest number of stops: the very first time BFS reaches a station, that is guaranteed to be via a shortest possible route, measured in number of edges.

A subtlety worth getting right (and a real bug to avoid): notice the code marks a station visited the instant it is added to the queue, not when it is later removed and processed. This matters. If instead you waited to mark a station visited until it was dequeued, then in step 6 (processing N), H would be added to the queue but not yet marked visited — and in step 7 (processing I), the code would check "is H visited?", get "no", and add H to the queue a second time. The final set of visited stations would still be correct, but the algorithm would do wasted work, and in more advanced uses of BFS (like reconstructing the exact shortest path by recording who discovered whom) the duplicate entry can quietly corrupt the recorded route. Mark on discovery, not on processing — that's the rule.

Depth-First Search, traced step by step

DFS needs the opposite discipline: always continue from the most recently discovered, not-yet-fully-explored station — last in, first out. This is a stack, and the natural way to get one for free in Python is the function call stack itself, via recursion.

def dfs_recursive(graph, start, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(start)
    order.append(start)
    for neighbour in graph[start]:
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited, order)
    return order

print(dfs_recursive(adjacency, 'R'))

Trace it by following the recursion exactly as Python would, going all the way down before coming back up:

1. Call dfs(R). Mark and record R. Look at R's neighbours [K, S] in order. K is unvisited — dive into dfs(K) before even looking at S.
2. Inside dfs(K): mark and record K. K's neighbours are [R, C]. R is visited, skip. C is unvisited — dive into dfs(C).
3. Inside dfs(C): mark and record C. C's only neighbour, K, is visited. Nothing to do — return, popping back up to dfs(K).
4. Back in dfs(K): no more neighbours left. Return, popping back up to dfs(R).
5. Back in dfs(R): the loop moves to R's second neighbour, S. Unvisited — dive into dfs(S).
6. Inside dfs(S): mark and record S. S's neighbours are [R, N, I]. R visited, skip. N unvisited — dive into dfs(N) before even considering I.
7. Inside dfs(N): mark and record N. N's neighbours are [S, H]. S visited, skip. H unvisited — dive into dfs(H).
8. Inside dfs(H): mark and record H. H's neighbours are [N, I]. N visited, skip. I unvisited — dive into dfs(I).
9. Inside dfs(I): mark and record I. I's neighbours are [S, H] — both already visited. Return.
10. Unwind all the way back through H, N, S — each has no unvisited neighbours left — back to R, which also has nothing left. Done.

Final visiting order: R, K, C, S, N, H, I — matching the code exactly, and strikingly different from BFS's R, K, S, C, N, I, H. Same graph, same starting station, genuinely different order, because the two algorithms make a different choice every time they have more than one unvisited neighbour to pick from: BFS finishes the current layer first; DFS commits to one neighbour and rides it to the end of the line before trying the next.

You can also write DFS without recursion, using an explicit stack — useful when a graph is so deep that recursion could exceed Python's call-stack limit:

def dfs_iterative(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbour in reversed(graph[node]):
            if neighbour not in visited:
                stack.append(neighbour)
    return order

print(dfs_iterative(adjacency, 'R'))

This prints the identical order, R, K, C, S, N, H, I — but only because of the reversed(...). Here's why that's needed, and it's a genuine gotcha students trip over: a stack is last-in-first-out. If you pushed R's neighbours K, S onto the stack in that order, S would land on top and get popped first — giving you the opposite order to the recursive version, since recursion naturally tries the first listed neighbour first. Reversing the neighbour list before pushing corrects for the stack's "flip," so the iterative and recursive versions agree.

One more detail worth noticing in the iterative code: even though it checks if neighbour not in visited before pushing, a station can still end up on the stack twice — watch I in the trace: it gets pushed once while exploring S's neighbours, and again while exploring H's neighbours, before either push has been "finalised" by actually being popped and marked visited. That's precisely why the line if node in visited: continue right after popping is not optional decoration — it's the safety net that quietly discards the second, stale copy of I when it eventually surfaces. Push-time checks reduce duplicates; only a pop-time check guarantees correctness.

Key insight: DFS does not find the shortest route

This is the single most important practical difference between the two algorithms, and our example makes it concrete rather than abstract. Look at the direct connection between Central Secretariat (S) and INA (I) — it's a genuine edge in the graph, one stop apart. BFS discovers I in exactly 2 stops: R → S → I. But trace the DFS spanning structure from the recursion above: I was only reached at the very end, as a neighbour of H, via the discovery path R → S → N → H → I — four edges, double the real shortest distance, even though the one-stop S–I connection exists in the network the whole time.

Why did DFS "miss" the direct route? It didn't miss it — the S–I edge is still there, still usable. DFS simply never needed it for discovery: by the time S's loop got around to checking neighbour I, DFS had already reached I the long way around, through N and H. DFS commits fully to one branch before considering alternatives, so the order in which it first reaches a station has nothing to do with how close that station actually is. If your goal is "fewest stops," DFS can hand you a technically-valid but needlessly long route. This is not a flaw in DFS — it simply isn't what DFS is designed to optimise for.

BFS tree vs. DFS tree: the same graph, two different shapes

Every traversal that visits each station exactly once is quietly building a spanning tree — the set of "discovery edges" (which station first led you to which). Our graph has 7 edges but only needs 6 to connect all 7 stations without a cycle, so exactly one edge gets left out of each traversal's tree. Compare the two trees directly:

Figure 2: Numbers show visiting order. The BFS tree (left) fans out and reaches its deepest station, H, at depth 3. The DFS tree (right) commits to the S branch and reaches its deepest station, I, at depth 4 — one hop deeper than necessary, exactly the "long way round" traced above. The BFS tree leaves out edge I–H; the DFS tree leaves out edge S–I. Each tree uses 6 of the graph's 7 edges — that's the one edge that had to be dropped to break the S–N–H–I cycle.

Why both run in O(V + E) time

Both algorithms do exactly two kinds of work: they visit each vertex once (mark it, record it — never twice, thanks to the visited set), and for every vertex they examine its adjacency list once. Because our graph is undirected, each of the 7 edges appears in two adjacency lists (once at each endpoint) — so the total number of list entries examined across the whole run is 2 × 7 = 14, and the total number of vertices visited is 7. Total work is proportional to 7 + 14 = 21 basic steps — in general, for V vertices and E edges, that's O(V + E): time that grows in direct proportion to the size of the network, not its square.

Contrast this with an adjacency matrix representation — a V×V grid of 0s and 1s marking which pairs of stations connect. For our 7-station graph that's a 7×7 = 49-cell table to potentially scan, even though only 7 real connections exist. Real transit networks are sparse: each station typically connects to only a handful of others, no matter how large the overall network gets. That's exactly the situation where the adjacency list's O(V + E) beats the adjacency matrix's O(V²) — imagine a hypothetical network of 300 stations with roughly 320 connections: an adjacency-list BFS does work proportional to about 300 + 640 ≈ 940 steps, while scanning a full adjacency matrix means checking up to 300 × 300 = 90,000 cells. The gap only widens as networks grow.

Two misconceptions, corrected

Misconception 1: "DFS on a graph is the same as the tree traversals I already learned (preorder, postorder)." Not quite — tree preorder/postorder never needs a visited set, because a tree, by definition, has no cycles: you can never accidentally walk back to a node you've already seen. A graph can. Try running DFS on our network starting from S without ever marking anything visited: S → N → H → I → S → N → H → I → ... forever, looping the four-station cycle endlessly. The visited set isn't a minor implementation detail bolted onto tree traversal — it's the one addition that makes graph traversal terminate at all.

Misconception 2: "There's one 'correct' BFS or DFS order for a given graph." There isn't. Both the starting vertex and the order neighbours are listed in the adjacency list change the output. If C's entry in our dictionary had listed K differently, or if we'd started BFS from H instead of R, the visiting order would change completely, even though the graph itself is identical. What stays fixed is the property each algorithm guarantees — BFS always finds shortest hop-counts first; DFS always fully commits to one branch before backtracking — not any specific sequence of letters.

When to reach for which

• Use BFS when you need the shortest path measured in number of edges (fewest metro changes, fewest hops in a friend network to find "degrees of separation," fewest moves in a sliding puzzle), or when you need to explore a network level-by-level (like finding everyone within 2 "connections" of a person on a social app).
• Use DFS when you need to know if a path exists at all, need to detect a cycle, need to explore every possible configuration systematically (DFS is the engine behind backtracking algorithms used for maze-solving and puzzle-solving), or when you're working with a graph too large to hold many "in-progress" branches in a queue at once.

Check your understanding

1. Run BFS on the seven-station graph starting from C instead of R. Write out the queue at each step, and give the final visiting order.
2. Run DFS (recursive) on the same graph starting from H. Which station is visited last, and why does the order differ from a BFS starting at H?
3. Explain, using our example, why marking a station "visited" at the moment it's discovered rather than the moment it's processed matters for BFS's correctness.
4. Central Secretariat (S) connects directly to INA (I) — one stop. Explain, using the actual traced DFS order from this chapter, why the DFS spanning tree still records I as reachable only via a four-edge path.
5. A new metro line adds a direct edge between Chandni Chowk (C) and Hauz Khas (H). Redraw the adjacency list, then explain whether this changes the BFS shortest distance from R to H, and if so, to what.

Answer key — (1) BFS from C: queue starts [C]; visit C, enqueue K; visit K, enqueue R (C's and K's other neighbours already handled or visited); visit R, enqueue S; visit S, enqueue N and I; visit N, enqueue H; visit I (H already visited via N, skip); visit H. Order: C, K, R, S, N, I, H. (2) DFS from H visits H, then N (H's first listed neighbour), then S, then R, then K, then C, then finally I — last, because I only gets reached after everything else is exhausted and DFS backtracks all the way to H's second neighbour. (3) If visited were marked only when dequeued, H could be added to the queue twice — once via N, once via I — before either copy is processed, wasting a slot and risking incorrect parent-tracking in path-reconstruction code. (4) Because by the time S's loop reaches its third neighbour I, DFS has already dived through N and H and reached I from H's side; the S–I edge exists but isn't needed for first discovery, so it never becomes a tree edge. (5) New adjacency: C gains H as a neighbour, H gains C. Check the new route: R→K→C→H is 3 edges. The old shortest routes, R→S→N→H and R→S→I→H, were also 3 edges each. So the shortest distance from R to H stays 3 — it doesn't improve — but there are now three shortest routes instead of two.

Summary

• A graph generalises a tree by allowing cycles; because of that, every graph traversal needs a visited set to avoid looping forever — something tree traversal never required.
• BFS uses a FIFO queue, explores layer by layer, and is the algorithm to reach for whenever you need the fewest-edges shortest path in an unweighted graph. Mark vertices visited at the moment they're enqueued, not when they're dequeued, or you risk duplicate queue entries.
• DFS uses a LIFO stack (explicit, or implicit via recursion), commits fully to one branch before backtracking, and is the natural engine for existence/connectivity checks, cycle detection, and backtracking search — but it offers no guarantee of finding the shortest route, and can genuinely find a needlessly long one, as our S–I example showed concretely.
• Both algorithms run in O(V + E) time on an adjacency list, because each vertex is visited once and each edge is examined at most twice (once from each end) — far better than an adjacency matrix's O(V²) for the sparse, real-world networks graphs are usually used to model.
• Every traversal quietly builds a spanning tree of discovery edges; BFS and DFS build different spanning trees of the very same graph, leaving out different edges to break the same cycle.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where bfs and dfs: exploring graphs systematically is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting bfs and dfs: exploring graphs systematically to at least 3 other topics you have studied.