# How Many Steps Apart? Breadth-First Search

Find how many friendships apart two people are, the fewest, without listing every route or walking in circles: why both of those fail, and the search that fixes them, breadth-first search, with a queue and a visited set.

Journeyman · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Trace breadth-first search level by level, using a queue and a visited set
- Use breadth-first search to find the fewest steps between two vertices

## Key takeaways

- Listing every route explodes (a 30 by 30 grid has about 3 × 10¹⁶ shortest routes corner to corner), and walking from friend to friend without notes loops forever.
- Breadth-first search visits every vertex one step away, then every vertex two steps away, and so on, like ripples in a pond.
- A queue keeps the order fair (first found, first explored), and a visited set stops it from exploring anyone twice.
- The first time breadth-first search reaches a vertex, it has found the fewest steps to it.
- It looks at every vertex and edge once, so it takes O(V + E) time.

**Before this:** *Are These Two Friends? Adjacency Lists and Grids* says in one step whether two people are friends. When they aren't, it can't say how far apart they are.

The social app wants two new lines on a profile: "Fay is 4 steps from you" and, in the "people you may know" box, "a friend of a friend". Both need the same answer: **how many friendships apart are two people, at the fewest?** Here's the chapter's network again, as each person's friends:

| Person | Friends | Person | Friends |
|---|---|---|---|
| Ava | Ben, Cara | Eli | Dev, Fay |
| Ben | Ava, Dev | Fay | Eli |
| Cara | Ava, Dev | Gus | Hana |
| Dev | Ben, Cara, Eli | Hana | Gus |

How many steps from Ava to Fay? Map apps ask the same thing as "the fewest transfers", and games as "the fewest moves to the door".

## What would you try?

**List every route from Ava to Fay, and keep the shortest.** Here there are two: Ava, Ben, Dev, Eli, Fay and Ava, Cara, Dev, Eli, Fay, both 4 steps. But routes multiply fast. In a town laid out as a 30 by 30 grid of blocks, the routes of the *shortest* length alone, from one corner to the opposite one, number about 3 × 10¹⁶. Listing a billion a second, that takes about a year, and the longer routes are more still. Trying every route is exponential.

**Walk from friend to friend until you reach Fay.** Start at Ava, go to her first friend, Ben, then to his first friend: Ava. Then Ben, then Ava, forever. Ava is Ben's friend and Ben is Ava's, so a walk with no notes goes round in circles. It needs a note of **who it has already seen**.

**Work in rounds, on paper.** Round 1: Ava's friends, Ben and Cara, are 1 step away. Round 2: their friends nobody has seen yet, only Dev, are 2 steps away. Round 3: Dev's new friend Eli is 3. Round 4: Eli's new friend Fay is 4. Each person is written down once, with their steps, and nobody is visited twice.

| What we tried | Work for a 30 by 30 grid | Where it breaks |
|---|---|---|
| Every route, keep the shortest | about 3 × 10¹⁶ routes, and more | exponential |
| Walk from friend to friend | never finishes | goes round in circles |
| Rounds, with notes of who's seen | each person once | nowhere so far |

## The questions that lead to it

**Could someone 2 steps away be found before everyone 1 step away?** Not in rounds: round 2 starts only when round 1 is done. That's why the first step count written for a person is the fewest.

**Who do I check next: the one I found first, or the one I found last?** The one found first. Ben and Cara were found in round 1, so they're checked before Dev, who was found in round 2. People wait to be checked in the order they were found: first found, first checked.

**Which structure from Module 2 hands things back in the order they arrived?** The line at the coffee shop, a **queue**. Put each newly found person at the back; take the next person to check from the front. And the "already seen" notes are a set, or a dictionary that also remembers each person's steps.

## How it got its name

This search was so useful that it got a name: **breadth-first search**, or BFS. "Breadth" means width: it goes wide, a whole round at a time, before it goes any deeper. Each round is a **level**.

The picture to keep is a stone dropped in a still pond. The first ripple touches everything close, the next ripple everything a little farther out, and nothing far away is touched before everything near has been.

