Space-Efficient Implementations of Graph Search Methods
Robert Endre Tarjan · ACM Transactions on Mathematical Software · 1983
Several space-efficmnt implementations of the two most common and useful kinds of graph search, namely, breadth-first search and depth-first search, are discussed.A straightforward implementation of each method requires n bits and n + O(1) pointers of auxiliary storage, where n is the number of vertices in the graph.We devise methods that need only 2n + m bits, of which m are read-only, where rn is the number of edges in the graph.We save space by folding the queue or stack required by the search into the graph representation; two of our methods for depth-first search are variants of the Deutsch-Schorr-Waite list-marking algorithm.Our algorithms are expressed in a version of Dijkstra's guarded command language.