I want to derive a proof of running time based on the following pseudo code for BFS using matrix adjacency:
I have written the following lines. Is the proof correct?
Initialization (lines 1-3) generates a list the size equivalent to the number of vertices in the graph and therefore has running time limited by the number of vertices in the graph, i.e., Θ(V). The operations of lines 4 and 5 are executed in constant time, and in line 4, q is initialized as a unitary list containing only the value s, and in line 5, the value of the visited list is changed to TRUE for the index corresponding to the starting vertex s.
The loop of lines 6-11 needs more careful analysis. The visited list generated during initialization corresponds to vertices that have not yet been visited and, once a vertex is visited and as long as its value is equal to 1, it has its value immediately changed to TRUE in the visited list (line 10) and inserted into the list q (line 11).
During the first execution of the loop, q is initialized as a unitary list with only the value s of the list (line 4), and each of the vertices of the adjacency list whose value is equal to 1 has its value in the list q. visited changed to TRUE and is placed in the q list. Thus, the traversal of the graph starts with the vertex s, and then all the vertices of the list of vertices in s are traversed, making a total of |V| comparisons made in this step.
On the second execution of the loop, the first vertex adjacent to s, say u, is taken from the list q (line 7) and all adjacent vertices in the list u, which have not yet been visited and which have a value of 1, will have their values changed to TRUE in the visited list, and inserted in the q list, so that |V| comparisons will be made.
Note that a vertex is only inserted into the list once. Furthermore, for a vertex to be inserted into the list q it must be reachable from s, and, therefore, the process of queuing and dequeuing has cost limited by O(V). Thus, if {s,v₁,v₂,...,vₖ} is the set of all vertices in the graph, then all of them will be inserted in the list q right after being visited and if their value is equal to 1, which has cost O(V).
Then, for each vertex u ∈ {s,v₁,v₂,...,vₖ}, the vertices whose values are equal to 1 and which have not yet been visited are inserted in the visited list, which has a cost O(V). Adding this cost for each of the vertices of the set {s,v₁,v₂,...,vₖ}, we have cost bounded by
Thus, the total cost to traverse the graph is limited by O(V+V²)=O(V²).