VietMX Staff asked 3 years ago
Breadth First Search (BFS) is the traversing method used in graphs. It uses a queue for storing the visited vertices. In this method the emphasize is on the vertices of the graph, one vertex is selected at first then it is visited and marked. The vertices adjacent to the visited vertex are then visited and stored in the queue sequentially. A node is fully explored before visiting any other node in the graph, in other words, it traverses shallowest unexplored nodes first.
The BST algorithm works as follows:
- Start by putting any one of the graph’s vertices at the back of a queue.
- Take the front item of the queue and add it to the visited list.
- Create a list of that vertex’s adjacent nodes. Add the ones which aren’t in the visited list to the back of the queue.
- Keep repeating steps 2 and 3 until the queue is empty.
BST example step-by-step:
We have a graph whose vertices are A, B, C, D, E, F, G. Considering A as starting point. The steps involved in the process are:
- Vertex A is expanded and stored in the queue.
- Vertices B, D and G successors of A, are expanded and stored in the queue meanwhile Vertex A removed.
- Now B at the front end of the queue is removed along with storing its successor vertices E and F.
- Vertex D is at the front end of the queue is removed, and its connected node F is already visited.
- Vertex G is removed from the queue, and it has successor E which is already visited.
- Now E and F are removed from the queue, and its successor vertex C is traversed and stored in the queue.
- At last C is also removed and the queue is empty which means we are done.
- The generated Output is – A, B, D, G, E, F, C.
