chapter

Graph Traversal, Connectivity and Directed Graphs Short Notes for GATE CS

Graph Traversal, Connectivity and Directed Graphs short notes for GATE CS: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved pr

graph traversal connectivity and directed graphs short notes

Key Takeaways: BFS Trees

Summary: BFS Tree Core Concepts Shortest Path: Path from root to v in BFS tree T is the shortest path in unweighted G . Undirected Edges: Only Tree and Cross edges exist. Level Constraint: For any cross edge (u, v) in undirected BFS, ∣ l e v e l (u) - l e v e l (v) ∣ \leq 1 . Tree Diameter: Found efficiently using the Two-BFS Trick . Directed Graphs: Back and forward edges can exist; level constraints do not apply to them.

Quick Revision: Edge Types and Timestamps

.smart-card { font-family: system-ui, -apple-system, sans-serif; padding: 24px; border-radius: 12px; background: var(--color-bg); border: 1px solid var(--color-border); color: var(--color-text); } .summary-table { width: 100%; border-collapse: collapse; margin: 16px 0; font-size: 0.85rem; } .summary-table th { text-align: left; padding: 8px; border-bottom: 2px solid var(--color-border); color: var(--color-muted); font-weight: 600; font-size: 0.75rem; text-transform: uppercase; letter-spacing: 0.05em; } .summary-table td { padding: 8px; border-bottom: 1px solid color-mix(in srgb, var(--color-border), transparent 50%); } .summary-table tr:last-child td { border-bottom: none; } .golden-rules { background: color-mix(in srgb, var(--color-primary), transparent 90%); border: 1px solid color-mix(in srgb, var(--color-primary), transparent 80%); border-radius: 8px; padding: 16px; margin-top: 16px; } .golden-rules ol { margin: 0; padding-left: 20px; font-size: 0.9rem; line-height: 1.6; } .golden-rules li { margin-bottom: 6px; } .golden-rules li:last-child { margin-bottom: 0; } Quick Revision: Edge Types and Timestamps Edge Type Ancestor Relation Interval Relation Undirected? Tree u \to v v nested in u Yes Forward u \to v v nested in u No Back v \to u u nested in v Yes Cross None Disjoint (v before u) No Golden Rules Parenthesis Theorem: Intervals are either disjoint or strictly nested. Undirected DFS implies only Tree and Back edges. Cycle exists if and only if a Back edge exists.

Quick Revision: Components and Cut Vertices

.smart-card { font-family: system-ui, -apple-system, sans-serif; padding: 24px; border-radius: 12px; background: var(--color-bg); border: 1px solid var(--color-border); color: var(--color-text); } .summary-table { width: 100%; border-collapse: collapse; margin: 16px 0; font-size: 0.85rem; } .summary-table th { text-align: left; padding: 8px; border-bottom: 2px solid var(--color-border); color: var(--color-muted); font-weight: 600; font-size: 0.75rem; text-transform: uppercase; letter-spacing: 0.05em; } .summary-table td { padding: 8px; border-bottom: 1px solid color-mix(in srgb, var(--color-border), transparent 50%); } .summary-table tr:last-child td { border-bottom: none; } .golden-rules { background: color-mix(in srgb, var(--color-primary), transparent 90%); border: 1px solid color-mix(in srgb, var(--color-primary), transparent 80%); border-radius: 8px; padding: 16px; margin-top: 16px; } .golden-rules ol { margin: 0; padding-left: 20px; font-size: 0.9rem; line-height: 1.6; } .golden-rules li { margin-bottom: 6px; } .golden-rules li:last-child { margin-bottom: 0; } Quick Revision: Components and Cut Vertices Concept Key Formula / Condition Connected Components C = ∣ V ∣ - E_{tree} (in DFS forest) Articulation Point (Root) Has \geq 2 children in DFS tree Articulation Point (Non-Root) \exists child v such that low [v] \geq disc [u] Leaf Node Never an articulation point Back Edge Update low [u] = min (low [u], disc [v]) Tree Edge Update low [u] = min (low [u], low [v]) (after returning) Golden Rule The \geq in the non-root condition is strict. If low [v] = disc [u], v can reach u but nothing above u, so removing u still disconnects the graph.

