09 — Graphs¶

বিন্দু আর সংযোগ। শহর আর রাস্তা। মানুষ আর বন্ধুত্ব। একবার 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/) আসলে এমন একটা 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/) — BFS আসলে একটা queue-ই, DFS আসলে একটা stack-ই।
O(1) "এটা কি আগে দেখেছি?" check-এর জন্য hash sets (../05-hashing/)।
DFS-এর জন্য recursion-এ স্বাচ্ছন্দ্য (../06-recursion-and-backtracking/)।
shortest-path.md পড়ার আগে heaps (../08-heap-priority-queue/) — Dijkstra ওটার উপরেই দাঁড়িয়ে।

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

collections.deque আর কেন popleft O(1) কিন্তু list.pop(0) O(n)।
Tree traversals (../07-trees/) — level order-ই BFS হয়ে যায়; preorder/postorder হয়ে যায় DFS।
visited-এর idea টা: একটা set, যেটা cycle থাকলে infinite loop ঠেকায়।
heapq-র push/pop (../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-র 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 ছোঁয়	LeetCode 1791	Graph representation warm-up
Find if Path Exists in Graph — সরল reachability check	LeetCode 1971	BFS/DFS reachability
Flood Fill — pixels-এর একটা connected region নতুন রঙে আঁকো	LeetCode 733	DFS on a grid
Building Roads — সব শহর connect করতে minimum নতুন রাস্তা	CSES — Building Roads	Connected components

Medium¶

Problem	Source	Pattern
Number of Islands — grid-এ connected land region গোনো	LeetCode 200	Components on a grid
Number of Provinces — matrix থেকে friend cluster গোনো	LeetCode 547	Components (DSU-রও classic)
Rotting Oranges — neighbor-এ ছড়াতে ছড়াতে সব কমলা পচতে কত মিনিট	LeetCode 994	Multi-source BFS
Clone Graph — এক node থেকে reachable পুরো graph-এর deep-copy	LeetCode 133	Traversal + hash map of copies
Course Schedule — prerequisites দিয়ে সব course শেষ করা যাবে কি?	LeetCode 207	Cycle detection / topological sort
Course Schedule II — একটা valid course order output করো	LeetCode 210	Topological sort (Kahn)
01 Matrix — প্রতিটা cell থেকে nearest zero-র distance	LeetCode 542	Multi-source BFS
Pacific Atlantic Water Flow — যেসব cell-এর পানি দুই ocean-এই পৌঁছায়	LeetCode 417	Reverse DFS/BFS from borders
Network Delay Time — একটা signal-এর সব node-এ পৌঁছানোর সময়	LeetCode 743	Dijkstra
Is Graph Bipartite? — nodes-কে দুই রঙে রাঙাও যাতে কোনো edge এক রঙের না হয়	LeetCode 785	BFS/DFS coloring
Labyrinth — grid maze-এর ভেতর দিয়ে shortest path, path-টাও লাগবে	CSES — Labyrinth	BFS on grid + path reconstruction
Building Teams — teammate-conflict ছাড়া ছাত্রদের দুই team-এ ভাগ করো	CSES — Building Teams	Bipartite coloring
Course Schedule (CSES) — requirements মেনে course order করো	CSES — Course Schedule	Topological sort
Shortest Routes I — city 1 থেকে সব city-তে cheapest routes	CSES — Shortest Routes I	Dijkstra

Hard¶

Problem	Source	Pattern
Word Ladder — এক শব্দ থেকে আরেক শব্দে fewest এক-অক্ষর change	LeetCode 127	BFS on an implicit graph
Alien Dictionary — sorted word list থেকে অক্ষরের order উদ্ধার করো	LeetCode 269	Topological sort from constraints
Cheapest Flights Within K Stops — hop limit সহ cheapest route	LeetCode 787	Bellman-Ford flavor / constrained Dijkstra
Bus Routes — target-এ পৌঁছাতে fewest buses (stops না)	LeetCode 815	BFS on a transformed graph
Swim in Rising Water — সবচেয়ে আগে কখন grid পার হতে পারবে	LeetCode 778	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-র graph traversal আর SSSP modules; reference write-up cp-algorithms BFS আর cp-algorithms DFS-এ।

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-এ মোটামুটি Div 2 B থেকে উপরের দিকে BFS/DFS-কে জানা ধরে নেওয়া হয়।
CSES Problem Set-এর graph section একটা বিখ্যাত ladder — এই folder-এর CSES pick গুলো সেখান থেকেই।
Dijkstra, 0-1 BFS, আর topological sort + DP-on-DAG হলো রোজকার tool; reference treatment-এর জন্য দেখো cp-algorithms Dijkstra আর cp-algorithms topological sort, আর guided path-এর জন্য USACO Guide।
পরের topic গুলো (MST, bridges, strongly connected components, flows) সবই এই folder-এর traversal-এর উপরে দাঁড়িয়ে।

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

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

Source map¶

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