# Graph Traversal BFS and DFS

The two canonical ways to explore a graph: breadth-first expands level by level, depth-first descends as far as possible before backtracking.

**Rests on:** Topological Sort

**Leads to:** Binary Tree Traversal, Dijkstra Shortest Path, GraphRAG, Social Network Analysis

*Mathematical Foundations · Graph Theory*


## Why learn this

Imagine you need to find the fastest route from your home to a new restaurant, or trace how a piece of misinformation spread through your friend group over just three steps. You cannot do this by guessing; you need a reliable method for checking connections one by one. BFS and DFS are those methods: simple, step-by-step procedures that let you explore every possible connection starting from one point without getting lost. Mastering them gives you the ability to navigate any network of relationships, whether it is streets on a map, links between web pages, or colleagues in an organization.


## The intuition

A graph is a collection of points (called vertices or nodes) connected by lines (called edges). Think of a map of cities with roads between them, or a social network where people are connected by friendships. Now, imagine you are standing at one city/node and want to explore everything reachable from it. There are two natural ways to do it.

Breadth-first search (BFS) works like ripples in a pond: you first visit all nodes that are one edge away, then all nodes that are two edges away, and so on. It expands outward, level by level, like checking every shop on the same street before moving to the next street.

For example, if node A is connected to B and C, BFS visits A, then immediately checks its neighbors B and C, then looks at who B knows and who C knows. It treats all nodes at the current


## An analogy

You are in a large house with many rooms connected by doors. You want to explore every room starting from the entrance.

**BFS** is like exploring with a group of friends: you all stand at the entrance, then each of you picks a different door, and you all step into those adjacent rooms together. Then, from each of those rooms, you all send people through the doors into the next layer of rooms, and so on. You never go two doors deep from the entrance until you've seen every room just one door away. This way, if you stop at any moment, you know you've seen all rooms within a certain distance from the start.

**DFS** is like exploring with a single rope tied to the entrance: you walk through a door, then another door, always choosing the first available door you haven't tried, going deeper and deeper. If you hit a room with no new doors, you walk back along the rope to the last room where you had an untried door, and go down that next corridor. You completely exhaust one corridor before trying the next.

**Where the analogy breaks down:** In a real house, you can see the whole room when you enter it, and you know all its doors. In a graph, you only discover a node's neighbours when you actually visit it. Also, in a physical house you can leave markers (string, chalk) to know you've been somewhere; a computer uses a 'visited' list for the same purpose. And while BFS's 'level' is like rooms at the same number of doors from the entrance, in a graph the same node can be reached at multiple distances—BFS records the first (shortest) distance it finds.


## Definition

Graph traversal is the process of systematically visiting every vertex of a graph by following its edges; BFS visits all vertices at distance 1, then 2, then 3, etc., while DFS follows one path to its end before backtracking to try another.


## How it connects

You have not studied any other topics yet, so this page must build from absolute scratch. But know that once you have BFS and DFS, you can move on to topics like: Dijkstra's shortest path (which extends BFS to weighted edges), topological sorting (which uses DFS to order dependencies), PageRank (which can be computed using a form of traversal over the web graph), and social network analysis (which uses BFS to compute degrees of separation). Your library notes also mention that 'every binary relation is a directed graph', so these traversal patterns are the basis for reasoning about any relational data.


## The mathematics

To understand Breadth-First Search (BFS) and Depth-First Search (DFS), we must first define what a graph is in precise terms, because the algorithms depend entirely on how we count connections.

A graph consists of two things: a set of nodes (also called vertices) and a set of edges. Let us call the set of nodes V and the set of edges E. An edge is simply a pair of nodes that are connected. For example, if node A is connected to node B, we write this as the edge {A, B}. In an undirected graph, the connection goes both ways: if you can go from A to B, you can go from B to A.

