# 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.