Breadth-First Search (BFS)

Table of Contents +

Say you want to find the fewest hops between two people on a social app. You start from one person. You look at all their direct friends first. Then you look at the friends of those friends, and so on. That spreading-out search is exactly what Breadth-First Search does on a graph. BFS is a way to visit every node in a graph by going level by level, nearest nodes first.

So in this tutorial we will walk through what BFS does, why it needs a queue, and then write it in five languages.

🎯 What BFS Actually Does

A graph is a set of nodes (we call them vertices) joined by connections (we call them edges). BFS starts at one vertex and explores outward in rings.

Here is the simple idea:

  • It starts from a chosen vertex. We call this the start vertex.
  • It visits all the direct neighbors of that vertex first. Neighbors are the nodes connected to it by one edge.
  • Only after finishing that whole ring does it move to the next ring, the neighbors of the neighbors.
  • It never visits the same vertex twice.

Think of dropping a stone in still water. The ripple touches the closest points first. Then it spreads out evenly. BFS spreads through a graph the same way.

Note

Because BFS reaches closer nodes before farther ones, it naturally finds the shortest path in an unweighted graph. Shortest path here means the fewest edges between two vertices.

🧰 Why BFS Needs a Queue

BFS has to remember which nodes to visit next. And it must visit them in the order it found them. The oldest waiting node should come out first. That is a queue.

A queue is a “first in, first out” list. You add to the back and you remove from the front, like a line of people at a ticket counter. The person who joined first gets served first.

BFS also keeps a visited set. A visited set is just a record of which vertices we have already seen. It stops us from adding the same node to the queue twice. Without it, a cycle in the graph would make BFS loop forever.

So BFS uses two helpers together:

  • Queue — holds the nodes waiting to be explored, in arrival order.
  • Visited set — marks nodes already seen so we do not repeat them.

🪜 Steps to Run BFS From a Start Vertex

Let’s lay out the exact steps before we code it. Say we run BFS on this small graph, starting at vertex 0.

0

1

2

3

4

Here is the plan, in order:

  1. Create an empty queue and an empty visited set.
  2. Mark the start vertex as visited and add it to the queue.
  3. While the queue is not empty, remove the front vertex. Call it current.
  4. Print or record current. This is the visit order.
  5. Look at every neighbor of current. For each neighbor that is not visited yet, mark it visited and add it to the back of the queue.
  6. Repeat from step 3 until the queue is empty.

When this finishes, the order we recorded is the BFS order. First the start vertex. Then its ring of neighbors. Then the next ring.

Tip

Mark a vertex as visited the moment you put it in the queue, not when you take it out. If you wait, the same node can get added several times before it is ever processed.

💻 BFS in 5 Languages

We will store the graph as an adjacency list. An adjacency list keeps, for each vertex, a list of the vertices it connects to. Then we run BFS from vertex 0 and print the order we visit the vertices.

bfs.py
from collections import deque


# run BFS from the start vertex and print the visit order
def bfs(graph, start):
    visited = set()        # nodes we have already seen
    queue = deque()        # first in, first out


    visited.add(start)     # mark before adding
    queue.append(start)    # add start to the queue


    while queue:
        current = queue.popleft()   # remove from the front
        print(current, end=" ")     # record the visit


        # add every unvisited neighbor to the back
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    print()


# adjacency list: key = vertex, value = its neighbors
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3, 4],
    3: [1, 2, 4],
    4: [2, 3],
}


bfs(graph, 0)  # start BFS from vertex 0

The output of the above code will be:

0 1 2 3 4

Output

Starting at 0, BFS first prints 0. Then it adds the ring 1 and 2. After that it reaches 3 and 4. So the visit order is 0 1 2 3 4, exactly ring by ring.

⏱️ Time and Space Complexity

Let V be the number of vertices and E be the number of edges.

BFS looks at each vertex once and walks across each edge once. So the work adds up to O(V + E).

Note

The time is O(V + E) because every vertex enters the queue one time and every edge is checked one time while scanning neighbors.

Here is the full picture:

What Cost Why
Time O(V + E) Each vertex is processed once, each edge is scanned once.
Space O(V) The queue and the visited set can each hold up to V vertices.

⚠️ Common Mistakes

A few slips trip up almost everyone the first time:

  • Marking a vertex visited when you remove it from the queue instead of when you add it. The same node then gets queued many times.
  • Forgetting the visited set on a graph with cycles. BFS then loops forever.
  • Using a stack or plain recursion. That gives you depth-first behavior, not level by level. For level order you need a queue.
  • Reading from the back of the queue. A queue must remove from the front, or the order breaks.

🧩 What You’ve Learned

  • ✅ BFS explores a graph level by level, visiting all neighbors of a node before going deeper.
  • ✅ It uses a queue to hold waiting nodes in arrival order and a visited set to avoid repeats.
  • ✅ The steps: mark and enqueue the start, then repeatedly dequeue a node, record it, and enqueue its unvisited neighbors.
  • ✅ On an unweighted graph, BFS naturally finds the shortest path, the fewest edges between two vertices.
  • ✅ BFS runs in O(V + E) time and O(V) space.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Which data structure does BFS use to decide which vertex to visit next?

    Why: BFS uses a queue so vertices are processed in the order they were discovered, which gives the level-by-level traversal.

  2. 2

    Why does BFS keep a visited set?

    Why: The visited set stops BFS from re-adding nodes it has already seen, which would otherwise cause infinite loops on cyclic graphs.

  3. 3

    When should you mark a vertex as visited?

    Why: Marking it when you add it to the queue prevents the same node from being enqueued multiple times before it is processed.

  4. 4

    What is the time complexity of BFS on a graph with V vertices and E edges?

    Why: Each vertex is processed once and each edge is scanned once, so the total work is O(V + E).

Score: 0 / 4

🚀 What’s Next?

Previous Graph Representation Next Depth-First Search (DFS)

Share & Connect

Share on LinkedIn