Graph Traversal: BFS and DFS Notes for GATE DA: Concepts, Formulas, Worked Examples & Practice

Graph Traversal: BFS and DFS notes for GATE DA: 29 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Graph Traversal

What you will master

How directed edges break the symmetry of connectivity.
Using reverse graphs to find strongly connected components.
Classifying edges discovered during Depth First Search.
Accurately tracing traversals on complex visual diagrams.

Reachability in Directed Graph Traversals

Understanding how one-way edges change the fundamental nature of graph exploration.

The Core Shift

In an undirected graph, a traversal from a source vertex naturally discovers its entire connected component. The path can be traversed in both directions.

In a directed graph, edges are one-way streets. A traversal from vertex $v$ only discovers vertices that are reachable from $v$ by following the directed edges. It does not guarantee that those discovered vertices can reach back to $v$ .

Directed Reachability vs Undirected Connectivity

Symmetry vs. Asymmetry

Undirected Connectivity (Symmetric) If there is a path from

v

u

, there is inherently a path from

u

v

. The reachable set from

v

is exactly the connected component containing

v

Directed Reachability (Asymmetric) A directed path from

v

u

does not imply a path from

u

v

We say $u$ is reachable from $v$ .
The set of all such vertices is the forward reachable set from $v$ .
This set can be strictly smaller than the weakly connected component containing $v$ .

The Reverse Graph

Analyzing Backward Reachability

To answer the question "Which vertices can reach $v$ ?", we use the reverse graph, denoted as $G^{R}$ .

G^{R} = (V, E^{R}), where E^{R} = {(u, w) ∣ (w, u) \in E}

Simply flip the direction of every edge.

The Key Property:
A directed path exists from

v

u

G^{R}

if and only if a directed path exists from

u

v

in the original graph

G

Therefore, running a traversal (BFS or DFS) from $v$ in $G^{R}$ yields the exact set of vertices that can reach $v$ in $G$ .

More notes in this unit

chapter

Graph Traversal: BFS and DFS Notes for GATE DA: Concepts, Formulas, Worked Examples & Practice

Graph Traversal: BFS and DFS notes for GATE DA: 29 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free