Graph Traversal

DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).

Graph Traversal: DFS and BFS

Two fundamentally different strategies for visiting every reachable vertex — one goes deep, one goes wide.

🕳️ DFS vs 🌊 BFS

DFS (Depth First)Go as deep as possible down one path before backtracking — uses a STACK (or recursion) internally.

BFS (Breadth First)Visit all neighbours at the current distance before going further — uses a QUEUE internally, and naturally finds the SHORTEST path in an unweighted graph.

Worked example — DFS and BFS from vertex A on graph: A-B, A-C, B-D, C-D, D-E DFS from A: A → B → D → C (backtrack when D's neighbours exhausted) → E BFS from A: A → B, C (both at distance 1) → D (distance 2) → E (distance 3)

💡 Practice both DFS and BFS traversal orders on the SAME graph starting from the same vertex — seeing how differently they explore the exact same structure really cements the difference.

Choosing between them

The stack-versus-queue distinction is the mechanism. The exam question is usually which one to pick, and that follows from what each guarantees.

🧭 Which traversal, and why

Shortest path, unweightedBFS — it reaches every vertex by the fewest edges, because it exhausts distance 1 before touching distance 2.

Does a path exist?Either. Both visit exactly the reachable set.

Cycle detection, topological sortDFS — its recursion stack is what reveals a back edge to a vertex still being explored.

Deep or infinite graphsBFS — DFS can descend forever down one branch and never return.

Memory is tightDFS — it stores one path, O(depth). BFS stores an entire level, which on a wide graph can be enormous.

The memory contrast is the one most often missed. On a broad, shallow graph BFS may hold a huge frontier while DFS holds only the current path; on a deep, narrow graph the reverse. Both are O(V) worst case, but the typical cost differs sharply with shape.

💡 BFS finds shortest paths only on unweighted graphs — where every edge counts as 1. Add weights and BFS returns the path with the fewest edges, which may be far from the cheapest. That is exactly the gap Dijkstra's algorithm fills.

Why both are O(V + E)

Each vertex is marked visited once, and each edge is examined once from each end. So the total is proportional to vertices plus edges rather than to either alone — assuming an adjacency list, since a matrix forces an O(V) scan per vertex and pushes both to O(V²).

Syllabus points

Depth First Traversal (DFS)
Breadth First Traversal (BFS)

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.