Analysis of Breadth-First Search
(Keep the pseudocode of the algorithm from the previous chapter somewhere handy)
Let 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 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 time, the total time required for queueing all the vertices is . 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 (see handshaking lemma). Hence the time for initialization is and the time for running the algorithm is . Therefore the time complexity of the algorithm can be expressed as .
Space Complexity: Since we are using adjacency lists to represent the graph, the space complexity of the algorithm is .
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 between any two vertices and in a graph is the minimum number of edges between any path from to in the graph. If no path from to exists, then we say that .
Lemma 1: Let be the input graph (it can be either directed or undirected, doesn’t matter) and let be any vertex in . Then for any edge in , it is true that .
Proof: If a path exists from to then, since there is the edge , there is also path from to . Since there is an edge between and , the shortest path between and cannot be longer than one edge more than the shortest path between and . If there is no path between and , then , in which case the inequality obviously holds.
Lemma 2: Let be the input graph (once again, it can be either directed or undirected) and let be any vertex in $latexc G$. Let BFS be run on with as the source. Upon termination, for each vertex in , it is true that .
Proof: Proof by Induction on vertices with the inductive hypothesis being: for all $v \in V$.
Basis Step: When contains only , the inductive hypothesis is true since and for any other vertex , . This completes the basis step.
Inductive Step: Let be a white vertex that is discovered after scanning the adjacency list of a vertex . From line 16, we know that, is set to . From the inductive hypothesis, we know that and hence . Since , this implies that . By lemma 1, we know that and since , it is evident that . This completes the inductive step.
I’ll continue the proof for correctness in the next chapter.
Happy New Year, by the way.