We also need a precise definition of a 'path'. A path from a starting node s to an ending node t is a sequence of nodes where each adjacent pair in the sequence is connected by an edge. For example, the sequence (s, x, y, t) is a path if there is an edge between s and x, an edge between x and y, and an edge between y and t. The 'length' of this path is the number of edges it uses. In the example above, the length is 3.

The key mathematical difference between BFS and DFS lies in how they define 'distance' and how they manage the list of nodes to visit next.

Breadth-First Search (BFS) explores the graph layer by layer. It finds the shortest path in terms of the number of edges. To do this, it uses a data structure called a queue. A queue is a list where items are added at one end (the back) and removed from the other end (the front). This is 'first-in, first-out'.

Here is the step-by-step logic for BFS starting at node s:
1. Create an empty set called 'visited' to keep track of nodes we have already seen. This prevents us from looping forever.
2. Create a queue Q. Put the starting node s into Q. Mark s as visited.
3. While the queue Q is not empty, do the following:
   a. Remove the first node from the front of Q. Call this node 'current'.
   b. Look at all nodes directly connected to 'current' (its neighbors). Let us call one such neighbor 'next_node'.
   c. For each neighbor 'next_node':
      i. Check if 'next_node' is already in the 'visited' set.
      ii. If it is NOT in 'visited', add 'next_node' to the 'visited' set, and add 'next_node' to the back of the queue Q.

Why does this find the shortest path? Because BFS processes all nodes at distance 1 from s before any node at distance 2. It processes all nodes at distance 2 before any node at distance 3. The first time we encounter a target node, we have reached it via the minimum number of edges.

Depth-First Search (DFS) explores as far as possible along each branch before backtracking. It does not guarantee the shortest path in terms of edge count. To do this, it uses a data structure called a stack. A stack is a list where items are added to the top and removed from the top. This is 'last-in, first-out'.

Here is the step-by-step logic for DFS starting at node s:
1. Create an empty set called 'visited'.
2. Create a stack S. Put the starting node s onto S. Mark s as visited.
3. While the stack S is not empty, do the following:
   a. Remove the top node from S. Call this node 'current'.
   b. Look at all neighbors of 'current'. Let us call one such neighbor 'next_node'.
   c. For each neighbor 'next_node':
      i. Check if 'next_node' is already in the 'visited' set.
      ii. If it is NOT in 'visited', add 'next_node' to the 'visited' set, and push 'next_node' onto the top of stack S.

Note: In practice, DFS is often implemented using recursion (a function calling itself) rather than an explicit stack, but the logic is identical: go deep, then return.

The distinction in order matters. BFS visits nodes in increasing order of their distance from the start. DFS visits nodes by diving into a single path until it hits a dead end (a node with no unvisited neighbors), then backtracking to try other paths.


## A worked example

Let us trace both algorithms on a specific graph.

The Graph:
Nodes: A, B, C, D, E.
Edges: {A, B}, {A, C}, {B, D}, {C, E}.
(Note: The original text mentioned a cycle D to B, but for clarity in this basic traversal example, we will treat the graph as a tree structure where each node is visited exactly once. If there were a cycle, the 'visited' set would simply prevent re-processing.)

Starting Node: A.

Part 1: Breadth-First Search (BFS)
We use a Queue Q and a Visited Set V_set.

Step 1: Initialization.
Q = [A]
V_set = {A}
(We start at A. We mark it as visited immediately so we do not add it again later.)

Step 2: Process the first item in Q.
Remove A from the front of Q. Q is now empty.
Neighbors of A are B and C.
Check B: Is B in V_set? No.
Add B to V_set. Add B to the back of Q.
Q = [B]
V_set = {A, B}
Check C: Is C in V_set? No.
Add C to V_set. Add C to the back of Q.
Q = [B, C]
V_set = {A, B, C}

Step 3: Process the next item in Q (which is B).
Remove B from the front of Q. Q is now [C].
Neighbors of B are A and D.
Check A: Is A in V_set? Yes. Ignore A.
Check D: Is D in V_set? No.
Add D to V_set. Add D to the back of Q.
Q = [C, D]
V_set = {A, B, C, D}

