Explore fundamental graph algorithms through interactive visualizations
Level-order traversal algorithm
Recursive traversal algorithm
Shortest path in weighted graphs
Minimum spanning tree
Minimum spanning forest
Visiting node C. Adding its unvisited neighbors D and F to the queue.
BFS(graph, start):
queue = [start]
visited = set([start])
while queue:
node = queue.pop(0)
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
BFS visits each vertex exactly once and examines each edge exactly twice (once from each endpoint in undirected graphs). Therefore, the time complexity is proportional to the sum of vertices and edges.
The space complexity is determined by the maximum size of the queue, which can contain at most \( V-1 \) vertices in the worst case (when all but one vertex are at the same level of the BFS tree).