4
$\begingroup$

I'm trying to figure out how to best represent BFS (Breadth First Search) and DFS (Depth First Search) on a graph, specifically between being represented as an adjacency matrix and an adjacency list. How do I determine which is a better representation? Is time and space complexity a part of it?

I've been going back and forth between these two and am currently at a loss as to which of these would be better for either of the searches, though I am favoring adjacency list for BFS and adjacency matrix for DFS.

$\endgroup$

2 Answers 2

6
$\begingroup$

Maybe not exactly what you are looking for, but there is a really cool and natural way to represent BFS with an adjacency matrix.

Consider a graph $G = (V, E)$ and its adjacency matrix representation $\mathbf{A} \in \mathbb{B}^{n \times n}$ (where $\mathbb{B}$ is the set of booleans and $n = |V|$). Further, let $\mathbf{q} \in \mathbb{B}^n$ represent the frontier vector where initially the $\mathbf{q}(i) = 1$ means vertex $i$ is the source vertex.

Now, note that we can perform matrix-vector/matrix-matrix multiplications over various semirings (which is a generalization of a ring without the additive inverse requirement). For instance, traditionally given three matrices $A, B, C \in \mathbb{R}^{n \times n}$, matrix-matrix multiplication is defined as \begin{align*} C &= A \cdot B \\ C(i, j) &= \sum_{k = 1}^n A(i, k) \cdot B(k, j). \end{align*} However, if $\langle D, \oplus, \otimes, 0 \rangle$ is a semiring (where $D$ is the domain, $\oplus$ is the additive operator, $\otimes$ is the multiplicative operator, and $0$ is the identity additive identity element), then we can generalize this formula to \begin{align*} C &= A \oplus . \otimes B \\ C(i, j) &= \bigoplus_{k = 1}^n A(i, k) \otimes B(k, j). \end{align*} Now going back to our problem formulation. If we use the so-called "lor-land" semiring where $D = \mathbb{B} = \{0, 1\} = \{F, T\}$, $\oplus = \lor$, $\otimes = \land$, and $0 = F$, then the resulting vector of the operation $$\mathbf{q}' = \mathbf{q} \ \lor . \land \ \mathbf{A}$$ has the property that $\mathbf{q}(j) = T \iff$ vertex $j$ was is on the current frontier. So, constructing a new vector $\mathbf{v}$ which corresponds to the index of true values for the current iteration of $\mathbf{q}'$, we get the vector of the levels at which vertex $j$ was found! In particular, we have

  • Let $\mathbf{q}(s) = T$ (index of source vertex $s$ is true)
  • for $level = 1$ to $n - 1$:
    • Set $\mathbf{v}\langle\mathbf{q}\rangle = level$
    • Set $\mathbf{q} = F$ (reset $\mathbf{q}$ vector)
    • Set $\mathbf{q}\langle\overline{\mathbf{v}}\rangle = \mathbf{q} \ \lor . \land \ \mathbf{A}$

Note: The notation $\mathbf{v} \langle \mathbf{q} \rangle$ refers to the mask (in angled brackets). This specifies to only carry out the computation where $\mathbf{q}$ already has values. Similarly, $\mathbf{q}\langle\overline{\mathbf{v}}\rangle$ specifies to only perform this computation where there is not already an entry in $\mathbf{v}$. This makes sense since if a vertex has already been found on the frontier, we do not want to find it again at a later level!

This algorithm gives us the levels at which each vertex is found, but we can also modify the semiring to find the parents of each vertex by setting $D = \mathbb{N} \cup \{\infty\}, \oplus = \min, \otimes = \mathrm{selectFirst}$, and $0 = +\infty$ (where $\mathrm{selectFirst}(x, y) = x$).

The connection between linear algebra and graph algorithms has been realized for a long time. Here is more information on BFS specifically: BFS explanation.

Unfortunately, this construction does not work so well for DFS. But definitely use an adjacency matrix for BFS! For an iterative approach, either an adjacency matrix or an adjacency list would be suitable as the algorithm is quite simple (simply use either a stack for DFS or a queue for BFS as you reach new nodes from the source vertex). However, an adjacency matrix will use more storage but has constant lookup time while an adjacency list uses less storage and has linear lookup time.

$\endgroup$
0
$\begingroup$

It boils down to the computational model of your BFS or DFS, as well as the sparcity of graphs considered. In an adjacency matrix, you need exactly $|V|^2$ space to store the graph $G$, while in an adjacenecy list, you need $|V|+2|E|$ space. Here I have assumed unit space is required to store any entry, which is reasonable, at least in an asymptotic sense. The adjacency list is storage-efficient when the graph is sparse although being complex than an adjacency matrix representaion.

In a sequential RAM model, you would need $O(|V|^2)$ time using an adjacency matrix for both BFS and DFS, while using an adjacency list gives you $(|V|+|E|)$ time complexity. Thus, in this model, the choice is generally obvious depending on the sparsity of the graph.

But if you are using some parallel model such as CREW, then having a vector/matrix would be more computationally efficient than a sequential list. Thus, in parallel architectures such as CUDA (or other GPU-based ones, e.g., GraphBLAST), an adjacency matrix might be preferred (see here). The same has also been pointed out in the previous answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.