A method of computing a breadth-first search using a sparse adjacency matrix.
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}
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 |
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.