Graph BFS

The Puzzle: How Many Introductions Does It Take to Reach Zara?

Aarav wants to get in touch with Zara, but they have never met. Aarav is friends with Bhavya and Chirag. Bhavya is friends with Diya. Chirag is friends with Diya and Esha. Diya is friends with Farhan. Esha is friends with Farhan and Gauri. Farhan and Gauri are both friends with Zara. If Aarav asks a friend to introduce him to a friend of theirs, and so on, what is the fewest number of introductions needed before Aarav is connected to Zara?

You could try to answer this by guessing a path and following it — Aarav to Chirag to Esha to Gauri to Zara, say — and counting four steps. But how do you know that isn't a longer route, with a shorter one hiding somewhere else in the network? Checking one path at a time is unreliable. What you actually need is a systematic way to explore every nearby person before moving further away, so that the moment you reach Zara, you can be certain no shorter route exists. That systematic method is called Breadth-First Search, or BFS, and it is one of the most useful algorithms in all of computer science — it runs, in some form, every time a GPS app finds the shortest route, every time a website suggests "people you may know," and every time a puzzle-solving program figures out the minimum number of moves to reach a goal.

From Ripples in a Pond to a Precise Idea

Here is the intuition before any formal definition. Drop a stone into still water. A ripple spreads outward as a circle. A moment later, a slightly bigger circle has formed around it, then a bigger one still. The water does not skip ahead and touch a distant point before it has touched every nearer point — the disturbance reaches things in order of their distance from the stone.

Breadth-First Search explores a network of connections in exactly this ripple pattern. Starting from one person (or one city, or one webpage — anything that has "neighbours"), it first looks at everyone directly connected to the start. Then, without skipping ahead, it looks at everyone connected to those people who hasn't been seen yet. Then the next ring outward, and the next, until it finds what it's looking for or has visited everyone reachable. Because it finishes an entire ring before starting the next one, the very first time it reaches a particular person, that is guaranteed to be by the shortest possible route — measured in number of connections, or "hops."

What Exactly Is a Graph?

Before writing any algorithm, we need precise vocabulary for "a network of connections." In computer science, this structure is called a graph. A graph has two parts:

• Vertices (also called nodes) — the things being connected. In our example, each person (Aarav, Bhavya, Chirag, Diya, Esha, Farhan, Gauri, Zara) is a vertex.
• Edges — the connections between pairs of vertices. A friendship between Aarav and Bhavya is an edge.

Our friendship graph is undirected, meaning each edge works both ways: if Aarav is Bhavya's friend, Bhavya is also Aarav's friend. (A graph where connections only go one way — like "Account A follows Account B" on a social app, where B does not necessarily follow back — is called a directed graph. BFS works on both, with a small tweak to how edges are read, but we will stay with the simpler undirected case here.)

To actually run an algorithm on a graph, we need to store it in a form a computer can process. The most common and efficient method is an adjacency list: a table where each vertex is a key, and its value is the list of vertices it is directly connected to. For our eight friends, the adjacency list looks like this:

Aarav  -> Bhavya, Chirag
Bhavya -> Aarav, Diya
Chirag -> Aarav, Diya, Esha
Diya   -> Bhavya, Chirag, Farhan
Esha   -> Chirag, Farhan, Gauri
Farhan -> Diya, Esha, Zara
Gauri  -> Esha, Zara
Zara   -> Farhan, Gauri

Notice every edge appears twice in this list — once from each end (Aarav lists Bhavya, and Bhavya lists Aarav) — because the friendship is mutual. This is the standard, memory-efficient way to represent a graph; the alternative, an adjacency matrix (a giant grid marking which pairs are connected), wastes space when most people are not directly connected to most others, which is true of almost every real network.

Here is the same graph as a picture, with the eight friends arranged by how far they turn out to be from Aarav — you will see exactly why they land in these columns once we trace the algorithm in the next section.

The Two Tools BFS Needs: a Queue and a Visited Set

To turn the "ripple" intuition into an algorithm a computer can follow exactly, BFS relies on two simple data structures:

• A queue — a waiting line where the first person added is the first one served (First-In-First-Out, or FIFO). This is exactly like a queue at an IRCTC ticket counter: whoever joined first gets served first. The queue holds vertices that have been discovered but not yet "opened up" to check their neighbours.
• A visited set — a record of every vertex we have already discovered, so we never process the same person twice or add them to the queue more than once.

The algorithm, in plain words, is:

1. Put the starting vertex in the queue and mark it visited.
2. While the queue is not empty: remove the vertex at the front of the queue (this is the one we now "process"), and look at each of its neighbours.
3. For every neighbour that has not already been marked visited: mark it visited immediately, and add it to the back of the queue.
4. Repeat until the queue is empty (or until you find the specific vertex you were searching for).

The queue's FIFO behaviour is precisely what produces the ripple effect: because vertices are processed in the same order they were discovered, an entire ring finishes being explored before the next ring even starts being added to the line.

Worked Example: Tracing BFS on Aarav's Network, Step by Step

