Algorithms Notes – Chapter 6

shouldnt_be_hard

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.

2017_488427117869557_39280945_n

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s