Breadth-First Search (BFS)
1. What Is Breadth-First Search? Core idea: expand level by level Breadth-first search (BFS) is the other classic graph traversal algorithm. Starting from a source vertex, it first visits all of its immediate neighbors — these form the first level. Then it visits, in order, all not-yet-visited neighbors of the first-level nodes — these form the second level. The process resembles the ripples spreading out when a stone is dropped into water: it expands outward one level at a time until every reachable node has been visited. Key data structure: the queue BFS makes perfect use of a queue’s first-in, first-out (FIFO) property to guarantee level-by-level traversal order.
Read note →