PATTERN 14A: Graph Traversal & Properties

D

Qubits of DPK

April 11, 2026

Core DSA

Core Intent

Model relationships, reason about structure, ordering, cycles, and optimization.

EASY: Graph Modeling & Reachability

  1. #
    Graph Representation – Adjacency List — GFG
  2. #
    DFS Traversal of a Graph — GFG
  3. #
    BFS Traversal of a Graph — GFG
  4. #
    Number of Connected Components — LC 323
  5. #
    Find if Path Exists in Graph — LC 1971
  6. #
    Number of Provinces — LC 547
  7. #
    Clone Graph — LC 133
  8. #
    Graph Valid Tree — LC 261
  9. #
    Keys and Rooms — LC 841
  10. #
    Find the Town Judge — LC 997
Now EASY locks:
  • DFS vs BFS intuition
  • Adjacency list usage
  • Visited tracking
  • Undirected graph logic
  • Basic property reasoning

️ MEDIUM: Cycles, Ordering, Graph Properties

Now reasoning starts.
  1. #
    Course Schedule — LC 207
  2. #
    Course Schedule II — LC 210
  3. #
    Topological Sort (DFS) — GFG
  4. #
    Bipartite Graph — LC 785
  5. #
    Alien Dictionary — LC 269
  6. #
    Evaluate Division — LC 399
  7. #
    Find Eventual Safe States — LC 802
  8. #
    Reorder Routes to Make All Paths Lead to City Zero — LC 1466
  9. #
    All Paths From Source to Target — LC 797
  10. #
    Minimum Height Trees — LC 310
This section locks:
  • Directed vs undirected thinking
  • Topological ordering
  • Coloring logic
  • Reverse graph reasoning
  • Graph pruning

HARD: Optimization & Advanced Graph Theory

Now weighted, structural, and deep reasoning.
  1. #
    Dijkstra’s Algorithm — GFG
  2. #
    Network Delay Time — LC 743
  3. #
    Cheapest Flights Within K Stops — LC 787
  4. #
    Minimum Spanning Tree (Kruskal) — GFG
  5. #
    Minimum Spanning Tree (Prim) — GFG
  6. #
    Number of Ways to Arrive at Destination — LC 1976
  7. #
    Critical Connections (Bridges) — LC 1192
  8. #
    Strongly Connected Components (Kosaraju) — GFG
  9. #
    Longest Path in DAG — GFG
  10. #
    Shortest Path in a DAG — GFG
Now this section cleanly covers:
  • Weighted shortest path
  • MST
  • Bridge detection
  • SCC
  • DAG DP-style logic

INTERVIEW REVISION CARD — Pattern 14A

1️⃣ Pattern in One Line

"Model relationships as a graph — then reason about reachability, cycles, ordering, and connectivity."

2️⃣ Recognize It When...

  • Problem has entities with relationships/dependencies
  • Trigger words: "connected", "path exists", "cycle", "order", "prerequisite", "bipartite"
  • Can be modeled as nodes + edges
  • Need to visit/classify all nodes

3️⃣ Don't Confuse With...

  • BFS (P14B) → use BFS for shortest path/minimum steps; DFS for reachability/cycles
  • Union-Find (P15) → DSU for dynamic connectivity; Graph DFS for static traversal
  • Tree (P11) → trees are acyclic graphs; general graphs can have cycles

4️⃣ Approach in 3 Steps

  1. #
    Build adjacency list from input
  2. #
    Choose DFS (cycle/path/ordering) or BFS (shortest path/levels)
  3. #
    Track visited array — mark when entering, unmark if backtracking needed

5️⃣ Invariant to Maintain

"Every visited node is never re-processed — the visited array ensures each node is handled exactly once."

6️⃣ Complexity to Justify

  • Time: O(V + E) — visit each vertex and edge once
  • Space: O(V + E) — adjacency list + visited array
  • Why: Each node and edge processed exactly once

7️⃣ Edge Cases to Always Check

  • Disconnected graph — must start DFS/BFS from all unvisited nodes
  • Self-loops
  • No edges (isolated nodes)
  • Directed vs undirected — handle accordingly
  • Cycle detection differs for directed vs undirected

8️⃣ One Line to Say in Interview

"I'll model this as a graph, build an adjacency list, then apply DFS/BFS — O(V+E) time and space."