Breadth-First Search on an Adjacency Matrix

Level-order traversal over a graph represented as a matrix, with shortest-path reconstruction.

Context

An adjacency matrix is a graph representation using a 2D array of size V × V, where V is the number of vertices.

• adjMatrix[i][j] != 0 indicates an edge from vertex i to vertex j
• 0 indicates no edge (for unweighted graphs)

The memory cost is O(V²), which makes adjacency matrices impractical for sparse graphs. However, they are simple, cache-friendly, and efficient for dense graphs.

Unlike tree traversal, graph traversal must account for:

• Cycles
• Multiple paths
• Potential disconnected components

Breadth-First Search (BFS) on a graph guarantees the shortest path in terms of number of edges in an unweighted graph.

Core idea

To perform BFS on an adjacency matrix:

• Maintain a visited[] array to avoid revisiting vertices
• Maintain a prev[] array to reconstruct the shortest path
• Use a queue to process vertices in breadth-first order
• Continue until:
  • The target is found
  • Or the queue becomes empty
• If the queue empties and prev[target] == -1 (and source ≠ target), then the target is unreachable.

Path reconstruction is done by:

• Following prev[] backward from target to source
• Reversing the collected path

Implementation

import java.util.*;

class GraphSearch {

    static List<Integer> bfsOnAdjacencyMatrix(int[][] adjMatrix, int source, int target) {
        var n = adjMatrix.length;
        if (source < 0 || source >= n || target < 0 || target >= n)
            throw new IllegalArgumentException();
        
        var visited = new boolean[n];
        var prev = new int[n];
        Arrays.fill(prev, -1);
        
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(source);
        visited[source] = true;
        
        while (!queue.isEmpty()) {
            var current = queue.poll();
            
            if (current == target) return buildPath(current, prev);
            
            for (var neighbor = 0; neighbor < n; neighbor++) {
                if (!visited[neighbor] && adjMatrix[current][neighbor] != 0) {
                    visited[neighbor] = true;
                    prev[neighbor] = current;
                    queue.add(neighbor);
                }
            }
        }
        
        return List.of();
    }
    
    private static List<Integer> buildPath(int target, int[] prev) {
        List<Integer> out = new ArrayList<>();
        
        for (var at = target; at != -1; at = prev[at]) {
            out.add(at);    
        }
        
        Collections.reverse(out);
        return out;
    }
}