# Algorithms Notes – Chapter 6

Analysis of Breadth-First Search

(Keep the pseudocode of the algorithm from the previous chapter somewhere handy)

Complexity

Let $G = (V, E)$ be the input graph for the algorithm.

Time Complexity: We know that the algorithm never sets the color of a vertex to white after initialization hence the $if$ condition in line 14 ensures that every vertex is enqueued at most once. If a vertex is enqueued at most once then it is dequeued at most once. Since the enqueuing and dequeuing operations take $\mathcal{O}(1)$ time, the total time required for queueing all the vertices is $\mathcal{O}(|V|)$. We also know that the algorithms scan the adjacency list of each vertex only after it is dequeued. Since a vertex is dequeued at most once, every adjacency list is scanned at most once. The same of the lenghts of all the adjacency lists is $\Theta(|E|)$ (see handshaking lemma). Hence the time for initialization is $\mathcal{O}|V|$ and the time for running the algorithm is $\mathcal{O}|E|$. Therefore the time complexity of the algorithm can be expressed as $\mathcal{O}(|V| + |E|)$.

Space Complexity: Since we are using adjacency lists to represent the graph, the space complexity of the algorithm is $\mathcal{O}(|V| + |E|)$.

Correctness

We shall prove the correctness of the Breadth-First Search algorithm by proving that it correctly calculates shortest path distances.

Definition: The shortest-path distance $\delta (u, v)$ between any two vertices $u$ and $v$ in a graph is the minimum number of edges between any path from $u$ to $v$ in the graph. If no path from $u$ to $v$ exists, then we say that $\delta(u, v) = \infty$.

Lemma 1: Let $G = (V, E)$  be the input graph (it can be either directed or undirected, doesn’t matter) and let $s$ be any vertex in $G$. Then for any edge $(u, v)$ in $G$, it is true that $\delta(s, v) \le \delta(s, u) + 1$.

Proof: If a path exists from $s$ to $u$ then, since there is the edge $(u, v)$, there is also path from $s$ to $v$. Since there is an edge between $u$ and $v$, the shortest path between $s$ and $v$ cannot be longer than one edge more than the shortest path between $s$ and $u$. If there is no path between $s$ and $u$, then $\delta(u, v) = \infty$, in which case the inequality obviously holds. $\square$

Obligatory Math Terminology Comic

Lemma 2: Let $G = (V, E)$ be the input graph (once again, it can be either directed or undirected) and let $s$ be any vertex in $latexc G$. Let BFS be run on $G$ with $s$ as the source. Upon termination, for each vertex $v$ in $G$, it is true that $v.d \ge \delta(s, v)$.

Proof: Proof by Induction on vertices with the inductive hypothesis being: $v.d \ge \delta(s, v)$ for all $v \in V$.

Basis Step: When $Q$ contains only $s$, the inductive hypothesis is true since $s.d = 0 = \delta(s, s)$ and for any other vertex $v$, $v.d = \infty \ge \delta(s, v)$. This completes the basis step.

Inductive Step: Let $v$ be a white vertex that is discovered after scanning the adjacency list of a vertex $u$. From line 16, we know that, $v.d$ is set to $u.d + 1$. From the inductive hypothesis, we know that $u.d \ge \delta(s, u)$ and hence $u.d + 1 \ge \delta(s, u) + 1$. Since $v.d = u.d + 1$, this implies that $v.d \ge \delta(s, u) + 1$. By lemma 1, we know that $\delta(s, u) + 1 \ge \delta(s, v)$ and since $v.d \ge \delta(s, u) + 1$, it is evident that $v.d \ge \delta(s, v)$. This completes the inductive step. $\square$

I’ll continue the proof for correctness in the next chapter.

Happy New Year, by the way.

Advertisements