Theory
Breadth First Search, or BFS, explores a graph level by level. It commonly uses a queue. BFS is useful for finding the shortest path in an unweighted graph and for level-order traversal of trees.
Example
const graph = {
A: ["B", "C"],
B: ["D"],
C: [],
D: []
};
const queue = ["A"];
const visited = new Set();
while (queue.length > 0) {
const node = queue.shift();
if (visited.has(node)) continue;
visited.add(node);
for (const next of graph[node]) {
queue.push(next);
}
}
console.log([...visited]);
Expected Output
The graph nodes are visited level by level.
Practice
Implement BFS for a small graph.
Interview Questions
- What is BFS?
- Which data structure does BFS use?
- Where is BFS useful?
- What is the complexity of BFS?