breadth first search Algorithm
Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadthward motion, meaning it visits all the vertices at the same level before moving on to the next level. It systematically explores the graph in layers or levels, starting from a source vertex and proceeding outwards towards the neighbors of the source vertex, followed by their neighbors, and so on. BFS is an important algorithm in computer science, with applications in various fields such as artificial intelligence, network routing, social networking, and even biology.
The algorithm starts by initializing a queue with the source vertex and marking it as visited. Then it iterates until the queue is empty. In each iteration, the algorithm dequeues the current vertex, processes it, and enqueues all its unvisited neighbors, marking them as visited. This ensures that BFS visits all vertices at the same level before moving on to a deeper level. The visiting order of the vertices can be used to obtain the shortest path from the source vertex to any other vertex in the graph, provided the graph is unweighted. BFS is guaranteed to find the shortest path in an unweighted graph, unlike other graph traversal algorithms such as Depth-First Search (DFS), which doesn't have this property.
#!/usr/bin/python
""" Author: OMKAR PATHAK """
class Graph:
def __init__(self):
self.vertices = {}
def printGraph(self):
"""prints adjacency list representation of graaph"""
for i in self.vertices.keys():
print(i, " : ", " -> ".join([str(j) for j in self.vertices[i]]))
def addEdge(self, fromVertex, toVertex):
"""adding the edge between two vertices"""
if fromVertex in self.vertices.keys():
self.vertices[fromVertex].append(toVertex)
else:
self.vertices[fromVertex] = [toVertex]
def BFS(self, startVertex):
# initialize set for storing already visited vertices
visited = set()
# create a first in first out queue to store all the vertices for BFS
queue = []
# mark the source node as visited and enqueue it
visited.add(startVertex)
queue.append(startVertex)
while queue:
vertex = queue.pop(0)
# loop through all adjacent vertex and enqueue it if not yet visited
for adjacent_vertex in self.vertices[vertex]:
if adjacent_vertex not in visited:
queue.append(adjacent_vertex)
visited.add(adjacent_vertex)
return visited
if __name__ == "__main__":
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
g.printGraph()
# 0 : 1 -> 2
# 1 : 2
# 2 : 0 -> 3
# 3 : 3
assert sorted(g.BFS(2)) == [0, 1, 2, 3]
