🌐 Complete Graph Roadmap README

A DSA + Interview + CP focused Graph Roadmap with process, intuition, and approach for every topic. Best for OA + Interviews + Competitive Programming.

---

🟢 EASY GRAPH TOPICS (Foundation Level)

1) What is Graph (Directed / Undirected)

Process:

• Understand nodes = vertices
• Understand connections = edges
• Directed → one-way edge
• Undirected → two-way edge

Approach:

• Convert real problems into nodes + relationships
• Think in terms of network traversal

---

2) Graph Representation (Adjacency List / Matrix) ⭐

Process:

• Store neighbors of each node
• Choose list for sparse graph
• Choose matrix for dense graph

Approach:

• Adjacency List → O(V+E) space efficient
• Matrix → O(V²) fast edge check

---

3) Degree of Node (In-degree / Out-degree)

Process:

• Count edges entering node
• Count edges leaving node

Approach:

• Important for topological sort
• Useful in Kahn’s BFS

---

4) BFS (Breadth First Search) ⭐⭐⭐

Process:

• Start from source
• Use queue
• Visit level by level

Approach Pattern:

1. Push source in queue
2. Mark visited
3. Pop node
4. Push all unvisited neighbors

Best For: shortest path in unweighted graph

---

5) DFS (Depth First Search) ⭐⭐⭐

Process:

• Go as deep as possible
• Backtrack when stuck

Approach:

• Recursive DFS
• Stack-based DFS
• Great for components and cycles

---

6) Traversal of Graph (Connected Components)

Process:

• Loop over all nodes
• Start BFS/DFS from unvisited nodes

Approach:

• Every fresh DFS = new component

---

7) Count Number of Nodes & Edges

Process:

• Nodes = total vertices
• Sum adjacency list sizes

Approach:

• Undirected: edges = sum/2
• Directed: direct sum

---

8) Check if Graph is Connected

Process:

• Run DFS from any node
• Count visited nodes

Approach:

• If visited == total nodes → connected

---

9) Number of Connected Components ⭐⭐

Process:

• Run DFS from each unvisited node
• Count DFS calls

Approach:

• DFS call count = components

---

10) Basic Grid Problems (Flood Fill) ⭐⭐

Process:

• Treat cell as node
• Explore 4 directions

Approach:

• BFS/DFS on matrix
• Boundary checks mandatory

---

11) Number of Islands ⭐⭐⭐

Process:

• Scan grid
• Start DFS on every unvisited land

Approach:

• Every DFS = one island

---

12) Detect Cycle in Undirected Graph ⭐⭐⭐

Process:

• DFS with parent tracking
• If visited neighbor != parent → cycle

Approach:

• BFS pair(node,parent)
• DFS recursion with parent

---

🟡 MEDIUM GRAPH TOPICS (Interview Level)

13) Cycle Detection in Directed Graph ⭐⭐⭐

Process:

• Use visited + pathVisited

Approach:

• Back edge in recursion stack = cycle

---

14) Topological Sort (DFS + Kahn) ⭐⭐⭐

Process:

• DAG ordering problem

Approach:

• DFS + stack
• BFS using indegree

---

15) Bipartite Graph Check ⭐⭐⭐

Process:

• 2-color graph
• Adjacent nodes different color

Approach:

• BFS/DFS coloring
• Same color conflict = not bipartite

---

16) Shortest Path in Unweighted Graph ⭐⭐

Process:

• BFS from source
• Level = distance

Approach:

• distance[child] = distance[node]+1

---

17) Dijkstra’s Algorithm ⭐⭐⭐

Process:

• Pick minimum distance node
• Relax edges

Approach:

• Min heap + distance array
• Works for positive weights

---

18) Bellman-Ford Algorithm ⭐⭐

Process:

• Relax all edges V-1 times

Approach:

• Good for negative edges

---

19) Detect Negative Cycle ⭐⭐

Process:

• Run 1 extra relaxation

Approach:

• If still relaxes → negative cycle

---

20) Multi-source BFS ⭐⭐

Process:

• Push all sources initially

Approach:

• All start at distance 0
• Expand simultaneously

---

21) Grid Shortest Path ⭐⭐⭐

Process:

• BFS over matrix
• Distance per cell

Approach:

• Use queue + direction arrays

---

22) Rotten Oranges ⭐⭐

Process:

• Multi-source BFS from rotten oranges

Approach:

• Each level = 1 minute

---

23) Number of Provinces

Approach:

• DFS on adjacency matrix
• Count components

---

