Breadth First Search (BFS) Algorithm
Tags: algorithms, beginners, codenewbie, computerscience
Published: 2021-07-09 23:09:42

hi guys, on this beautiful day we'll talk about Breadth-First Search

## Definition of Breadth-First Search Algorithm (BFS)

**Breadth-First Search**: is an algorithm that traverses and searches in trees and graphs using recursion and [queue](https://dev.to/ayabouchiha/queue-data-structure-2hfg) data structure, this algorithm comes to avoid processing a node more than once.

## Time complexity and Space complexity of BFS

| Space complexlity 	| O(V) 	|
|-------------------	|------	|
| **Time complexity**   	| **O(V+E)** 	|

## Breadth-First Search applications

+ Google maps 
+ Cheney's algorithm
+ Search Engines
+ Peer to Peer Networking
+ Ford-Fulkerson algorithm

## Breadth-First Search approach

+ Initialize a queue 

+ Mark the node as visited by inserting it to a list

+ Insert the vertices into the queue

+ While len(queue) > 0:

    + Delete the first item of the queue 

    + mark as visited and push all adjacents unvisited nodes of the deleted Item.

## Breadth-First Search implementation in python

[more details...](https://favtutor.com/blogs/breadth-first-search-python)

If you are not familiar with python, I recommend you check this [series]( https://dev.to/aatmaj/launching-the-learning-python-course-5f31)

```python
# CODE FROM https://favtutor.com/blogs/breadth-first-search-python

graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}

visitedNodes = [] 
queue = []   

def bfs(visitedList: list, graph: dict, node):
    visitedList.append(node)
    queue.append(node)

    while queue:        
        m = queue.pop(0) 
        print (m, end = "\t") 
        for adjacent in graph[m]:
            if adjacent not in visitedList:
                visitedList.append(adjacent)
                queue.append(adjacent)

bfs(visitedNodes, graph, '5') # 5 3 7 2 4 8

```

## References and useful resources

+ [https://www.javatpoint.com/breadth-first-search-algorithm#:~:text=Breadth%20first%20search%20is%20a,until%20it%20finds%20the%20goal.](https://www.javatpoint.com/breadth-first-search-algorithm#:~:text=Breadth%20first%20search%20is%20a,until%20it%20finds%20the%20goal.)

+ [https://www.pythonpool.com/bfs-python/#:~:text=Breadth%2Dfirst%20search%20(BFS)%20in%20python%20is%20an%20algorithm,dictionaries%20and%20lists%20in%20python.](https://www.pythonpool.com/bfs-python/#:~:text=Breadth%2Dfirst%20search%20(BFS)%20in%20python%20is%20an%20algorithm,dictionaries%20and%20lists%20in%20python.)

+ [https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/#:~:text=The%20Time%20complexity%20of%20BFS,and%20E%20stands%20for%20edges.](https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/#:~:text=The%20Time%20complexity%20of%20BFS,and%20E%20stands%20for%20edges.)

+ [https://stackoverflow.com/questions/9844193/what-is-the-time-and-space-complexity-of-a-breadth-first-and-depth-first-tree-tr](https://stackoverflow.com/questions/9844193/what-is-the-time-and-space-complexity-of-a-breadth-first-and-depth-first-tree-tr)

+ [https://medium.com/edureka/breadth-first-search-algorithm-17d2c72f0eaa](https://medium.com/edureka/breadth-first-search-algorithm-17d2c72f0eaa)

+ [https://www.programiz.com/dsa/graph-bfs](https://www.programiz.com/dsa/graph-bfs)

+ [https://www.quora.com/What-are-some-real-life-examples-of-Breadth-and-Depth-First-Search](https://www.quora.com/What-are-some-real-life-examples-of-Breadth-and-Depth-First-Search)

+ [https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/](https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/)

+ [https://www.youtube.com/watch?v=vf-cxgUXcMk](https://www.youtube.com/watch?v=vf-cxgUXcMk)

+ [https://www.javatpoint.com/breadth-first-search-algorithm](https://www.javatpoint.com/breadth-first-search-algorithm)

+ [https://www.tutorialspoint.com/data_structures_algorithms/breadth_first_traversal.htm](https://www.tutorialspoint.com/data_structures_algorithms/breadth_first_traversal.htm)

Have a nice day!!