  Recent work by Elmasry et al. (STACS 2015) and Asano et al. (ISAAC 2014),
reconsidered classical fundamental graph algorithms focusing on improving the
space complexity. We continue this line of work focusing on space. Our first
result is a simple data structure that can maintain any subset $S$ of a
universe of $n$ elements using $n+o(n)$ bits and support in constant time,
apart from the standard insert, delete and membership queries, the operation
{\it findany} that finds and returns any element of the set (or outputs that
the set is empty). Using this we give a BFS implementation that takes $O(m+n)$
time using at most $2n+o(n)$ bits. Later, we further improve the space
requirement of BFS to at most $1.585n + o(n)$ bits. We demonstrate the use of
our data structure by developing another data structure using it that can
represent a sequence of $n$ non-negative integers $x_1, x_2, \ldots x_n$ using
at most $\sum_{i=1}^n x_i + 2n + o(\sum_{i=1}^n x_i+n)$ bits and, in constant
time, determine whether the $i$-th element is $0$ or decrement it otherwise. We
also discuss an algorithm for finding a minimum weight spanning tree of a
weighted undirected graph using at most $n+o(n)$ bits. We also provide an
implementation for DFS that takes $O(m+n)$ time and $O(n \lg(m/n))$ bits. Using
this DFS algorithm and other careful implementations, we can test
biconnectivity, 2-edge connectivity, and determine cut vertices, bridges etc
among others, essentially within the same time and space bounds required for
DFS. These improve the space required for earlier implementations from $\Omega
(n\lg n)$ bits.

Data Structures and Algorithms