24) Word Ladder ⭐⭐⭐

Process:

• Each word = node
• One letter difference = edge

Approach:

• BFS with dictionary set

---

25) Clone Graph ⭐⭐

Approach:

• DFS/BFS + hashmap old→new node

---

26) Course Schedule ⭐⭐⭐

Approach:

• DAG cycle + topological sort

---

🔴 HARD GRAPH TOPICS (Advanced)

27) Floyd-Warshall ⭐⭐⭐

Process:

• Try every node as intermediate

Approach:

• Triple loop DP
• All-pairs shortest path

---

28) MST ⭐⭐⭐

Goal: minimum total edge weight connecting all nodes

---

29) Kruskal’s Algorithm

Approach:

• Sort edges
• Use DSU
• Pick smallest safe edge

---

30) Prim’s Algorithm

Approach:

• Grow MST from source
• Min heap edges

---

31) DSU / Union Find ⭐⭐⭐

Process:

• Find parent
• Union sets

Approach:

• Path compression
• Union by size/rank

---

32) SCC (Kosaraju) ⭐⭐⭐

Process:

1. DFS order
2. Reverse graph
3. DFS by stack order

---

33) Tarjan’s Algorithm ⭐⭐⭐

Approach:

• Low-link + discovery time
• Finds SCC / bridges / articulation

---

34) Bridges ⭐⭐⭐

Condition:

• low[child] > tin[parent]

---

35) Articulation Points ⭐⭐⭐

Condition:

• low[child] >= tin[node]

---

36) Shortest Path in Weighted DAG ⭐⭐

Approach:

• Topological order + relax edges

---

37) 0-1 BFS ⭐⭐⭐

Approach:

• Deque
• Weight 0 → push front
• Weight 1 → push back

---

38) K Shortest Paths

Approach:

• Modified Dijkstra
• Store multiple distances

---

39) Network Delay Time ⭐⭐

Approach:

• Dijkstra standard application

---

40) Reconstruct Itinerary ⭐⭐

Approach:

• Hierholzer DFS + lexical order

---

⚫ DIFFICULT GRAPH TOPICS (CP / Expert)

41) Binary Lifting ⭐⭐⭐

Approach:

• Sparse parent table
• Fast kth ancestor / LCA

---

42) Heavy Light Decomposition ⭐⭐⭐

Approach:

• Break tree into heavy chains
• Segment tree over chains

---

43) Euler Tour Technique ⭐⭐⭐

Approach:

• Flatten tree into array
• Subtree becomes range

---

44) Centroid Decomposition ⭐⭐⭐

Approach:

• Recursively split tree by centroid

---

45) Persistent DSU ⭐⭐⭐

Approach:

• Versioned DSU states

---

46) Dynamic Connectivity ⭐⭐⭐

Approach:

• Offline queries + DSU rollback

---

47) Max Flow ⭐⭐⭐

Approach:

• Augmenting paths
• Residual graph

---

48) Dinic’s Algorithm ⭐⭐⭐

Approach:

• BFS level graph
• DFS blocking flow

---

49) Min Cut ⭐⭐⭐

Approach:

• Use max-flow min-cut theorem

---

50) Bipartite Matching ⭐⭐⭐

Approach:

• DFS augmenting path / Hopcroft-Karp

---

51) Hungarian Algorithm ⭐⭐⭐

Approach:

• Assignment optimization

---

52) Traveling Salesman ⭐⭐⭐

Approach:

• DP + bitmask
• state = mask, node

---

53) Meet in the Middle (Graph States)

Approach:

• Split state space in half

---

54) Graph Coloring (Advanced)

Approach:

• Backtracking / greedy / DP bitmask

---

🎯 FINAL LEARNING ORDER

Graph Basics
→ BFS + DFS
→ Grid Problems
→ Cycle + Topological Sort
→ Shortest Path
→ MST + DSU
→ SCC + Bridges
→ Tree Algorithms
→ Flow + Matching
→ Advanced CP Graphs

---

🚀 PRO TIP

For interviews:

• BFS
• DFS
• Topological sort
• Dijkstra
• DSU
• MST
• SCC
• Bridges

For CP:

• HLD
• Binary lifting
• Max flow
• Matching
• TSP DP

---

⭐ Goal

After completing this README roadmap, you can solve:

• 90% Interview Graph Problems
• Most OA graph questions
• Advanced Codeforces/LeetCode Hard graph problems

---

🧠 MATHEMATICAL LOGIC BEHIND EACH GRAPH TOPIC