![The chapter's social network drawn as ripples around Ava: Ava in the center at level 0, Ben and Cara on the first ring at level 1, Dev on the second ring at level 2, Eli on the third at level 3 and Fay on the fourth at level 4, while Gus and Hana sit outside every ring because no friendship connects them to Ava](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/c38a28921ffc4d1ab2dca45f6e983db5.webp)

Here is the search from Ava, one step at a time. "Steps" is how many friendships away from Ava each person is.

| Take from the queue | Their friends | Newly found (steps) | Queue after |
|---|---|---|---|
| (start) | | Ava (0) | Ava |
| Ava | Ben, Cara | Ben (1), Cara (1) | Ben, Cara |
| Ben | Ava, Dev | Dev (2) | Cara, Dev |
| Cara | Ava, Dev | nobody new | Dev |
| Dev | Ben, Cara, Eli | Eli (3) | Eli |
| Eli | Dev, Fay | Fay (4) | Fay |
| Fay | Eli | nobody new | (empty) |

The queue is empty, so the search is done. Gus and Hana were never found: no chain of friendships reaches them from Ava.

## Breadth-first search in code

The network is the one from *Who Knows Whom? When Anything Can Connect: Graphs*, written out as a dictionary. The `steps` dictionary does two jobs: it's the visited set (anyone in it has been seen) and it records how many steps away each person is.

```csharp
Dictionary<string, List<string>> network = new Dictionary<string, List<string>>
{
    ["Ava"] = new List<string> { "Ben", "Cara" },
    ["Ben"] = new List<string> { "Ava", "Dev" },
    ["Cara"] = new List<string> { "Ava", "Dev" },
    ["Dev"] = new List<string> { "Ben", "Cara", "Eli" },
    ["Eli"] = new List<string> { "Dev", "Fay" },
    ["Fay"] = new List<string> { "Eli" },
    ["Gus"] = new List<string> { "Hana" },
    ["Hana"] = new List<string> { "Gus" },
};

Dictionary<string, int> StepsFrom(string start)
{
    Dictionary<string, int> steps = new Dictionary<string, int> { [start] = 0 };
    Queue<string> queue = new Queue<string>();
    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        string person = queue.Dequeue();
        foreach (string friend in network[person])
        {
            if (!steps.ContainsKey(friend))
            {
                steps[friend] = steps[person] + 1;
                queue.Enqueue(friend);
            }
        }
    }
    return steps;
}

Dictionary<string, int> fromAva = StepsFrom("Ava");
List<string> found = new List<string>();
foreach (KeyValuePair<string, int> entry in fromAva)
{
    found.Add(entry.Key + " " + entry.Value);
}
Console.WriteLine("Steps from Ava: " + string.Join(", ", found));
Console.WriteLine("Fewest steps from Ava to Fay: " + fromAva["Fay"]);
Console.WriteLine("Can Ava reach Hana? " + (fromAva.ContainsKey("Hana") ? "yes" : "no"));
```

```text
Steps from Ava: Ava 0, Ben 1, Cara 1, Dev 2, Eli 3, Fay 4
Fewest steps from Ava to Fay: 4
Can Ava reach Hana? no
```

```java
Map<String, List<String>> network = Map.of(
    "Ava", List.of("Ben", "Cara"),
    "Ben", List.of("Ava", "Dev"),
    "Cara", List.of("Ava", "Dev"),
    "Dev", List.of("Ben", "Cara", "Eli"),
    "Eli", List.of("Dev", "Fay"),
    "Fay", List.of("Eli"),
    "Gus", List.of("Hana"),
    "Hana", List.of("Gus"));

Map<String, Integer> stepsFrom(String start) {
    Map<String, Integer> steps = new LinkedHashMap<>();
    steps.put(start, 0);
    Queue<String> queue = new ArrayDeque<>();
    queue.add(start);
    while (!queue.isEmpty()) {
        String person = queue.remove();
        for (String friend : network.get(person)) {
            if (!steps.containsKey(friend)) {
                steps.put(friend, steps.get(person) + 1);
                queue.add(friend);
            }
        }
    }
    return steps;
}

void main() {
    Map<String, Integer> fromAva = stepsFrom("Ava");
    List<String> found = new ArrayList<>();
    for (Map.Entry<String, Integer> entry : fromAva.entrySet()) {
        found.add(entry.getKey() + " " + entry.getValue());
    }
    IO.println("Steps from Ava: " + String.join(", ", found));
    IO.println("Fewest steps from Ava to Fay: " + fromAva.get("Fay"));
    IO.println("Can Ava reach Hana? " + (fromAva.containsKey("Hana") ? "yes" : "no"));
}
```

```text
Steps from Ava: Ava 0, Ben 1, Cara 1, Dev 2, Eli 3, Fay 4
Fewest steps from Ava to Fay: 4
Can Ava reach Hana? no
```

```python
from collections import deque

network = {
    "Ava": ["Ben", "Cara"],
    "Ben": ["Ava", "Dev"],
    "Cara": ["Ava", "Dev"],
    "Dev": ["Ben", "Cara", "Eli"],
    "Eli": ["Dev", "Fay"],
    "Fay": ["Eli"],
    "Gus": ["Hana"],
    "Hana": ["Gus"],
}


def steps_from(start):
    steps = {start: 0}
    queue = deque([start])
    while queue:
        person = queue.popleft()
        for friend in network[person]:
            if friend not in steps:
                steps[friend] = steps[person] + 1
                queue.append(friend)
    return steps


from_ava = steps_from("Ava")
found = [f"{person} {count}" for person, count in from_ava.items()]
print("Steps from Ava: " + ", ".join(found))
print(f"Fewest steps from Ava to Fay: {from_ava['Fay']}")
print(f"Can Ava reach Hana? {'yes' if 'Hana' in from_ava else 'no'}")
```

```text
Steps from Ava: Ava 0, Ben 1, Cara 1, Dev 2, Eli 3, Fay 4
Fewest steps from Ava to Fay: 4
Can Ava reach Hana? no
```

```javascript
const network = new Map([
  ["Ava", ["Ben", "Cara"]],
  ["Ben", ["Ava", "Dev"]],
  ["Cara", ["Ava", "Dev"]],
  ["Dev", ["Ben", "Cara", "Eli"]],
  ["Eli", ["Dev", "Fay"]],
  ["Fay", ["Eli"]],
  ["Gus", ["Hana"]],
  ["Hana", ["Gus"]],
]);

function stepsFrom(start) {
  const steps = new Map([[start, 0]]);
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const person = queue[head];
    head++;
    for (const friend of network.get(person)) {
      if (!steps.has(friend)) {
        steps.set(friend, steps.get(person) + 1);
        queue.push(friend);
      }
    }
  }
  return steps;
}

const fromAva = stepsFrom("Ava");
const found = [...fromAva].map(([person, count]) => `${person} ${count}`);
console.log(`Steps from Ava: ${found.join(", ")}`);
console.log(`Fewest steps from Ava to Fay: ${fromAva.get("Fay")}`);
console.log(`Can Ava reach Hana? ${fromAva.has("Hana") ? "yes" : "no"}`);
```

```text
Steps from Ava: Ava 0, Ben 1, Cara 1, Dev 2, Eli 3, Fay 4
Fewest steps from Ava to Fay: 4
Can Ava reach Hana? no
```

```typescript
const network = new Map<string, string[]>([
  ["Ava", ["Ben", "Cara"]],
  ["Ben", ["Ava", "Dev"]],
  ["Cara", ["Ava", "Dev"]],
  ["Dev", ["Ben", "Cara", "Eli"]],
  ["Eli", ["Dev", "Fay"]],
  ["Fay", ["Eli"]],
  ["Gus", ["Hana"]],
  ["Hana", ["Gus"]],
]);

function stepsFrom(start: string): Map<string, number> {
  const steps = new Map<string, number>([[start, 0]]);
  const queue: string[] = [start];
  let head = 0;
  while (head < queue.length) {
    const person = queue[head];
    head++;
    for (const friend of network.get(person) ?? []) {
      if (!steps.has(friend)) {
        steps.set(friend, steps.get(person)! + 1);
        queue.push(friend);
      }
    }
  }
  return steps;
}

const fromAva = stepsFrom("Ava");
const found = [...fromAva].map(([person, count]) => `${person} ${count}`);
console.log(`Steps from Ava: ${found.join(", ")}`);
console.log(`Fewest steps from Ava to Fay: ${fromAva.get("Fay")}`);
console.log(`Can Ava reach Hana? ${fromAva.has("Hana") ? "yes" : "no"}`);
```

```text
Steps from Ava: Ava 0, Ben 1, Cara 1, Dev 2, Eli 3, Fay 4
Fewest steps from Ava to Fay: 4
Can Ava reach Hana? no
```

Each language's queue: `Queue<T>` in C#, `ArrayDeque` in Java and `deque` in Python all take from the front in O(1). JavaScript has no built-in queue: an array's `shift()` takes from the front but can move every other item along, so the JavaScript and TypeScript tabs keep a `head` index that walks along the array instead.

**Try it.** Start the search from Gus instead of Ava. It finds only Gus 0 and Hana 1: the search covers exactly the part of the graph the start can reach.

## Why it finds the fewest steps

Breadth-first search finishes every level before it starts the next one. So when it first reaches Fay, at level 4, every route of 1, 2 or 3 steps has already been tried, and none of them got to Fay. The first time BFS reaches a vertex is always by a route with the **fewest edges**. In textbooks that route is a **shortest path** in an unweighted graph.

That makes BFS the answer to every "fewest steps" question: degrees of separation, the fewest transfers on a subway, the fewest moves in a puzzle. And on the 30 by 30 grid, it checks each of the 900 blocks once, instead of 3 × 10¹⁶ routes.

## When you don't need it

For "who is exactly two steps away?", two loops are enough: each friend's friends. That's what a "people you may know" box often does, and the exercise does it that way. For "can I get there at all?", the next lesson's search works as well. And BFS counts edges, not miles: when edges have weights, the fewest roads isn't always the shortest drive, and *The Fastest Drive, Not the Fewest Roads: Dijkstra's Algorithm* handles that.

## Cost card

| What it does | Big-O | The everyday reason |
|---|---|---|
| Visit every vertex the start can reach | O(V + E) time | Everyone joins the line once, and every friendship is looked at from both ends |
| Remember who's waiting and who's seen | O(V) memory | At most one name per person in the queue and in the visited set |
| Fewest steps to every reachable vertex | Included in the same search | The level a vertex is found on is its number of steps |

## Check yourself

2 questions to try on the lesson page.

## So what

Whenever a question sounds like "how many steps away?", "is there any route at all?" or "who is within two hops?", reach for breadth-first search with a queue and a visited set, and never for a list of every route.

## Key terms

- [Breadth-First Search](https://www.ask-codey.com/glossary/breadth-first-search)
- [Graph](https://www.ask-codey.com/glossary/graph)
- [Vertex](https://www.ask-codey.com/glossary/vertex)
- [Shortest Path](https://www.ask-codey.com/glossary/shortest-path)

## Cheat sheets

- [How Many Steps Apart? Breadth-First Search](https://www.ask-codey.com/cheat-sheets/ds-bfs-cheat-sheet)

## Related

- [Who Knows Whom? When Anything Can Connect: Graphs](https://www.ask-codey.com/lessons/ds-graphs)
- [Are These Two Friends? Adjacency Lists and Grids](https://www.ask-codey.com/lessons/ds-graph-representations)
- [First Come, First Served at Rush Hour: Queues](https://www.ask-codey.com/lessons/ds-queues)

Source: https://www.ask-codey.com/lessons/ds-bfs