2 more cards in this chapter

Free preview ends here

Login to view the complete short 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

Graph Traversal, Connectivity and Directed Graphs Short Notes for GATE CS

Graph Traversal, Connectivity and Directed Graphs short notes for GATE CS: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Key Takeaways: BFS Trees

Summary: BFS Tree Core Concepts

Shortest Path: Path from root to $v$ in BFS tree $T$ is the shortest path in unweighted $G$ .
Undirected Edges: Only Tree and Cross edges exist.
Level Constraint: For any cross edge $(u, v)$ in undirected BFS, $∣ l e v e l (u) - l e v e l (v) ∣ \leq 1$ .
Tree Diameter: Found efficiently using the Two-BFS Trick.
Directed Graphs: Back and forward edges can exist; level constraints do not apply to them.

Quick Revision: Edge Types and Timestamps

Edge Type	Ancestor Relation	Interval Relation	Undirected?
Tree	$u \to v$	$v$ nested in $u$	Yes
Forward	$u \to v$	$v$ nested in $u$	No
Back	$v \to u$	$u$ nested in $v$	Yes
Cross	None	Disjoint ( $v$ before $u$ )	No

Golden Rules

Parenthesis Theorem: Intervals are either disjoint or strictly nested.
Undirected DFS implies only Tree and Back edges.
Cycle exists if and only if a Back edge exists.

Quick Revision: Components and Cut Vertices

Concept	Key Formula / Condition
Connected Components	$C = ∣ V ∣ - E_{tree}$ (in DFS forest)
Articulation Point (Root)	Has $\geq 2$ children in DFS tree
Articulation Point (Non-Root)	$\exists$ child $v$ such that $low [v] \geq disc [u]$
Leaf Node	Never an articulation point
Back Edge Update	$low [u] = min (low [u], disc [v])$
Tree Edge Update	$low [u] = min (low [u], low [v])$ (after returning)

Golden Rule

The $\geq$ in the non-root condition is strict. If $low [v] = disc [u]$ , $v$ can reach $u$ but nothing above $u$ , so removing $u$ still disconnects the graph.

Exam Readiness: SCC and Cycle Patterns

Cycle Detection Always look for the "recursion stack" or "3-color" (white, gray, black) method. Gray means currently in recursion stack.

SCC Definition Mutual reachability. If

u

can reach

v

and

v

can reach

u

, they are in the same SCC.

Condensation Graph Always a DAG. The number of SCCs with in-degree zero dictates the minimum number of starting points needed to traverse the entire graph.

Edge Classification in Directed DFS

Tree Edge: to unvisited.
Back Edge: to ancestor in recursion stack (implies cycle).
Forward Edge: to descendant (already fully processed).
Cross Edge: to a different branch (already fully processed).

graph traversal connectivity and directed graphs short notes

Key Takeaways: BFS Trees

Summary: BFS Tree Core Concepts

Quick Revision: Edge Types and Timestamps

Quick Revision: Edge Types and Timestamps

Quick Revision: Components and Cut Vertices

Quick Revision: Components and Cut Vertices

Login to view the complete short notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Graph Traversal, Connectivity and Directed Graphs Short Notes for GATE CS

Key Takeaways: BFS Trees

Summary: BFS Tree Core Concepts

Quick Revision: Edge Types and Timestamps

Quick Revision: Edge Types and Timestamps

Quick Revision: Components and Cut Vertices

Quick Revision: Components and Cut Vertices

Exam Readiness: SCC and Cycle Patterns

Exam Readiness: SCC and Cycle Patterns

More short notes in this unit