Graph: প্রশ্নটিকে node আর edge-এ প্রকাশ করা¶
অধ্যায়ের সূচি · অনুশীলন ও সমাধান · মূল ধারণা
Graph problem-এর প্রথম কাজ code লেখা নয়: একটি node কী, একটি edge কী, উত্তর কী মাপছে—এই তিনটি কথা লেখা। Grid-এ node একটি cell, word transformation-এ node একটি word, build system-এ node একটি package। একই algorithm ভিন্ন ধরনের data-তে কাজ করতে পারে।
শেখার ক্রম¶
| ধাপ | পড়া | ফল |
|---|---|---|
| 1 | Representation | Edge list থেকে adjacency list |
| 2 | পূর্ণ BFS/DFS trace | Queue ও call stack দেখা |
| 3 | BFS, তারপর DFS | Distance ও reachability আলাদা করা |
| 4 | Topological sort | Dependency-এর বৈধ ক্রম |
| 5 | Shortest path | Weight-এর শর্ত দেখে algorithm |
| 6 | Implementation ও practice tracker | নিজের input-এ চালানো |
একটি প্রোগ্রাম: কম transfer-এ গন্তব্যে যাওয়া¶
প্রতিটি station একটি node। প্রতিটি সংযোগে সমান এক ধাপ লাগে। A থেকে F পর্যন্ত সর্বনিম্ন edge চাই। নিচের edge-গুলো undirected; neighbor order alphabetical।
flowchart LR
A["A"] --- B["B"]
A --- C["C"]
B --- D["D"]
C --- D
C --- E["E"]
D --- F["F"]
E --- F| Pop | নতুন করে আবিষ্কৃত node | Pop ও enqueue শেষের queue | Distance |
|---|---|---|---|
| শুরু | A | [A] | A=0 |
| A | B, C | [B,C] | B=C=1 |
| B | D | [C,D] | D=2 |
| C | E; D আগেই দেখা | [D,E] | E=2 |
| D | F | [E,F] | F=3 |
| E | নেই; F আগেই দেখা | [F] | অপরিবর্তিত |
| F | নেই | খালি | উত্তর 3 |
Enqueue করার সময় visited লিখলে D ও F দুবার queue-তে যায় না। প্রথম আবিষ্কারের parent রাখলে F ← D ← B ← A থেকে route A → B → D → F পাওয়া যায়। Distance ও parent আলাদা তথ্য: একটির মাধ্যমে খরচ, অন্যটির মাধ্যমে পথ ফেরত পাওয়া যায়।
যদি edge-এর অর্থ travel time হয় এবং A–B-এর সময় 50, A–C-এর সময় 1 হয়, তখন কম edge-ওয়ালা route কম সময়ের নাও হতে পারে। এই ক্ষেত্রে BFS-এর দাবি আর প্রযোজ্য নয়।
Algorithm বাছার ছোট তালিকা¶
| প্রশ্নের শর্ত | Algorithm | কী মনে রাখবেন |
|---|---|---|
| শুধু পৌঁছানো যায় কি না / connected group | BFS বা DFS | Disconnected graph হলে প্রতিটি unvisited node থেকে শুরু |
| সব edge-এর cost সমান | BFS | Distance হলো edge-এর সংখ্যা |
| Cost শুধু 0 বা 1 | 0–1 BFS | 0-cost সামনে, 1-cost পেছনে |
| সব cost nonnegative | Dijkstra | Stale heap entry বাদ দিতে হবে |
| Negative edge-ও আছে | Bellman–Ford বা DAG হলে topo DP | Reachable negative cycle থাকলে finite shortest path নাও থাকে |
| আগে A শেষ, তারপর B | Topological sort | Directed cycle থাকলে বৈধ পূর্ণ ক্রম নেই |
Dependency প্রোগ্রামে arrow-এর অর্থ¶
flowchart LR
core["core"] --> api["api"]
core --> ui["ui"]
api --> app["app"]
ui --> appএখানে core → api মানে core আগে build হবে। Indegree শুরুতে core=0, api=1, ui=1, app=2। core সরালে api ও ui ready; দুটো শেষ হলে app ready। বৈধ order core, api, ui, app; core, ui, api, app-ও বৈধ। “একটাই সঠিক order” ধরে test লিখবেন না।
অনুশীলনের জন্য Course Schedule নোট এবং মূল LeetCode প্রশ্ন খুলুন।