Step 4: Process the next item in Q (which is C).
Remove C from the front of Q. Q is now [D].
Neighbors of C are A and E.
Check A: Is A in V_set? Yes. Ignore A.
Check E: Is E in V_set? No.
Add E to V_set. Add E to the back of Q.
Q = [D, E]
V_set = {A, B, C, D, E}

Step 5: Process the next item in Q (which is D).
Remove D from the front of Q. Q is now [E].
Neighbors of D are B.
Check B: Is B in V_set? Yes. Ignore B.
No new nodes added.
Q = [E]

Step 6: Process the next item in Q (which is E).
Remove E from the front of Q. Q is now empty.
Neighbors of E are C.
Check C: Is C in V_set? Yes. Ignore C.
No new nodes added.
Q = []

The queue is empty. We stop.
The order in which nodes were removed from the queue (visited) is: A, B, C, D, E.
Notice that we visited all neighbors of A (B and C) before visiting any neighbors of B or C.

Part 2: Depth-First Search (DFS)
We use a Stack S and a Visited Set V_set.

Step 1: Initialization.
S = [A] (A is on top)
V_set = {A}

Step 2: Process the top of S.
Pop A from S. S is now empty.
Neighbors of A are B and C.
We must decide which neighbor to push first. Let us assume we process neighbors in alphabetical order, but because it is a stack, the LAST one pushed will be the FIRST one popped.
Push B onto S. S = [B].
Push C onto S. S = [C, B] (C is on top).
V_set = {A, C} (We mark C as visited when we push it to ensure we don't process it twice if we encounter it from another path later, though in this tree structure it doesn't matter yet. Standard DFS marks upon pushing or popping; marking upon pushing is safer for preventing duplicate stack entries).

Step 3: Process the top of S (which is C).
Pop C from S. S = [B].
Neighbors of C are A and E.
Check A: Is A in V_set? Yes. Ignore.
Check E: Is E in V_set? No.
Push E onto S. S = [E, B] (E is on top).
V_set = {A, C, E}

Step 4: Process the top of S (which is E).
Pop E from S. S = [B].
Neighbors of E are C.
Check C: Is C in V_set? Yes. Ignore.
No new nodes added.
S = [B]

Step 5: Process the top of S (which is B).
Pop B from S. S is now empty.
Neighbors of B are A and D.
Check A: Is A in V_set? Yes. Ignore.
Check D: Is D in V_set? No.
Push D onto S. S = [D].
V_set = {A, C, E, B, D}

Step 6: Process the top of S (which is D).
Pop D from S. S is now empty.
Neighbors of D are B.
Check B: Is B in V_set? Yes. Ignore.
No new nodes added.
S = []

The stack is empty. We stop.
The order in which nodes were popped from the stack (visited) is: A, C, E, B, D.
Notice that we went deep down the A-C-E branch before ever visiting B's other neighbor D.

Comparison:
BFS Order: A, B, C, D, E.
DFS Order: A, C, E, B, D.

Both algorithms successfully visited every node in the graph. BFS did so by expanding outward layer by layer. DFS did so by diving deep into one path and backtracking.


## From scratch, in Python

```python
# We need a way to represent a graph. We'll use a dictionary
# where each key is a node and its value is a list of neighbouring nodes.
# This is called an adjacency list.
# Example graph: { 'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': [] }

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}

def bfs(graph, start):
    visited = set()  # a set remembers what we have seen; order doesn't matter
    queue = [start]  # a list used as a queue: append to end, pop from front

    while queue:
        node = queue.pop(0)  # take the first element (FIFO)
        if node not in visited:
            visited.add(node)
            # add all neighbours that haven't been visited yet to the back
            for neighbour in graph[node]:
                if neighbour not in visited:
                    queue.append(neighbour)
    return list(visited)

def dfs(graph, start):
    visited = set()
    stack = [start]  # a list used as a stack: append to end, pop from end

    while stack:
        node = stack.pop()  # take the last element (LIFO)
        if node not in visited:
            visited.add(node)
            # add neighbours to the stack; they will be explored next
            for neighbour in graph[node]:
                if neighbour not in visited:
                    stack.append(neighbour)
    return list(visited)

print("BFS order:", bfs(graph, 'A'))  # ['A', 'C', 'B', 'E', 'D'] (order may vary)
print("DFS order:", dfs(graph, 'A'))  # ['A', 'C', 'E', 'B', 'D'] (order may vary)
```


