An Interest In:
Web News this Week
- April 19, 2024
- April 18, 2024
- April 17, 2024
- April 16, 2024
- April 15, 2024
- April 14, 2024
- April 13, 2024
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
- 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-pythongraph = { '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 = "") 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!!
Original Link: https://dev.to/ayabouchiha/breadth-first-search-bfs-algorithm-1m5c
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To