README.md

10 - Graphs

PHASE 10 — GRAPHS (461–480)

Topics Covered

• Graph Traversal with BFS and DFS
• Connected Components and Cycle Detection
• Topological Sorting and DAG Scheduling
• Shortest Path and Weighted Graph Problems
• Grid-Based Graph Traversal
• Union-Find and Tree Validation

---

Problems List

No.	Problem	Difficulty	Topics	Link
1	Flood Fill	Easy	DFS, BFS, Grid	Open
2	Number of Islands	Medium	DFS, BFS, Grid	Open
3	Clone Graph	Medium	DFS, BFS, Graph	Open
4	Max Area of Island	Medium	DFS, BFS, Grid	Open
5	Pacific Atlantic Water Flow	Medium	DFS, BFS, Grid	Open
6	Course Schedule	Medium	Topological Sort	Open
7	Course Schedule II	Medium	Topological Sort	Open
8	Graph Valid Tree	Medium	Union-Find, DFS	Open
9	Number of Connected Components	Medium	Union-Find, DFS	Open
10	Redundant Connection	Medium	Union-Find	Open
11	Network Delay Time	Medium	Dijkstra, Shortest Path	Open
12	Cheapest Flights Within K Stops	Medium	BFS, Dijkstra	Open
13	Rotting Oranges	Medium	BFS, Grid	Open
14	Walls and Gates	Medium	BFS, Grid	Open
15	Surrounded Regions	Medium	DFS, BFS, Grid	Open
16	Detect Cycle in Directed Graph	Medium	DFS, Topological Sort	Open
17	Detect Cycle in Undirected Graph	Medium	DFS, Union-Find	Open
18	Topological Sort	Medium	DAG, Ordering	Open
19	Word Ladder	Hard	BFS, Shortest Path	Open
20	Dijkstra Algorithm	Hard	Shortest Path	Open

---

Important Patterns

Graph Traversal

• Use DFS for component exploration and flood-fill style problems
• Use BFS for shortest path in unweighted graphs and level-based propagation
• Mark visited nodes early to avoid repeated processing

Cycle Detection and Connectivity

• Union-Find is useful for undirected connectivity and redundant edges
• DFS color/state tracking helps detect directed cycles
• Connected components can often be counted with repeated traversal

Topological Sorting

• Use in-degree counts and a queue for DAG scheduling problems
• A cycle exists if not all nodes can be processed
• Useful for dependency resolution and course planning

Shortest Path

• Use Dijkstra when edge weights are non-negative
• Use BFS when every edge has equal weight
• Keep the current best distance in a priority queue