GraphsLesson 33Free preview

DSA Graphs Traversal

This lesson is part of DSA · All levels

Summary

Graph search uses breadth-first search (BFS) which browses per level with the help of queues, and depth-first search (DFS) which searches as deep as possible with stacks or recursions. Both require a marker of the nodes that have already been visited so as not to repeat. BFS is suitable for shortest distance on non-weighted graphs, whereas DFS is suitable for cycle detection.

Key points

BFS uses queues and searches per level
DFS uses stacks or recursions and tracks as deep as possible
Visited markers prevent nodes from being visited repeatedly
BFS for shortest distance without weight, DFS for cycle and topological sort

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.