Let's run this by hand on our eight-person graph, starting from Aarav, and watch the queue and the visited set change at every step.

Read the "newly discovered" column from top to bottom and you get the exact ripple pattern from the diagram: Aarav discovers {Bhavya, Chirag} at distance 1, those two discover {Diya, Esha} at distance 2, those two discover {Farhan, Gauri} at distance 3, and those two both discover Zara at distance 4 — and because two different people (Farhan and Gauri) both reach Zara in the same step, Zara can only be added once, the first time it is found, since it gets marked visited immediately.

This directly answers our opening puzzle: Zara is at distance 4 from Aarav, meaning the shortest possible chain needs exactly four introductions. There are actually two shortest chains of equal length — Aarav→Bhavya→Diya→Farhan→Zara and Aarav→Chirag→Esha→Gauri→Zara — and BFS as described only reports one of them (whichever gets processed first), though it correctly tells you the shortest possible length either way.

Writing BFS in Python

Now let's turn the trace above into working code. We store the graph as a dictionary of lists (the adjacency list), use collections.deque for an efficient queue (a plain Python list would make removing from the front slow, since every remaining element would have to shift over), and a set for visited vertices.

from collections import deque

graph = {
    "Aarav":  ["Bhavya", "Chirag"],
    "Bhavya": ["Aarav", "Diya"],
    "Chirag": ["Aarav", "Diya", "Esha"],
    "Diya":   ["Bhavya", "Chirag", "Farhan"],
    "Esha":   ["Chirag", "Farhan", "Gauri"],
    "Farhan": ["Diya", "Esha", "Zara"],
    "Gauri":  ["Esha", "Zara"],
    "Zara":   ["Farhan", "Gauri"],
}

def bfs_levels(graph, start):
    visited = {start}
    distance = {start: 0}
    order = []
    queue = deque([start])

    while queue:
        current = queue.popleft()
        order.append(current)
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[current] + 1
                queue.append(neighbor)

    return order, distance

order, distance = bfs_levels(graph, "Aarav")
print(order)
print(distance)

Running this produces:

['Aarav', 'Bhavya', 'Chirag', 'Diya', 'Esha', 'Farhan', 'Gauri', 'Zara']
{'Aarav': 0, 'Bhavya': 1, 'Chirag': 1, 'Diya': 2, 'Esha': 2, 'Farhan': 3, 'Gauri': 3, 'Zara': 4}

Check this against the trace table: the order list is exactly the "vertex removed" column read top to bottom, and every value in distance matches the level/column each person sits in on the diagram. distance["Zara"] equals 4, confirming our hand count.

Knowing the shortest distance is useful, but often you also want the actual shortest path — the sequence of names, not just the count. This needs one more piece of bookkeeping: a parent dictionary that remembers, for each newly discovered vertex, which vertex discovered it. Once the search reaches the goal, you walk backwards through parent to rebuild the path, then reverse it.

def bfs_shortest_path(graph, start, goal):
    visited = {start}
    parent = {start: None}
    queue = deque([start])

    while queue:
        current = queue.popleft()
        if current == goal:
            break
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = current
                queue.append(neighbor)

    path = []
    node = goal
    while node is not None:
        path.append(node)
        node = parent[node]
    path.reverse()
    return path

print(bfs_shortest_path(graph, "Aarav", "Zara"))

Tracing this by hand: parent ends up as {Aarav: None, Bhavya: Aarav, Chirag: Aarav, Diya: Bhavya, Esha: Chirag, Farhan: Diya, Gauri: Esha, Zara: Farhan} — notice Diya's parent is Bhavya, not Chirag, because Bhavya was removed from the queue (step 2) and discovered Diya before Chirag got its turn (step 3). Walking backwards from Zara: Zara → Farhan → Diya → Bhavya → Aarav, then reversing gives the printed output ['Aarav', 'Bhavya', 'Diya', 'Farhan', 'Zara'] — four hops, matching the distance we computed earlier.

A Bug That Trips Up Almost Everyone the First Time

Here is a mistake nearly every student makes on their first BFS implementation, and it is worth understanding exactly why it is wrong. Suppose you wrote the neighbour-checking step like this instead:

# INCORRECT version — marks visited too late
while queue:
    current = queue.popleft()
    if current in visited:
        continue
    visited.add(current)
    for neighbor in graph[current]:
        queue.append(neighbor)

This looks reasonable — it checks "have I seen this before?" and marks it visited when processing it. But look at what happens on our graph: both Farhan and Gauri are neighbours of Esha and get added to the queue; separately, Zara gets added to the queue twice — once when Farhan is processed, once when Gauri is processed — because at the moment each of them runs, Zara has not yet been marked visited (marking only happens when a vertex is popped and processed, not when it is discovered and queued). The algorithm still eventually gives the right distance here because we skip duplicates when we finally see them with continue, but on a denser, more interconnected graph — which is exactly what real friend networks and road networks look like — the queue can fill up with a huge number of duplicate, already-doomed entries, wasting time and memory, and in some variants of the algorithm (like the path-reconstruction version) it can silently overwrite a correct shortest parent with a longer one processed later.

