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
- 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
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:
visitedList.append(adjacent)
queue.append(adjacent)
bfs(visitedNodes, graph, '5') # 5 3 7 2 4 8
References and useful resources
https://medium.com/edureka/breadth-first-search-algorithm-17d2c72f0eaa
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.tutorialspoint.com/data_structures_algorithms/breadth_first_traversal.htm
Have a nice day!!
Top comments (0)