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

BFS with Adjacency Matrix

Implementing BFS using adjacency matrix representation: scanning rows for edges and handling dense graphs.

BFS with Adjacency Matrix

What you'll learn: How to implement Breadth-First Search when your graph is stored as an adjacency matrix, and why it behaves differently than with adjacency lists.

The Core Idea

When using an adjacency matrix, your graph is represented as a 2D array where matrix[i][j] indicates whether there's an edge from vertex i to vertex j (typically 1 for yes, 0 for no, or the edge weight). To perform BFS with this representation, you must scan entire rows to find neighbors instead of directly accessing a neighbor list.

How It Works

The BFS algorithm stays the same conceptually: use a queue, mark vertices as visited, and explore level by level. The difference is in finding neighbors:

  • With adjacency list: You iterate through a pre-built list of neighbors (fast, proportional to actual edges)
  • With adjacency matrix: You scan the entire row for that vertex, checking each column to see if matrix[vertex][col] != 0

For each vertex you dequeue, you loop through all V vertices (where V is the total number of vertices) to check which ones are connected. This means even if a vertex has only one neighbor, you still check V positions.

Dense Graphs Advantage

Adjacency matrices shine with dense graphs (many edges). When most vertices connect to most others, scanning rows becomes less wasteful since you'll find edges frequently. The matrix's constant-time edge lookup (matrix[i][j]) also helps when you need to repeatedly check specific connections.

Key Takeaway: BFS with adjacency matrix requires scanning full rows (O(V) per vertex), making it less efficient for sparse graphs but reasonable for dense graphs where the O(V²) space is already justified.