## Breadth First Search use case.

Breadth First search is also called a level order traversal. BFS is an algorithm to traverse the graph level by level. While traversing the algorithm visits all vertices and edges, any node is taken as a root node during traversal starting. For BF search a queue data structure would be used that follows FIFO(First In First Out) principle.

*
Python Knowledge Base: Make coding great again.
- Updated:
2024-09-12 by Andrey BRATUS, Senior Data Analyst.*

## Breadth First Search Python code:

## Breadth First Search code output:

The process organised in such a way that we visit nodes level wise, i e first we complete the top level and then move on to lower levels. The practical example of BFS use case is a chess game engine where we build the game tree from the current position and apply all possible moves to find a win position. Breadth-first search finds a solution node if one exists.

```
import collections
# BFS function
def bfs(graph, root):
visited, queue = set(), collections.deque([root])
visited.add(root)
while queue:
# Dequeue a vertex from queue
vertex = queue.popleft()
print(str(vertex) + " ", end="")
# If not visited, mark it as visited, and
# enqueue it
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
graph = {'0': set(['1', '2']),
'1': set(['0', '3', '4']),
'2': set(['0']),
'3': set(['1']),
'4': set(['2', '3'])}
print("BFS Traversal: ")
bfs(graph, '3')
```

OUT: BFS Traversal:

3 1 0 4 2