# 09 — Graphs

> **এখান থেকে শুরু করুন:** [সহজ ব্যাখ্যা, শেখার ক্রম ও বাস্তব ব্যবহার](learning-guide.md) → [প্রশ্ন, official link ও স্থানীয় সমাধান](problems/README.md)। [উৎসের তালিকা](source-map.md)-এ reference পাবেন।

> বিন্দু আর সংযোগ। শহর আর রাস্তা। মানুষ আর বন্ধুত্ব। একবার graph দেখা শিখে গেলে আর না-দেখে থাকতে পারবে না — computer science-এর অর্ধেকটাই আসলে লুকানো graph problem।

---

## এই data structure টা কী

**Graph** হলো কিছু **nodes**-এর (যাদের vertices-ও বলে) একটা set, যারা **edges** দিয়ে জোড়া। ব্যস, এটাই পুরো definition — আর এই ঢিলেঢালা ভাবটাই আসল কথা। Array (একটা লাইন) বা tree (এক parent-ওয়ালা hierarchy) থেকে আলাদা — graph *যেকোনো* connection pattern-কে জায়গা দেয়: cycles, দুই point-এর মাঝে একাধিক route, বিচ্ছিন্ন দ্বীপ।

যেসব flavor-এর সাথে দেখা হবে:

- **Undirected** — edge দুই দিকেই যায় (বন্ধুত্ব)।
- **Directed** — edge-এর একটা direction আছে (one-way রাস্তা, "course A-র জন্য course B লাগবে")।
- **Weighted** — edge-এর একটা cost আছে (রাস্তার দৈর্ঘ্য, flight-এর দাম)।
- **Unweighted** — প্রতিটা edge সমান।

একটা tree ([../07-trees/](../07-trees/README.md)) আসলে এমন একটা graph যার কোনো cycle নেই আর একটাই connected টুকরো — তাই এখানকার সবকিছু তোমার জানা জিনিসেরই generalization।

## এটা কেন আছে (কোন pain solve করে)

অনেক real question আসলে value নিয়ে না, *relationship* নিয়ে:

- "A থেকে B-তে কোনো route আছে কি?"
- "Shortest / cheapest route কোনটা?"
- "Prerequisites মেনে এই course গুলো কোন order-এ নিতে পারি?"
- "কোন users একই friend cluster-এ আছে?"

Arrays, hash maps, আর trees স্বাভাবিকভাবে "যেকোনো কিছু যেকোনো কিছুর সাথে জুড়তে পারে" — এটা প্রকাশ করতে পারে না। Graph আমাদের connection problem-এর একটা ভাষা দেয় — আর হাতে গোনা কয়েকটা traversal algorithm (BFS, DFS, Dijkstra, topological sort), যেগুলো একই কয়েকটা move দিয়েই এমন প্রশ্নের এক বিশাল পরিবারের উত্তর দেয়।

## Real software-এ কোথায় ব্যবহার হয়

- **Maps আর navigation** — রাস্তা হলো edge, মোড় হলো node, Dijkstra-family algorithm তোমার route খুঁজে দেয়।
- **Social network** — friend suggestion মানে "তোমার থেকে 2 edge দূরের nodes"।
- **The web** — pages আর hyperlinks; search ranking শুরুই হয়েছিল একটা graph computation হিসেবে।
- **Package manager আর build system** — install/build order হলো dependencies-এর topological sort।
- **Compilers** — task scheduling, dead-code detection, register allocation — সব graph-এর উপরেই চলে।
- **Network routing** — internet আক্ষরিক অর্থেই shortest-path algorithm দিয়ে packet route করে।
- **Game AI** — grid আর navigation mesh-এ pathfinding।

## Prerequisites

- Solid Python: dicts, lists, sets, functions, recursion।
- Queue আর stack-এর behavior ([../04-stack-and-queue/](../04-stack-and-queue/README.md)) — BFS আসলে একটা queue-*ই*, DFS আসলে একটা stack-*ই*।
- O(1) "এটা কি আগে দেখেছি?" check-এর জন্য hash sets ([../05-hashing/](../05-hashing/README.md))।
- DFS-এর জন্য recursion-এ স্বাচ্ছন্দ্য ([../06-recursion-and-backtracking/](../06-recursion-and-backtracking/README.md))।
- [shortest-path.md](shortest-path.md) পড়ার আগে heaps ([../08-heap-priority-queue/](../08-heap-priority-queue/README.md)) — Dijkstra ওটার উপরেই দাঁড়িয়ে।

## শেখার আগে কী revise করবে

