# Graph: প্রশ্নটিকে node আর edge-এ প্রকাশ করা

[অধ্যায়ের সূচি](README.md) · [অনুশীলন ও সমাধান](problems/README.md) · [মূল ধারণা](concept.md)

Graph problem-এর প্রথম কাজ code লেখা নয়: **একটি node কী, একটি edge কী, উত্তর কী মাপছে**—এই তিনটি কথা লেখা। Grid-এ node একটি cell, word transformation-এ node একটি word, build system-এ node একটি package। একই algorithm ভিন্ন ধরনের data-তে কাজ করতে পারে।

## শেখার ক্রম

| ধাপ | পড়া | ফল |
| --- | --- | --- |
| 1 | [Representation](concept.md) | Edge list থেকে adjacency list |
| 2 | [পূর্ণ BFS/DFS trace](visual-explanation.md) | Queue ও call stack দেখা |
| 3 | [BFS](bfs.md), তারপর [DFS](dfs.md) | Distance ও reachability আলাদা করা |
| 4 | [Topological sort](topological-sort.md) | Dependency-এর বৈধ ক্রম |
| 5 | [Shortest path](shortest-path.md) | Weight-এর শর্ত দেখে algorithm |
| 6 | [Implementation](implementation.py) ও [practice tracker](problems/README.md) | নিজের input-এ চালানো |

## একটি প্রোগ্রাম: কম transfer-এ গন্তব্যে যাওয়া

প্রতিটি station একটি node। প্রতিটি সংযোগে সমান এক ধাপ লাগে। A থেকে F পর্যন্ত সর্বনিম্ন edge চাই। নিচের edge-গুলো undirected; neighbor order alphabetical।

```mermaid
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-এর অর্থ

```mermaid
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 নোট](problems/015-course-schedule.md) এবং [মূল LeetCode প্রশ্ন](https://leetcode.com/problems/course-schedule/) খুলুন।