Similar to depth first search, it is a searching algorithm that takes a graph in input & searches it. However, the searching approach it follows is to search all the nodes at one level before moving down to the next level. This is unlike DFS, where nodes at the deeper levels are explored first.
Implementing BFS algorithm
BFS explores all nodes at the current depth level before moving deeper, making it a “layered” approach. BFS is great for finding the shortest path in an unweighted graph because it finds nodes level by level.
Algorithm’s Steps
- Create a set called
visitedto store all the nodes which are explored (initially empty). - Create a queue and add the starting node to it.
- Loop over the queue, until it gets empty. In each loop cycle do:
- De-queue the node from queue (remove node from queue).
- Process the node (by default print or do nothing).
- Add the node to visited.
- Put all the node’s neighbors to queue for the successive cycles to process.
- When all the nodes will be explored in graph, queue will eventually get empty and algorithm will return.
from collections import deque
def bfs(graph, start_node):
visited = set()
queue = deque([start_node])
while queue:
node = queue.popleft() # remove from left side of queue
if node not in visited:
visited.add(node)
print(node) # Process the node (e.g., print it)
for neighbor in graph[node]:
queue.append(neighbor) # append to right-side of queue
# test graph:
graph = {
'A': ['B', 'C'], # A node is connected to 'B' adn 'C'
'B': ['D', 'E'], # B is connected to 'D' and 'E'
'C': ['F'], # C is connected to 'F'
'D': [], # D connecteed to nothing
'E': ['F'], # ...
'F': [] # ...
}
bfs(graph, 'A') # test the codeWhat is BFS used for?
- BFS can be used for finding shortest path in graph with no cost/weights. For weighted graphs, A-star algorithm or Dijkstra algorithm are better suited.
- It can be used for searching as its primary puirpose.
- It is better in cases if we know that the thing we are searching for is on the top levels of the graph (and not deeper).
- Can be used for maze game AI, similar to DFS.
For smaller graphs, there is no noticeable difference between DFS vs BFS performance.
Converting our simple maze game from DFS to BFS
I just replaced dfs() to bfs() in maze game code. And it now solves the maze problem using BFS algorithm. The code is written in Pygame library.
import pygame
import time
# Initialize Pygame
pygame.init()
# Constants
SCREEN_WIDTH = 500
SCREEN_HEIGHT = 500
CELL_SIZE = 100
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
RED = (255, 0, 0)
GREEN = (0, 255, 0)
# Set up the display
screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))
pygame.display.set_caption("DFS Maze Solver")
# Maze example
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)
# Convert the maze to a graph representation
def maze_to_graph(maze):
graph = {}
rows, cols = len(maze), len(maze[0])
for i in range(rows):
for j in range(cols):
if maze[i][j] == 0:
graph[(i, j)] = []
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = i + dx, j + dy
if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0:
graph[(i, j)].append((nx, ny))
return graph
def bfs(graph, start):
visited = set()
queue = [start]
path = []
while queue:
vertex = queue.pop(0) # Pop from the front of the queue
if vertex not in visited:
visited.add(vertex)
path.append(vertex)
# Visualization
screen.fill(WHITE)
draw_maze(maze, path)
pygame.display.flip()
time.sleep(0.5) # pause to visualize
queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
return path
# Draw the maze
def draw_maze(maze, path):
rows, cols = len(maze), len(maze[0])
for i in range(rows):
for j in range(cols):
color = WHITE if maze[i][j] == 0 else BLACK
pygame.draw.rect(screen, color, (j * CELL_SIZE, i * CELL_SIZE, CELL_SIZE, CELL_SIZE))
for (x, y) in path:
pygame.draw.rect(screen, RED, (y * CELL_SIZE, x * CELL_SIZE, CELL_SIZE, CELL_SIZE))
pygame.draw.rect(screen, GREEN, (start[1] * CELL_SIZE, start[0] * CELL_SIZE, CELL_SIZE, CELL_SIZE))
pygame.draw.rect(screen, GREEN, (end[1] * CELL_SIZE, end[0] * CELL_SIZE, CELL_SIZE, CELL_SIZE))
# Main function
def main():
graph = maze_to_graph(maze)
bfs(graph, start)
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
screen.fill(WHITE)
draw_maze(maze, [])
pygame.display.flip()
pygame.quit()
if __name__ == "__main__":
main()
Thank you for reading <3