Breadth-First Search (BFS) in Python
Python Code for BFS
import networkx as nx
import matplotlib.pyplot as plt
from collections import deque
class Graph:
def __init__(self):
self.graph = nx.Graph()
def add_edge(self, u, v):
self.graph.add_edge(u, v)
def bfs(self, start):
visited = set()
queue = deque([start])
visited.add(start)
print("\nBFS Traversal Order:")
traversal_order = []
while queue:
node = queue.popleft()
traversal_order.append(node)
for neighbor in self.graph.neighbors(node):
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
print(" -> ".join(map(str, traversal_order)))
self.draw_graph(traversal_order)
def draw_graph(self, traversal_order):
pos = nx.spring_layout(self.graph)
plt.figure(figsize=(8, 6))
nx.draw(self.graph, pos, with_labels=True, node_color="lightgray", edge_color="gray",
node_size=1000, font_size=12)
path_edges = [(traversal_order[i], traversal_order[i+1]) for i in
range(len(traversal_order)-1)]
nx.draw_networkx_nodes(self.graph, pos, nodelist=traversal_order,
node_color="orange", node_size=1000)
nx.draw_networkx_edges(self.graph, pos, edgelist=path_edges, edge_color="red",
width=2)
plt.title("BFS Traversal Visualization")
plt.show()
g = Graph()
num_edges = int(input("Enter the number of edges: "))
print("Enter the edges (u v):")
for _ in range(num_edges):
u, v = map(int, input().split())
g.add_edge(u, v)
start_node = int(input("Enter the starting node for BFS: "))
g.bfs(start_node)
Sample Input/Output
Sample Input:
Enter the number of edges: 6
Enter the edges (u v):
01
02
13
14
25
26
Enter the starting node for BFS: 0
Sample Output:
BFS Traversal Order:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