## The same thing, with a framework

```python
In practice, you will rarely implement BFS or DFS from scratch in production. But if you are working with large graphs, you might use libraries like NetworkX. Here's an example using NetworkX:

    import networkx as nx
    G = nx.Graph()
    G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'E')])
    bfs_order = list(nx.bfs_tree(G, 'A'))
    dfs_order = list(nx.dfs_tree(G, 'A'))
    print(bfs_order)  # ['A', 'B', 'C', 'D', 'E']
    print(dfs_order)  # ['A', 'B', 'D', 'C', 'E'] (depending on ordering)

NetworkX's bfs_tree and dfs_tree return a directed graph representing the traversal tree. Underneath, it uses the same queue/stack logic as our plain Python, just optimised with efficient data structures (like deque for queues) and compiled internals. The important thing is that you understand what it means: BFS returns nodes in increasing distance from the start, DFS returns nodes following a depth-first path.
```


## What the code does

First, we define the graph as a dictionary. A dictionary in Python maps keys to values; here each key is a node and the value is a list of its neighbours. For example, graph['A'] gives ['B', 'C'], meaning A is connected to B and C.

In bfs, we use a list called 'queue'. We start with [start]. The while loop continues as long as the queue is not empty. In each iteration, we take the first element (queue.pop(0))—this enforces FIFO order. We check if it's already visited (a set called 'visited' stores everything we've seen). If not, we add it to 'visited' and then append all its unvisited neighbours to the end of the queue. This way, nodes closer to the start are processed before nodes farther away.

