Aya Bouchiha

Posted on

# Breadth First Search (BFS) Algorithm

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 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

• 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...

If you are not familiar with python, I recommend you check this series

``````# 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: