With your own example explain breadth first traversal technique, and analyze its complexity

• Tweet
• Email

• Tweet
• Email

Breadth First Search (BFS)

Breadth-first-search is a graph search algorithm that begins at the root node (or arbitrarily selected vertex in graph) and explores all the neighboring nodes. Then for each of those nearest nodes it explores their unexplored neighboring nodes, and so on until it finds the goal.

With BFS technique, any element is searched in graph as following:

Algorithm

Step 1: Enqueue the root node

Step 2: Dequeue a node and examine it:

If the element searched is found in this node, return it and end the search

Else, enqueue all of its adjacent nodes which are not yet explored

Step 3: If the queue is empty then return ‘NOT FOUND’ because all the nodes are already scanned

Step 4: Repeat step 2

Consider a graph as follows and we are searching for element ‘f’ in it.

Let ‘c’ be the starting vertex from where we begin breadth first search. And key=’f’ which we are searching for. Enqueue ‘c’.

Q={c}

Now, let’s begin the search procedure. Dequeue vertex from queue and examine it.

u <– ‘c’

because u ≠ key , enqueue all unexplored adjacent vertices of ‘c’.

Q={b,a,e}

Returning to step 2 again, u <– ‘b’ and because u ≠ key , enqueue all adjacent vertices of ‘b’

Q={a,e,d}

Dequeue an element u <–’a’ and because u ≠ key enqueue all unexplored adjacent vertices of ‘a’. Because all of the adjacent vertices of a are already explored, nothing is enqueued.

Q={e,d}

U<–’e’ and because u ≠ key, enqueue unexplored adjacent vertices of ‘e’.

Q={d,f}

Now, it’s the turn of u<–’d’ and because u ≠ key and there are no unexplored vertices of ‘d’, nothing is added on queue.

Q={f}

When dequeuing we got u<–’f’ and because u = key, we got the element we were looking for. We’ll return this element and end the search here.

Complexity of Breadth First Search

It is obvious that each node is enqueued and, there for dequeued once and only once. Individual queue operations are O(1) and so the total time spent on queue operation os O(n).

The adjacency list for each node taken off the queue is scanned once. Hence the total time spent scanning adjacency list is O(m).

Hence, the total time spent by breadth-first-search is = O(m+n).

---

This was a post in response to Kigozi Ronald from Makerere University, Uganda. I have received a total of 5 questions and two assignments and this is the answer of his second questions. I’ll be answering them graudally.

Please find the answer to his first questions on : Define array. Write a program to store 10 salesmen’s amount in an array and find out total sale & best sales amount.

Apologies to Setimba Ivan as I’m not yet able to respond his/her Multiple Choice Questions. Please allow me some time.

Tagged As: Algorithm, BFS, Breadth-First Search, Complexity of BFS, example