The fix is precisely the pattern used in every version above: mark a vertex visited at the moment it is discovered and added to the queue, not when it is later removed and processed. That guarantees each vertex enters the queue exactly once, which is what makes BFS's running time predictable and its very first arrival at any vertex the shortest one.

A second, related misconception is thinking that any systematic way of visiting every vertex — for instance, Depth-First Search (DFS), which dives all the way down one path before backing up to try another — will also find the shortest path, since it eventually visits everyone anyway. This is false. DFS from Aarav might charge down Aarav → Chirag → Diya → Bhavya (a dead-end loop back toward the start) before ever trying Esha, and while it will still eventually reach Zara, the specific path it happens to record first is whatever it stumbled onto by going deep, with no guarantee it's the shortest one. BFS's guarantee comes specifically from processing vertices in strict order of distance from the start — a property DFS does not have, because it commits to going deep before going wide.

How Fast Is BFS?

Using an adjacency list, BFS visits every vertex exactly once (thanks to the visited-on-discovery rule above) and, across the whole run, looks at every edge exactly twice (once from each of its two endpoints). If a graph has V vertices and E edges, the total work is proportional to V + E, written as O(V + E) — linear in the size of the graph. This is about as fast as any algorithm that must look at the whole graph can possibly be; you cannot find a shortest path without at least glancing at the connections that might lead to it.

Compare this to using an adjacency matrix instead of a list: checking "who are Chirag's neighbours" would require scanning an entire row of the matrix — one entry for every other vertex in the graph, most of which are usually not connected to Chirag at all — costing O(V) time per vertex and O(V²) overall. For a social network with a few hundred people this hardly matters, but real networks — UPI's transaction graph, IRCTC's station network, a search engine's web-page links — have millions of vertices, where the difference between V² and V + E is the difference between an answer in milliseconds and an answer that never finishes.

Where BFS Actually Gets Used

The reason this algorithm is worth learning carefully, rather than just memorising, is that "find the shortest number of steps between two things in a network" turns out to be an enormously common question. A maps application modelling road intersections as vertices and road segments as edges uses a close relative of BFS (Dijkstra's algorithm, for when roads have different lengths or travel times) to find your route. A puzzle like the sliding 8-tile puzzle or a Rubik's Cube solver can model every possible arrangement as a vertex and every legal move as an edge, then use BFS to find the minimum number of moves to solve it. Websites that suggest "people you may know" are running something very close to our friendship example — checking who is two hops away in the connection graph rather than directly connected. In every one of these cases, the underlying question is identical to the one we solved for Aarav and Zara: given a starting point and a target, what is the fewest number of steps between them, explored ring by ring so the first arrival is guaranteed shortest?

Check Your Understanding

1. Write out the adjacency list for a graph with vertices P, Q, R, S where P–Q, P–R, Q–S, and R–S are the only edges. Then trace BFS from P by hand, listing the queue's contents after each step, and state the distance from P to each vertex.
2. In the trace table for Aarav's network, Diya's distance is 2 because both Bhavya and Chirag are her neighbours and both sit at distance 1. Explain in your own words why Diya cannot possibly be at distance 1 from Aarav, given the graph shown.
3. A friend writes BFS code but marks each vertex visited only when it is popped from the queue (the incorrect version discussed above), not when it is added. Describe a graph — you can reuse or modify Aarav's network — where this bug causes a vertex to be added to the queue more than once, and explain step by step why it happens.
4. Modify the bfs_shortest_path function so that instead of stopping at one goal vertex, it returns the shortest path from the start to every other reachable vertex. (Hint: you already have everything you need in the parent dictionary once the full queue empties — you don't need the early break.)
5. Explain why Depth-First Search, despite visiting every reachable vertex just like BFS does, cannot be relied on to report the shortest path between two vertices.

Summary

• A graph models a network as vertices (things) connected by edges (relationships); the adjacency list is the standard, memory-efficient way to store one.
• Breadth-First Search explores a graph in rings of increasing distance from a starting vertex — like ripples spreading from a stone dropped in water — using a FIFO queue to decide processing order and a visited set to avoid repeats.
• The critical implementation rule is to mark a vertex visited the moment it is discovered and enqueued, not when it is later processed — skipping this causes duplicate queue entries and, in denser graphs, real correctness and performance problems.
• Because BFS finishes an entire distance-ring before starting the next, the first time it reaches any vertex is guaranteed to be via a shortest path — a guarantee Depth-First Search does not offer, since DFS commits to depth before breadth.
• A parent dictionary recorded during the search lets you reconstruct the actual shortest path, not just its length, by walking backwards from the goal to the start and reversing.
• With an adjacency list, BFS runs in O(V + E) time — linear in the size of the graph — which is what makes it practical for networks with millions of vertices, from road maps to social graphs.

Think About It

Think about this: How would you explain graph bfs to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

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 graph bfs 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 graph bfs to at least 3 other topics you have studied.