- `collections.deque` আর কেন `popleft` O(1) কিন্তু `list.pop(0)` O(n)।
- Tree traversals ([../07-trees/](../07-trees/README.md)) — level order-ই BFS হয়ে যায়; preorder/postorder হয়ে যায় DFS।
- `visited`-এর idea টা: একটা set, যেটা cycle থাকলে infinite loop ঠেকায়।
- `heapq`-র push/pop ([../08-heap-priority-queue/concept.md](../08-heap-priority-queue/concept.md))।

## Learning goals (checklist)

- [ ] Edge list থেকে adjacency list বানাতে পারা এক মিনিটের কমে — হাতে আর code-এ, দুভাবেই।
- [ ] Adjacency list vs adjacency matrix explain করতে পারা, আর কোনটা কখন জেতে।
- [ ] কাগজে BFS চালিয়ে explain করতে পারা — কোনো node-এ প্রথমবার পৌঁছানোই কেন shortest unweighted path।
- [ ] DFS দুভাবেই চালাতে পারা — recursively আর explicit stack দিয়ে।
- [ ] কোনো adjacency structure না বানিয়েই একটা 2D grid-কে graph হিসেবে treat করতে পারা।
- [ ] যেকোনো traversal দিয়ে connected components গুনতে পারা।
- [ ] Directed graph-এ cycle detect করতে পারা (coloring) আর undirected-এ (parent check বা DSU)।
- [ ] `heapq` দিয়ে Dijkstra implement করা, আর negative edge কেন এটা ভেঙে দেয় — explain করতে পারা।
- [ ] Kahn's algorithm দিয়ে একটা topological order বের করা আর "no valid order" detect করা।
- [ ] [shortest-path.md](shortest-path.md)-র situation table থেকে — না দেখেই — ঠিক algorithm টা বাছতে পারা।

## Problem categories

| Category | Typical question shape |
| --- | --- |
| Traversal / reachability | "Can you get from A to B?", "visit everything" |
| Connected components | "How many islands / provinces / clusters?" |
| Shortest path (unweighted) | "Minimum steps / moves / transformations" |
| Shortest path (weighted) | "Cheapest / fastest route", "network delay" |
| Multi-source spreading | "Rotting oranges", "distance to nearest X for every cell" |
| Topological ordering | "Course prerequisites", "build order", "alien dictionary" |
| Cycle detection | "Is the schedule possible?", "find the redundant edge" |
| Bipartite / coloring | "Split into two teams with no internal conflict" |
| Graph construction | "Clone a graph", "build the graph from implicit rules" |

## Practice list

নিচের সব problem আমাদের নিজেদের ভাষায় বর্ণনা করা; official statement-এর জন্য link follow করো। Difficulty label গুলো আনুমানিক।

### Easy

