What do you understand about the BFS (Breadth First Search) algorithm.

1.	What do you understand about the BFS (Breadth First Search) algorithm.
Answer» BFS or Breadth-First Search is a graph traversal technique. It begins by traversing the graph from the ROOT node and explores all of the nodes in the immediate vicinity. It chooses the closest node and then visits all of the nodes that have yet to be visited. Until it reaches the objective node, the algorithm repeats the same METHOD for each of the closest nodes. The BFS Algorithm is given below: Step 1: Set status = 1 as the first step for all the nodes(ready state). Step 2: Set the status of the initial node A to 2, that is, waiting state. Step 3: Repeat steps 4 and 5 until the queue is not empty. Step 4: Dequeue and PROCESS node N from the queue, setting its status to 3, that is, the processed state. Step 5: Put all of N's NEIGHBOURS in the ready state (status = 1) in the queue and set their status to 2 (waiting state) Step 6: Exit.

Answer»

BFS or Breadth-First Search is a graph traversal technique. It begins by traversing the graph from the ROOT node and explores all of the nodes in the immediate vicinity. It chooses the closest node and then visits all of the nodes that have yet to be visited. Until it reaches the objective node, the algorithm repeats the same METHOD for each of the closest nodes.

The BFS Algorithm is given below:

Step 1: Set status = 1 as the first step for all the nodes(ready state).
Step 2: Set the status of the initial node A to 2, that is, waiting state.
Step 3: Repeat steps 4 and 5 until the queue is not empty.
Step 4: Dequeue and PROCESS node N from the queue, setting its status to 3, that is, the processed state.
Step 5: Put all of N's NEIGHBOURS in the ready state (status = 1) in the queue and set their status to 2 (waiting state)
Step 6: Exit.

Discussion

No Comment Found

Related InterviewSolutions

What do you understand about the DFS (Depth First Search) algorithm.
What do you understand about the BFS (Breadth First Search) algorithm.
Write down a string reversal algorithm. If the given string is "kitiR," for example, the output should be "Ritik".
What do you understand about the Dynamic Programming (DP) Algorithmic Paradigm? List a few problems which can be solved using the same.
Write an algorithm for counting the number of leaf nodes in a binary tree.
Write down an algorithm for adding a node to a linked list sorted in ascending order(maintaining the sorting property).
Describe the Binary Search Algorithm.
Describe the Linear Search Algorithm.
What do you understand by a searching algorithm? List a few types of searching algorithms.
What do you understand about greedy algorithms? List a few examples of greedy algorithms.

What do you understand about the BFS (Breadth First Search) algorithm.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment