## Breadth-First Search Algorithm in Details: Graph Algorithm

1. Developing the algorithm in Python
2. How to use this algorithm to find the shortest path of any node from the source node.
3. Time complexity

## How the Breadth_first_search algorithm works

A graph has two elements. Vertices and edges.

1. Initialize a set for level with start vertex S as level 1.
2. Explore which other vertex is reachable from the start. Those vertices will be considered as level 2.
3. In this way, vertices will be opened level by level.

## Algorithm in Python

Before we can dive into the algorithm let’s make an adjacency list. That is to make a dictionary where each node will be a key and the nodes that are linked to it will be the values stored in a list.

`'u': ['v', 'x']`
```adj = {
'u': ['v', 'x'],
'x': ['u', 'v', 'y'],
'v': ['u', 'x', 'y'],
'y': ['w'],
'w': ['y', 'z'],
'z': ['w']
}```
```from queue import Queue
visited = {}
level = {}
parent = {}
traversal_output = []
queue = Queue()```
```for node in adj_list.keys():
visited[node] = False
parent[node] = None
level[node] = -1```
```s = "u"
visited[s] = True
level[s] = 0
queue.put(s)```
```while not queue.empty():
u = queue.get()
traversal_output.append(u)
if not visited[v]:
visited[v] = True
parent[v] = u
level[v] = level[u] + 1
queue.put(v)
print(traversal_output)
print(visited)
print(level)
print(parent)```
```['u', 'v', 'x', 'y', 'w', 'z']
{'u': True, 'x': True, 'v': True, 'y': True, 'w': True, 'z': True}
{'u': 0, 'x': 1, 'v': 1, 'y': 2, 'w': 3, 'z': 4}
{'u': None, 'x': 'u', 'v': 'u', 'y': 'v', 'w': 'y', 'z': 'w'}```
```def Breadth_first_search(adj_list):
visited = {}
level = {}
parent = {}
traversal_output = []
queue = Queue()
visited[node] = False
parent[node] = None
level[node] = -1
s = "u"
visited[s] = True
level[s] = 0
queue.put(s)
while not queue.empty():
u = queue.get()
traversal_output.append(u)
if not visited[v]:
visited[v] = True
parent[v] = u
level[v] = level[u] + 1
queue.put(v)
return traversal_output, visited, level, parent```

## Finding the Shortest Distance

This algorithm can be used to find the shortest path from the source to any other node. How?

`traversed, visited, level, parent = Breadth_first_search(adj)`
```v = "w"path = []
while v is not None:
path.append(v)
v = parent[v]
path.reverse()
print(path)```
`['u', 'v', 'y', 'w']`

## Time Complexity

We have only two elements here. Vertices and edges.

## Conclusion

I tried to explain, how the Breadth_first_search algorithm works using visuals, developed the algorithm in Python, How to find the shortest path using the Breadth_first_search algorithm, and the time complexity of this algorithm. I hope it is clear to you now.

#programming #python #algorithm #technology #searchandsort