Data Structure Breadth First Traversal

DATA STRUCTURE BREADTH FIRST TRAVERSAL DATA STRUCTURE & ALGORITHMS

What is Data Structure Breadth First Search (BFS)?

An algorithm which traverses the graph in a breadthward sequence is known as Breadth First Search or Breadth First Traversal. When dead end occurs, a queue is used to remember and go to the next vertex to start the search.

As the image displays, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D.

What are the rules employed by Data Structure Breadth First Search Algorithm?

BFS employs the following rules.

• Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
• Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
• Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

What are the steps involved in Data Structure Breadth First Search?

The following are the steps:

Step 1 – Initialize the queue.

Step 2 - Start from visiting S (starting node), and mark it as visited.

Step 3 – An unvisited adjacent node is seen from S. Three nodes are available but choose alphabetically A, mark it as visited and enqueue it.

Step 4 - Next, the unvisited adjacent node from S is B. Mark it as visited and enqueue it.

Step 5 - Next, the unvisited adjacent node from S is C. Mark it as visited and enqueue it.

Step 6 - Now, S is left with no unvisited adjacent nodes. So, dequeue and find A.

Step 7 - From A now D is unvisited adjacent node. Mark it as visited and enqueue it.

Now, no unmarked or unvisited nodes are left. But keep on dequeuing to get all the unvisited nodes, as the queue gets emptied, the program gets over.