Course contentsShow
← Computer Science
Lesson 696 of 2,87217. Graph Traversal AlgorithmsFree lesson

BFS with Adjacency List

Implementing BFS using adjacency list representation: iterating through neighbors and efficient queue operations.

What You'll Learn

You'll learn how to efficiently implement Breadth-First Search (BFS) using an adjacency list representation, focusing on iterating through neighbors and managing queue operations.

Core Idea

When performing BFS with an adjacency list, you leverage the list's natural structure: each vertex has a collection of its direct neighbors. As you dequeue a vertex from your BFS queue, you iterate through that vertex's adjacency list to find all unvisited neighbors, mark them as visited, and enqueue them for later processing.

Why Adjacency Lists Work Well for BFS

Think of BFS like exploring a social network level-by-level. With an adjacency list, when you visit a person (vertex), you immediately have access to their list of friends (neighbors)—no need to scan through every possible person in the world to see who they know.

The Implementation Pattern

Here's the typical flow:

  1. Start: Mark the starting vertex as visited and enqueue it
  2. Process: While the queue isn't empty:
    • Dequeue a vertex v
    • Iterate through v's adjacency list
    • For each neighbor u in that list:
      • If u is unvisited, mark it visited and enqueue it

Efficiency Advantages

With an adjacency list, you only examine actual edges in the graph. For each vertex, you iterate through exactly its neighbors—no wasted checks. This makes BFS run in O(V + E) time: you visit each vertex once (V) and examine each edge once (E).

Queue operations (enqueue/dequeue) are O(1), so they don't slow you down. The adjacency list gives you instant access to neighbors without searching.

Key Takeaway: BFS with adjacency lists is efficient because you iterate only through actual neighbors, examining each edge exactly once, making it ideal for sparse graphs where most vertices connect to relatively few others.