Beginner LevelData Structures & Algorithms
What is the difference between BFS and DFS graph traversal?
ā Interview Prompt: Compare Breadth-First Search (BFS) and Depth-First Search (DFS) ā data structures used, space complexity, and use cases.
Both BFS and DFS traverse all reachable vertices in $O(V + E)$ time.
| Property | BFS | DFS |
|---|---|---|
| Data Structure | Queue | Stack (or recursion) |
| Space | $O(W)$ max width | $O(H)$ max height |
| Order | Level-by-level | Deep path first |
| Shortest Path | ā (unweighted) | ā |
| Cycle Detection | ā | ā |
| Topological Sort | ā | ā |
| Connected Components | ā | ā |
When to Use:
ā¢
BFS: Shortest path (unweighted), social network proximity levels, word ladder.
ā¢
DFS: Maze/puzzle solving, topological sort, strongly connected components.
Code Implementation Example
typescript
// BFS ā shortest path in unweighted graph
function bfs(graph: Map<number, number[]>, start: number): Map<number, number> {
const dist = new Map([[start, 0]]);
const queue = [start];
while (queue.length) {
const node = queue.shift()!;
for (const neighbor of graph.get(node) ?? []) {
if (!dist.has(neighbor)) {
dist.set(neighbor, dist.get(node)! + 1);
queue.push(neighbor);
}
}
}
return dist;
}š”BFS computing shortest distances from a source node.
šÆ Interview Key Takeaway
BFS uses a queue and finds shortest paths in unweighted graphs. DFS uses a stack and is ideal for topological sorting and cycle detection.
#DSA#BFS#DFS#Graphs#Traversal#Beginner
Back to all Data Structures & Algorithms Questionsā