Algorithms / Graph Traversal
Least You Need to Know: BFS, DFS, and Connected Components
**Breadth-first search** explores layer by layer, while **depth-first search** follows one path deeply before backtracking. Both are core graph tools, and both can be used to discover reachability and connected components.
جو کم از کم جاننا ضروری ہے
- BFS explores vertices in increasing distance by number of edges from the start.
- In an unweighted graph, BFS finds shortest paths measured by edge count.
- DFS naturally uses recursion or an explicit stack.
- To count connected components in an undirected graph, start a traversal from each unvisited vertex.
- A queue is the hallmark data structure of BFS.
اہم علامتیں
BFS
breadth-first search
DFS
depth-first search
component
maximal connected piece of an undirected graph
مختصر حل شدہ مثال
- Starting from a source vertex, BFS first visits all neighbors at distance 1.
- Then it visits vertices at distance 2, then distance 3, and so on.
- That is why BFS gives shortest paths in unweighted graphs.
عام غلطیاں
- Students often swap the queue behavior of BFS with the stack behavior of DFS.
- Students often use DFS when the question specifically asks for the fewest edges in an unweighted graph.
- Students often forget to restart traversal when counting components.
اس قسم کے سوال کو کیسے پہچانیں
- If the question says fewest edges in an unweighted graph, think BFS.
- If the question emphasizes recursive exploration or backtracking, DFS is a natural fit.
- If not all vertices are reachable from the first start vertex, components may require repeated restarts.
Next recommended lesson
Continue through this topic with Least You Need to Know: Greedy Choice, Exchange Arguments, and Local Decisions.
Least You Need to Know: Greedy Choice, Exchange Arguments, and Local DecisionsRelated lessons
Keep going with nearby lessons in the same topic.