Linear Algebra BFS

A method of computing a breadth-first search using a sparse adjacency matrix.

Breadth-First Search

This is a way of searching through a graph, starting at one node, and searching all the node's immediate neighbors before moving on to neighbors-of-neighbors.

For example in the graph below, we can start at node 0 and explore all nodes breadth-first:

{0 1} {1 2} {1 3} {2 4} {2 5} {3 5}

By contrast, if we were to explore the same graph in depth-first order (choosing the left branch first), we would get this ordering:

{0 1} {1 2} {2 4} {2 5} {1 3} {3 5}

Adjacency Matrix

One way to represent such a graph is with an adjacency matrix. Each row/column corresponds to a node between parent/child of the graph. This matrix is symmetric about the diagonal, because we're considering an undirected graph.

0 1 0 0 0 0
1 0 1 1 0 0
0 1 0 0 1 1
0 1 0 0 0 1
0 0 1 0 0 0
0 0 1 1 0 0

Directed Graph

If nodes have directional edges between them, we can represent their connections with arrows. This gives rise to parent/child relationships between nodes, and an asymmetric adjacency matrix.