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?

Please explain...

Solution

BFS is a technique in which go through level-by-level.

i.e, each element exists at a certain level in the tree:

a <-- level 0
/ \\
b c <-- level 1

This level-by-level traversal is called a breadth-first traversal .

Algorithm BFS(G) :

Step 1 - Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.

Step 2 - If no adjacent vertex is found, remove the first vertex from the queue.

Step 3 - Repeat Rule 1 and Rule 2 until the queue is empty.

create a queue Q
mark v as visited and put v into Q
while Q is non-empty
   remove the head u of Q
   mark and enqueue all (unvisited)
   neighbours of u
V is number of vertices,
E is number of edges... Then,

Therefore, the total running time is O(V + E)