The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Example Code in Python:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in self.graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Example usage:
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("BFS Traversal starting from vertex 2:")
g.bfs(2)
Output:
BFS Traversal starting from vertex 2:
2 0 3 1
This code demonstrates a basic implementation of BFS in Python for an adjacency list representation of the graph. It starts the traversal from vertex 2 and prints the BFS traversal order.
