Write the pseudocode for the BreadthFirstSearch algorithm BF

Write the pseudocode for the Breadth-First-Search algorithm, BFS(G), assuming that G is represented using the adjacency-matrix representation. What is the running time of your pseudocode?

Solution

BFS(G):

//Input: Graph G = <V, E>

//Output: Graph G with its vertices marked with consecutive integers in the order they are visited.

c <- 0;

for each vertex v in V:

if v is marked as unvisited i.e., 0,

c <- c + 1;

while the queue is not empty:

for each vertex w in V adjacent to vertex in the front of the queue, do

if w is marked with 0

c <- c + 1;

mark w with count.

add w to the queue.

remove the front vertex from the queue.

And therefore, the running time of the algorithm is: O(|V|²), where V is the number of vertices.