Breadth-First Search
Imagine you are organizing a fundraiser where you need a guest speaker who speaks Portuguese, and you want the help of your friends on a social media platform. You want to contact your first-degree friends that are native Portuguese speakers to see if there is any interest in participating in your event. If none of your friends are native Portuguese speakers, you would not mind checking if any of your friend’s friends or a second-degree connection is a native Portuguese speaker, if none are native Portuguese speakers perhaps a 3rd-degree connection? A breadth-first search would be a perfect search to help find the closest degree of connection to you that matches your criteria.
Breadth-first search algorithm traverse trees and graphs, by traversing I mean the algorithm visits each vertex once. Breadth-first search is a recursive algorithm and can be implemented by using data structures like a dictionary and lists. Breath first search will search all closest vertices to the given source on a graph before going further in terms of tiers away from the source vertex.
Unlike trees, graphs can contain cycles or get stuck in a never-ending loop, why is that significant? Because we want to be able to visit every node once. If a graph is cyclical we could keep coming back to the same node. So to prevent us from processing a node more than once, we can use a boolean “visited” array. This will let the program know which vertices have been visited and which have not, this will prevent up from getting stuck in an infinite loop.
The beauty of a breadth-first search is finding the shortest path in terms of edges in the paths. BFS finds the shortest path from a given source vertex to all other vertices. A great way to solve common search problems such as: find the closest degree of a social media contact I have that satisfies my specific condition.
So how efficient is BFS? A BFS search runs in O(V+E), each vertex is visited at most once, and each vertex is enqueued at most once, and each edge is visited at most twice. Vis the number of vertices and E the number of edges
How is this implemented? One way of Thinking about the steps of a breadth-first search:
Each vertex “v” is assigned two values:
A distance in a minimum number of edges from the source vertex to v, and a predecessor of vertex “v” the predecessor's value could be: null, which would indicate no predecessor.
We start the search at the source and assign it a distance of 0. Then we visit all the neighbors and give them a distance of 1, like if those vertices are the first tier of nodes that all get visited before going further from the vertex. Then we visit all the neighbors of vertices of tier 1, that are Two edges away from the source, as long as they have not been visited before, those are tier 2 from the source vertex. We keep going until all vertices reachable from the source vertex have been visited, always visiting all vertices at distance k, from the source before visiting any vertex at distance k+1.
Here is a sample pseudo code:
Pseudo Code:
# create a queue Q# mark v as visited and put v into Q# while Q is non-empty# remove the head u of Q# mark and enqueue all (unvisited) neighbors of u
Code in Python:
graph = {
‘5’ : [‘3’,’7'],
‘3’ : [‘2’, ‘4’],
‘7’ : [‘8’],
‘2’ : [],
‘4’ : [‘8’],
‘8’ : []
}visited = [] # List for visited nodes
queue = [] #Initialize a queuedef bfs(visited, graph, node): #function for BFS
visited.append(node)
queue.append(node) while queue: # Creating loop to visit each node
m = queue.pop(0)
print (m, end = “ “)
for neighbour in graph[m]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)# Driver Code
print(“Following is the Breadth-First Search”)
bfs(visited, graph, ‘5’) # function calling
*Code by Shivali Bhadaniya
Output:
537248The main data structure involved in the Breadth-First Search algorithm is a queue. Whenever we first visit any vertex, we add this to the end of the queue. At the start, we add the source vertex with enqueue (inserts object into queue) because that’s always the first vertex we visit. To decide which vertex to visit next, we choose the vertex that has been in the queue the longest and remove it from the queue. We use the queue’s first in first out property.
A queue is an abstract data structure that follows the First-In-First-Out methodology (data inserted first will be accessed first). It is open on both ends, where one end is always used to insert data (enqueue) and the other is used to remove data (dequeue).
Breath first search (BFS) is an important graph search algorithm that is used to solve many problems. Finding the shortest path being at the core of this important search algorithm.
Resources:
https://favtutor.com/blogs/breadth-first-search-python , Shivali Bhadaniya
https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
https://medium.com/basecs/breaking-down-breadth-first-search-cebe696709d9 Vaidehi Joshi, Apr 10, 2017
https://medium.com/edureka/breadth-first-search-algorithm-17d2c72f0eaa
