hi guys, on this beautiful day we'll talk about BreadthFirst Search
Definition of BreadthFirst Search Algorithm (BFS)
BreadthFirst 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) 
BreadthFirst Search applications
 Google maps
 Cheney's algorithm
 Search Engines
 Peer to Peer Networking
 FordFulkerson algorithm
BreadthFirst 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.
BreadthFirst Search implementation in python
If you are not familiar with python, I recommend you check this series
# CODE FROM https://favtutor.com/blogs/breadthfirstsearchpython
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://medium.com/edureka/breadthfirstsearchalgorithm17d2c72f0eaa
https://www.quora.com/WhataresomereallifeexamplesofBreadthandDepthFirstSearch
https://www.hackerearth.com/practice/algorithms/graphs/breadthfirstsearch/tutorial/
https://www.tutorialspoint.com/data_structures_algorithms/breadth_first_traversal.htm
Have a nice day!!
Top comments (0)