In dfs, we use a stack: stack.pop() takes the last element (LIFO). We start with [start]. In each step, we pop the last element, mark it visited, and push its unvisited neighbours onto the stack. Because we keep pushing deeper neighbours, we go down one branch as far as possible before backtracking (when the stack becomes empty of that branch's neighbours).

The visited set prevents infinite loops when the graph has cycles (like an edge from D back to B). Without it, we would revisit B again and again.

The order of traversal may differ from the theory because we are not strictly adding neighbours in a particular order, but the key properties hold: BFS visits level by level, DFS follows depth first.


## Common misconceptions

**BFS is always faster than DFS** — BFS explores more levels so it must be slower.

Both visit all nodes in the worst case, so they have the same time complexity O(V + E). BFS uses more memory (queue) than DFS (stack) on wide graphs, but speed-wise they are comparable. In fact: The choice depends on what you need: BFS for shortest paths, DFS for memory efficiency (especially on deep graphs) and for tasks like cycle detection or topological sorting.

**DFS always needs a stack** — DFS must be implemented with an explicit stack data structure.

DFS is naturally recursive: the call stack of the programming language itself serves as the stack. Recursive implementations are often shorter and clearer, but can hit depth limits on very deep graphs. In fact: You can implement DFS recursively (without an explicit stack) or iteratively with a stack. Both are correct; the iterative version avoids recursion limits.

**The visited set is optional** — I can skip the visited set if I keep track of where I've been in the queue.

In a graph with cycles, you might push the same node multiple times if you don't check visited before adding to the queue/stack. You need to either check when you dequeue/pop or before adding. In fact: Always maintain a visited set and check it before processing a node. This is essential for correctness on cyclic graphs; otherwise you get infinite loops or repeated work.

**BFS always finds the shortest edge-weighted path** — Since BFS finds shortest unweighted paths, it should also work for weighted graphs.

BFS treats every edge as having equal weight (1). In a graph where some edges are longer (heavier), the path with fewest edges might not be the one with the smallest total weight. In fact: Use Dijkstra's algorithm for weighted graphs with non-negative weights, or Bellman-Ford for negative weights. BFS is only for unweighted graphs (or equal weights).

**DFS order is deterministic** — If I run DFS on the same graph, I'll always get the same traversal order.

The order depends on the order in which you iterate over neighbours. If the adjacency lists are not sorted, the traversal order can change, but the set of visited nodes is always the same. In fact: The traversal order is not unique; it depends on the graph representation and the algorithm's implementation. For reproducibility, sort the adjacency list or use a consistent iteration order.


## In short

BFS explores a graph level by level using a queue, giving shortest paths in unweighted graphs. DFS explores depth-first using a stack (or recursion), which is useful for cycle detection and topological sort. Both require a visited set to avoid infinite loops on cyclic graphs. The choice between BFS and DFS depends on what you need: BFS for shortest paths, DFS for memory efficiency and backtracking.


## Where this is used

You might think graph traversal is only for computer science textbooks, but it is everywhere in modern AI.

**Large language models (LLMs)**: When an LLM generates text, it doesn't literally traverse a graph, but the concept appears in tokenisation and in reasoning processes. Some agents built on LLMs use 'tree-of-thought' prompting, which explores different reasoning paths in a depth-first manner, backtracking when a branch leads to a contradiction. Also, transformer attention can be seen as a graph-like flow of information between tokens, and some interpretability research uses graph traversal to trace how activations spread through the layers.

**Small models running on devices**: When a model runs on a phone or a smart speaker, it often uses a dependency graph of operations (like TensorFlow Lite's ops graph). To execute these operations efficiently, the runtime must traverse the graph in a topological order, which is a DFS-based algorithm (topological sort). Also, on-device speech recognition might use a finite-state transducer (a graph) to decode audio; Viterbi decoding essentially does a best-first traversal (close cousin of BFS) over the state graph.

**Retrieval-augmented generation (RAG)**: RAG retrieves relevant documents to augment an LLM's answer. The retrieval step often uses an approximate nearest neighbour search over a vector database, but the knowledge graph that connects entities and documents is traversed using BFS or DFS to expand a query to related concepts. For example, if you ask about 'Bengaluru', the system might BFS from 'Bengaluru' to reach 'Karnataka', 'IT industry', 'traffic', etc., and use those as additional context.

**Agentic systems that plan and call tools**: An autonomous agent that decides what steps to take (like sending an API call, reading a file, or asking the user) can model its possible actions as a graph of states. BFS is used for breadth-first exhaustive search of possible plans (ensures shortest plan in terms of number of steps), while DFS is used for depth-first exploration that favours longer but possibly more promising paths, common in automated planning. When the agent needs to backtrack from a dead end, it's exactly DFS's backtracking.

**Everyday applied machine learning**: In recommendation systems, a user-item graph is built, and BFS is used to find similar items (like 'users who liked this also liked...') by exploring neighbours. In computer vision, connected-component labelling uses BFS/DFS to identify distinct objects in an image. In fraud detection, a graph of transactions between accounts is traversed to find suspicious patterns (like circular money flows), which is cycle detection using DFS. In speech recognition, the decoder searches over a graph of pronunciations and words, often using a beam search that is a best-first variant of BFS.

**What a developer actually writes**: They might write something like `nx.bfs_tree(G, start)` in Python to traverse a social network, or they might use a C++ library for graph databases. But the logic is always the same: a queue for BFS, a stack for DFS, and a visited set. If they do it badly—forgetting the visited set—the algorithm can loop forever on cyclic graphs. If they choose DFS when they need shortest paths, they'll get wrong answers. The choice between BFS and DFS is often the first decision in many graph problems.


---

Read this on the web: https://basavapurushottam.com/learn-ai/graph-traversal-bfs-and-dfs