This section explains the math intuition / proof logic behind the algorithms so you can solve problems by reasoning, not memorization.

🔹 BFS Mathematical Logic

• Works on levels (distance layers)
• If source is at distance 0, then all direct neighbors are at 1
• Their neighbors are at 2
• Hence BFS guarantees: dist[v] = minimum number of edges from source
• This is why BFS solves shortest path in unweighted graphs.

---

🔹 DFS Mathematical Logic

• DFS explores one full path before trying another.
• This naturally creates a tree of recursion states.
• The math idea is: Every edge is explored once
• Total complexity: O(V + E)

DFS is based on recursive graph decomposition.

---

🔹 Connected Components Logic

A graph is partitioned into disjoint reachable sets.

Mathematically:

• If u can reach v, both belong to same component.

• Components form an equivalence relation:

  • reflexive
  • symmetric (for undirected)
  • transitive

So: Number of fresh DFS/BFS starts = number of components

---

🔹 Cycle Detection Logic

Undirected

A cycle exists if:

• we revisit a visited node
• and it is not the parent

Mathematical condition: visited[child] = true && child != parent

Directed

A cycle exists if there is a back edge.

Condition: visited[v] && pathVisited[v]

This means current recursion path loops.

---

🔹 Topological Sort Logic

For every directed edge: u -> v

The ordering must satisfy: u appears before v

This is a partial order problem.

Kahn’s Algorithm math:

• indegree = number of prerequisites
• node with indegree 0 can be solved first

This is why it solves Course Schedule.

---

🔹 Bipartite Graph Logic

A graph is bipartite if it can be divided into 2 disjoint color sets.

Mathematical property:

• No odd length cycle
• Equivalent theorem: Graph is bipartite iff no odd cycle exists

Color relation: color[child] = 1 - color[node]

---

🔹 Dijkstra Mathematical Relaxation

Core equation: dist[v] = min(dist[v], dist[u] + wt)

This is called edge relaxation.

Why greedy works:

• smallest unvisited distance is always final
• only valid for non-negative weights

This follows greedy proof by contradiction.

---

🔹 Bellman-Ford Logic

Shortest path can contain at most: V-1 edges

So we relax all edges exactly V-1 times.

Negative cycle theorem:

• If relaxation happens on Vth iteration
• shortest path is unbounded
• therefore negative cycle exists

---

🔹 Floyd-Warshall DP Logic

DP relation: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Meaning:

• shortest path from i to j
• either direct
• or through node k

This is all-pairs shortest path DP.

---

🔹 MST Logic

For MST:

• total nodes = V
• total selected edges = V-1

Mathematical theorem:

Choose the minimum safe edge crossing a cut.

This is the cut property.

Used by:

• Kruskal
• Prim

---

🔹 DSU Logic

Each component behaves like a disjoint mathematical set.

Operations:

• find(x) → representative element
• union(a,b) → merge two sets

Optimization proof:

• path compression + union by rank
• amortized nearly constant
• O(alpha(n))

---

🔹 Bridges Logic

Edge (u,v) is bridge if removing it increases components.

Condition: low[v] > tin[u]

Meaning:

• child subtree cannot reach ancestor of parent
• so edge is critical

---

🔹 Articulation Point Logic

Node u is articulation point if removing it disconnects graph.

Condition: low[v] >= tin[u]

Meaning:

• child subtree depends fully on u

---

🔹 0-1 BFS Logic

Weights are only 0 or 1.

Math idea:

• weight 0 → same distance layer
• weight 1 → next layer

So deque simulates Dijkstra in: O(V + E)

---

🔹 Binary Lifting Logic

Parent jump table: up[node][j] = 2^j th ancestor

Mathematical decomposition: Any integer k can be written as powers of 2.

Example: 13 = 8 + 4 + 1

So kth ancestor becomes binary jumps.

---

🔹 Max Flow Logic

Core theorem: Flow in = Flow out

Conservation law: sum(incoming) = sum(outgoing)

Residual capacity: residual = capacity - flow

Final theorem: Max Flow = Min Cut

This is the base of Dinic and Edmonds-Karp.

---

🎯 HOW TO THINK MATHEMATICALLY IN GRAPH

For every graph problem ask:

1. Is it reachability? → BFS/DFS
2. Is it ordering? → Topological
3. Minimum cost? → Dijkstra/MST
4. Components merging? → DSU
5. Critical edge/node? → Bridges/AP
6. Tree queries? → Binary lifting/HLD
7. Capacity transfer? → Flow

This is the real mathematical decision tree for graph problems.