| Problem | Source | Pattern |
| --- | --- | --- |
| Find Center of Star Graph — যে node-কে প্রতিটা edge ছোঁয় · [ব্যাখ্যা](problems/001-find-center-of-star-graph.md) | [LeetCode 1791](https://leetcode.com/problems/find-center-of-star-graph/) | Graph representation warm-up |
| Find if Path Exists in Graph — সরল reachability check · [ব্যাখ্যা](problems/002-find-if-path-exists.md) | [LeetCode 1971](https://leetcode.com/problems/find-if-path-exists-in-graph/) | BFS/DFS reachability |
| Flood Fill — pixels-এর একটা connected region নতুন রঙে আঁকো · [ব্যাখ্যা](problems/003-flood-fill.md) | [LeetCode 733](https://leetcode.com/problems/flood-fill/) | DFS on a grid |
| Building Roads — সব শহর connect করতে minimum নতুন রাস্তা · [ব্যাখ্যা](problems/007-building-roads.md) | [CSES — Building Roads](https://cses.fi/problemset/task/1666) | Connected components |

### Medium

| Problem | Source | Pattern |
| --- | --- | --- |
| Number of Islands — grid-এ connected land region গোনো · [ব্যাখ্যা](problems/004-number-of-islands.md) | [LeetCode 200](https://leetcode.com/problems/number-of-islands/) | Components on a grid |
| Number of Provinces — matrix থেকে friend cluster গোনো · [ব্যাখ্যা](problems/006-number-of-provinces.md) | [LeetCode 547](https://leetcode.com/problems/number-of-provinces/) | Components (DSU-রও classic) |
| Rotting Oranges — neighbor-এ ছড়াতে ছড়াতে সব কমলা পচতে কত মিনিট · [ব্যাখ্যা](problems/008-rotting-oranges.md) | [LeetCode 994](https://leetcode.com/problems/rotting-oranges/) | Multi-source BFS |
| Clone Graph — এক node থেকে reachable পুরো graph-এর deep-copy · [ব্যাখ্যা](problems/013-clone-graph.md) | [LeetCode 133](https://leetcode.com/problems/clone-graph/) | Traversal + hash map of copies |
| Course Schedule — prerequisites দিয়ে সব course শেষ করা যাবে কি? · [ব্যাখ্যা](problems/015-course-schedule.md) | [LeetCode 207](https://leetcode.com/problems/course-schedule/) | Cycle detection / topological sort |
| Course Schedule II — একটা valid course order output করো · [ব্যাখ্যা](problems/016-course-schedule-ii.md) | [LeetCode 210](https://leetcode.com/problems/course-schedule-ii/) | Topological sort (Kahn) |
| 01 Matrix — প্রতিটা cell থেকে nearest zero-র distance · [ব্যাখ্যা](problems/009-01-matrix.md) | [LeetCode 542](https://leetcode.com/problems/01-matrix/) | Multi-source BFS |
| Pacific Atlantic Water Flow — যেসব cell-এর পানি দুই ocean-এই পৌঁছায় · [ব্যাখ্যা](problems/014-pacific-atlantic.md) | [LeetCode 417](https://leetcode.com/problems/pacific-atlantic-water-flow/) | Reverse DFS/BFS from borders |
| Network Delay Time — একটা signal-এর সব node-এ পৌঁছানোর সময় · [ব্যাখ্যা](problems/018-network-delay-time.md) | [LeetCode 743](https://leetcode.com/problems/network-delay-time/) | Dijkstra |
| Is Graph Bipartite? — nodes-কে দুই রঙে রাঙাও যাতে কোনো edge এক রঙের না হয় · [ব্যাখ্যা](problems/011-is-graph-bipartite.md) | [LeetCode 785](https://leetcode.com/problems/is-graph-bipartite/) | BFS/DFS coloring |
| Labyrinth — grid maze-এর ভেতর দিয়ে shortest path, path-টাও লাগবে · [ব্যাখ্যা](problems/010-labyrinth.md) | [CSES — Labyrinth](https://cses.fi/problemset/task/1193) | BFS on grid + path reconstruction |
| Building Teams — teammate-conflict ছাড়া ছাত্রদের দুই team-এ ভাগ করো · [ব্যাখ্যা](problems/012-building-teams.md) | [CSES — Building Teams](https://cses.fi/problemset/task/1668) | Bipartite coloring |
| Course Schedule (CSES) — requirements মেনে course order করো · [ব্যাখ্যা](problems/017-course-schedule-cses.md) | [CSES — Course Schedule](https://cses.fi/problemset/task/1679) | Topological sort |
| Shortest Routes I — city 1 থেকে সব city-তে cheapest routes · [ব্যাখ্যা](problems/019-shortest-routes-i.md) | [CSES — Shortest Routes I](https://cses.fi/problemset/task/1671) | Dijkstra |

### Hard

| Problem | Source | Pattern |
| --- | --- | --- |
| Word Ladder — এক শব্দ থেকে আরেক শব্দে fewest এক-অক্ষর change · [ব্যাখ্যা](problems/021-word-ladder.md) | [LeetCode 127](https://leetcode.com/problems/word-ladder/) | BFS on an implicit graph |
| Alien Dictionary — sorted word list থেকে অক্ষরের order উদ্ধার করো · [ব্যাখ্যা](problems/024-alien-dictionary.md) | [LeetCode 269](https://leetcode.com/problems/alien-dictionary/) | Topological sort from constraints |
| Cheapest Flights Within K Stops — hop limit সহ cheapest route · [ব্যাখ্যা](problems/022-cheapest-flights-k-stops.md) | [LeetCode 787](https://leetcode.com/problems/cheapest-flights-within-k-stops/) | Bellman-Ford flavor / constrained Dijkstra |
| Bus Routes — target-এ পৌঁছাতে fewest buses (stops না) · [ব্যাখ্যা](problems/023-bus-routes.md) | [LeetCode 815](https://leetcode.com/problems/bus-routes/) | BFS on a transformed graph |
| Swim in Rising Water — সবচেয়ে আগে কখন grid পার হতে পারবে · [ব্যাখ্যা](problems/025-swim-in-rising-water.md) | [LeetCode 778](https://leetcode.com/problems/swim-in-rising-water/) | Dijkstra-style on grid (minimax) |

## Visualization ideas

- Nodes-কে বৃত্ত আর edges-কে রেখা হিসেবে আঁকো; BFS-এর জন্য nodes-কে *waves*-এ রঙ করো — প্রতিটা distance layer-এর জন্য আলাদা রঙ।
- DFS-এর জন্য recursion-টা আঁকো গভীরে ঢুকে যাওয়া একটা সাপের মতো, আর backtracking দেখাও সাপটার পিছিয়ে আসা হিসেবে।
- Grid-এর জন্য visited cells shade করো আর BFS frontier-কে animate করো একটা ছড়িয়ে পড়া ring-এর মতো (পানিতে কালির মতো)।
- Dijkstra-র জন্য প্রতিটা node-এর ভেতরে current best distance লেখো আর edges relax হতে হতে live update করো।
- Topological sort-এর জন্য nodes-এর উপরে indegree counter আঁকো আর সেগুলো শূন্যের দিকে নামতে দেখো।
- Interactive: [VisuAlgo](https://visualgo.net/en)-র graph traversal আর SSSP modules; reference write-up [cp-algorithms BFS](https://cp-algorithms.com/graph/breadth-first-search.html) আর [cp-algorithms DFS](https://cp-algorithms.com/graph/depth-first-search.html)-এ।

## Common mistakes (সাধারণ ভুল)

- BFS-এ nodes-কে visited mark করা **pop করার সময়, push করার সময় না** — nodes একাধিকবার queue-তে ঢোকে আর runtime ফুলে যায় (distances-ও corrupt হতে পারে)।
- `visited` set-টা পুরোপুরি ভুলে যাওয়া — প্রথম cycle-এই infinite loop।
- Queue হিসেবে `list.pop(0)` ব্যবহার করা — pop প্রতি O(n)। `collections.deque` ব্যবহার করো।
- গভীর graph-এ recursive DFS Python-এর recursion limit-এ (~1000) ধাক্কা খায় — iterative-এ যাও বা সাবধানে limit বাড়াও।
- 10^5 nodes-এর sparse graph-এর জন্য adjacency *matrix* বানানো — 10^10 cells কোথাও আঁটবে না।
- Undirected edges-এর জন্য **দুই direction-ই** add করতে ভুলে যাওয়া (বা directed-এর জন্য দুটোই add করে ফেলা)।
- Negative weights-এ Dijkstra চালিয়ে answer-টা বিশ্বাস করা।
- Grid problem-এ `(row, col)` আর `(x, y)` order গুলিয়ে ফেলা, বা index করার আগে bounds check ভুলে যাওয়া।
- Topological sort-এ ভুলে যাওয়া যে n-এর কম nodes process হওয়া মানেই cycle আছে।

## Interview problem-এর সাথে connection

Graphs হলো big-tech interview preparation-এর একটা স্তম্ভ। Grid problem গুলো (Number of Islands, Rotting Oranges) common warm-up; Course Schedule হলো canonical topological-sort screen; Clone Graph traversal plus bookkeeping পরীক্ষা করে; Word Ladder পরীক্ষা করে তুমি একটা non-graph statement-এর ভেতরের লুকানো graph টা *দেখতে* পারো কিনা। এই folder-এর সবচেয়ে মূল্যবান interview skill হলো **modeling**: জোরে বলা — "states গুলো nodes, moves গুলো edges, আর প্রশ্নটা একটা shortest path — তাই BFS।"

## Competitive programming-এর সাথে connection

- [Codeforces](https://codeforces.com/problemset/)-এ মোটামুটি Div 2 B থেকে উপরের দিকে BFS/DFS-কে জানা ধরে নেওয়া হয়।
- [CSES Problem Set](https://cses.fi/problemset/)-এর graph section একটা বিখ্যাত ladder — এই folder-এর CSES pick গুলো সেখান থেকেই।
- Dijkstra, 0-1 BFS, আর topological sort + DP-on-DAG হলো রোজকার tool; reference treatment-এর জন্য দেখো [cp-algorithms Dijkstra](https://cp-algorithms.com/graph/dijkstra.html) আর [cp-algorithms topological sort](https://cp-algorithms.com/graph/topological-sort.html), আর guided path-এর জন্য [USACO Guide](https://usaco.guide/)।
- পরের topic গুলো (MST, bridges, strongly connected components, flows) সবই এই folder-এর traversal-এর উপরে দাঁড়িয়ে।

## Recommended learning order (পরামর্শমতো শেখার ক্রম)

1. [concept.md](concept.md) — graph কী, adjacency list-এর memory picture, complexity।
2. [visual-explanation.md](visual-explanation.md) — BFS-এর waves আর DFS-এর dives, frame by frame।
3. [bfs.md](bfs.md) — queue-চালিত layer-by-layer search।
4. [dfs.md](dfs.md) — stack-চালিত deep dive।
5. [topological-sort.md](topological-sort.md) — একটা DAG-কে order করা; Kahn's algorithm।
6. [shortest-path.md](shortest-path.md) — Dijkstra (আগে [../08-heap-priority-queue/](../08-heap-priority-queue/README.md) লাগবে)।
7. [implementation.py](implementation.py) — পড়ো, চালাও, ভাঙো, ঠিক করো।
8. [problems/README.md](problems/README.md) — tracker শুরু করো আর grind করো, easy থেকে hard।

## Source map

এই folder-এর প্রতিটা idea আর link কোথা থেকে এসেছে আর প্রত্যেকটার copying status কী — দেখো [source-map.md](./source-map.md)-এ।