Reformulating a breadth-first search algorithm on an undirected graph in the language of linear algebra.

Abstract

The formulation of algorithms from sparse linear algebra is often based on suitable concepts from graph theory. However, conversely, the formulation of algorithms from graph theory is rarely based on suitable concepts from sparse linear algebra. Here, we present an illustrating example of a standard graph algorithm that is expressed in the language of sparse linear algebra. More precisely, we reformulate a breadthfirst search (BFS) algorithm on an undirected graph using sparse matrixvector products. In addition, we demonstrate that the performance of this matrixbased BFS algorithm on an Intel Core 2 Duo CPU E8400 is improved as compared to a traditional graphbased BFS algorithm.