Learn
Breadth-First Search (BFS)
Breadth-First Search (BFS), also known as level-order traversal, is a graph traversal algorithm that explores vertices level by level. BFS guarantees the shortest path in unweighted graphs.
You start from a source vertex and visit all neighbors before moving to the next level. You use a queue to process vertices in the order they're discovered.
function bfs(graph, n, source):
dist = array of size n, initialized to -1
dist[source] = 0
queue = empty queue
queue.enqueue(source)
while queue is not empty:
u = queue.dequeue()
for each neighbor v of u:
if dist[v] == -1:
dist[v] = dist[u] + 1
queue.enqueue(v)
return dist
Shortest path guarantee: The first time you reach a vertex, you've taken the minimum number of edges.
Mark before enqueueing: If you forget to mark vertices as visited before enqueueing, you'll add the same vertex multiple times.
Applications: You use BFS for shortest path in unweighted graphs, web crawlers, social network friend suggestions, GPS navigation, and network broadcasting.
Time complexity: where is vertices and is edges.