# Graphs — Concept

[অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md)

> একটা শহরের road map, যেটা তুমি একটা Python dict-এ ধরে রাখতে পারো।

---

## Real-life analogy: একটা শহরের road map

তোমার শহরের একটা map খোলো। মোড়গুলো হলো **nodes**। তাদের মাঝের রাস্তাগুলো হলো **edges**। এখন প্রতিটা classic graph question হয়ে যায় এমন প্রশ্ন, যেটা তুমি বাস্তব জীবনে করেইছ:

- "বাসা থেকে stadium-এ আদৌ যাওয়া যায়?" → *reachability* (BFS বা DFS)।
- "সবচেয়ে কম মোড় পেরিয়ে?" → *shortest path, unweighted* (BFS)।
- "প্রতিটা রাস্তার travel time জানা থাকলে fastest route?" → *shortest path, weighted* (Dijkstra)।
- "বন্যায় কোন কোন এলাকা বিচ্ছিন্ন হয়ে গেছে?" → *connected components*।
- "এই রাস্তাগুলো one-way" → *directed* edges।
- "এই সেতুতে toll আছে" → *weighted* edges।

এই পুরো folder জুড়ে map-টা মাথায় রাখো। এখানকার প্রতিটা algorithm আসলে সেই map-এ হাঁটার একটা শৃঙ্খলাবদ্ধ উপায় — হারিয়ে না গিয়ে, চক্কর না কেটে।

*Directed* graph-এর জন্য দ্বিতীয় একটা analogy: একটা **recipe**। "ডিম ফেটাও, তারপর batter-এ মেশাও" — এটা এক step থেকে আরেক step-এ একটা arrow। Recipe-টা একটা বৈধ order-এ রান্না করাই হলো topological sort ([topological-sort.md](topological-sort.md))।

## Memory picture: adjacency list

"Graph কীভাবে store করব?" — এই প্রশ্নের একটাই প্রধান উত্তর: প্রতিটা node-এর জন্য তার direct neighbor-দের list রাখো। Python-এ সেটা হলো dict of lists।

এই ছোট undirected graph-টা নাও:

```text
      A ---- B
      |      |
      |      |
      C ---- D ---- E
```

Edge list (problem গুলো সাধারণত এভাবেই graph হাতে ধরিয়ে দেয়):

```text
edges = [("A","B"), ("A","C"), ("B","D"), ("C","D"), ("D","E")]
```

Adjacency list (তোমার যেভাবে store করা উচিত):

```text
adj = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}
```

পড়ো এভাবে: "A-র direct neighbors হলো B আর C।" খেয়াল করো, প্রতিটা undirected edge **দুবার** আসে — দুই প্রান্ত থেকে একবার করে। এই দ্বিগুণ করার লাইনটাই beginner graph code-এ সবচেয়ে বেশি ভুলে যাওয়া লাইন।

প্রতিদ্বন্দ্বী representation টা হলো **adjacency matrix**: একটা n-by-n grid, যেখানে cell `[i][j]`-তে 1 (বা একটা weight) থাকে edge থাকলে। এটা "i→j edge আছে কি?" এর উত্তর দেয় O(1)-এ, কিন্তু O(n^2) memory খরচ করে আর এক node-এর neighbors list করতে লাগে O(n)।

| | Adjacency list | Adjacency matrix |
| --- | --- | --- |
| Memory | O(V + E) | O(V^2) |
| List neighbors of v | O(deg(v)) — just its own list | O(V) — scan a full row |
| Edge check u–v | O(deg(u)) | O(1) |
| Best for | sparse graphs (most real ones) | tiny or very dense graphs |

Rule of thumb: **default হিসেবে adjacency list-ই নাও।** Real graphs (রাস্তা, বন্ধুত্ব, prerequisites) sparse হয় — একটা node হাতে গোনা কয়েকটাকে ছোঁয়, সবাইকে না। 10^5 nodes-এ একটা matrix-এর লাগে 10^10 cells; list-এর লাগে মোটামুটি edge প্রতি একটা entry।

তৃতীয় একটা representation-এর কোনো storage-ই লাগে না: **implicit graph**। একটা grid maze-এ cell `(r, c)`-র neighbors হলো শুধুই `(r±1, c)` আর `(r, c±1)` — যা on the fly compute করা যায়। Word Ladder-এর neighbors হলো "এক অক্ষর দূরের শব্দ।" Neighbors compute করতে পারলেই তোমার একটা graph আছে — `adj` কখনো না বানালেও।

## Core invariants আর vocabulary

- কোনো node-এর **degree**: কতগুলো edge তাকে ছোঁয় (directed graph-এ এটা ভাগ হয় indegree আর outdegree-তে)।
- **Path**: edges ধরে একটা হাঁটা; **cycle**: এমন path যেটা নিজের শুরুতে ফিরে আসে।
- **Connected component**: nodes-এর একটা maximal দ্বীপ, যেখানে সবাই সবার কাছে পৌঁছাতে পারে (undirected)।
- **DAG**: directed acyclic graph — directed, কোনো cycle নেই; একমাত্র এই ধরনটাকেই topologically sort করা যায়।
- **The traversal invariant** (এই folder-এর একমাত্র আইন): *প্রতিটা node `visited` set-এ ঢোকে বড়জোর একবার।* এটা ধরে রাখো, তাহলে BFS/DFS প্রত্যেকে প্রতিটা node একবার আর প্রতিটা edge constant সংখ্যকবার ছোঁয় — O(V + E), graph cost-এর gold standard।
- একটা tree হলো এমন connected undirected graph যার ঠিক `V - 1`-টা edge আর কোনো cycle নেই। Tree-তে একটা extra edge যোগ করলে ঠিক একটা cycle তৈরি হয় — DSU দিয়ে cycle detection-এর মূল fact ([../10-disjoint-set-union/](../10-disjoint-set-union/README.md))।

## কখন graph ব্যবহার করবে — আর কখন না

Problem-টাকে graph হিসেবে model করো যখন:

- Statement-টা states-এর মধ্যে **connections, dependencies, moves, বা transformations** নিয়ে কথা বলে।
- route, network, prerequisite, neighbor, spread, infect, reach — এই ধরনের শব্দ দেখো।
- "জিনিসগুলো" স্পষ্ট (nodes) আর "অনুমোদিত steps" স্পষ্ট (edges) — কোনোটাকে সে নামে ডাকা না হলেও।

Graph-এর দিকে হাত **বাড়িও না** যখন:

- Data টা purely sequential (arrays, strings) বা strictly hierarchical, এক parent-ওয়ালা (trees) — simpler tool-এর code-ও simpler।
- Relationship টা "lookup by key" — সেটা একটা hash map ([../05-hashing/](../05-hashing/README.md))।
- Connections-এর শুধু *grouping* লাগবে, *হাঁটা* না — disjoint set union ([../10-disjoint-set-union/](../10-disjoint-set-union/README.md)) "same group?" এর উত্তর দেয় আরও দ্রুত আর ছোট code-এ।

## Complexity table

V nodes আর E edges-এর একটা graph, adjacency list হিসেবে রাখা:

| Algorithm | Time | Extra space | Answers |
| --- | --- | --- | --- |
| Build adjacency list | O(V + E) | O(V + E) | the structure itself |
| BFS | O(V + E) | O(V) | reachability; shortest paths, unweighted |
| DFS | O(V + E) | O(V) | reachability; components; cycle detection |
| Topological sort (Kahn) | O(V + E) | O(V) | dependency order on a DAG |
| Dijkstra (binary heap) | O((V + E) log V) | O(V) | shortest paths, non-negative weights |
| Bellman-Ford | O(V * E) | O(V) | shortest paths, negative weights allowed |

Symbol না, shape-টা মুখস্থ করো: *traversal গুলো graph-এর size-এ linear; Dijkstra heap-এর জন্য একটা log যোগ করে; Bellman-Ford negatives সহ্য করার দাম দেয় পুরো একটা extra factor দিয়ে।*

## ছোট ছোট Python snippets, dry run সহ

### 1. Edge list → adjacency list

```python
from collections import defaultdict

edges = [("A","B"), ("A","C"), ("B","D"), ("C","D"), ("D","E")]

adj = defaultdict(list)
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)        # undirected: register BOTH directions

print(adj["D"])             # ['B', 'C', 'E']
```

Dry run: edge ("A","B") A-র list-এ B append করে, আর B-র list-এ A। পাঁচটা edge শেষে D-র list-এ append হয়েছে তিনবার (B, C, E edges থেকে) — map-এ তার তিনটা রাস্তার সাথে মিলে যায়।

### 2. "Stadium-এ পৌঁছাতে পারব?" — ছয় লাইনের BFS

```python
from collections import deque

def reachable(adj, start, goal):
    seen = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        if node == goal:
            return True
        for nxt in adj[node]:
            if nxt not in seen:
                seen.add(nxt)       # mark when PUSHED, not when popped
                q.append(nxt)
    return False

print(reachable(adj, "A", "E"))     # True
```

A থেকে dry run: A pop করো, B আর C queue-তে। B pop করো, D queue-তে। C pop করো (D already seen)। D pop করো, E queue-তে। E pop → goal পাওয়া গেছে। প্রতিটা node `seen`-এ ঢুকেছে ঠিক একবার — traversal invariant টা কাজে দেখা যাচ্ছে।

### 3. Grid হলো এমন graph যার কোনো adjacency list নেই

```python
grid = [
    "S.#",
    ".#.",
    "..G",
]
R, C = len(grid), len(grid[0])

def neighbors(r, c):
    for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:    # up, down, left, right
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#":
            yield nr, nc

print(list(neighbors(1, 0)))    # [(0, 0), (2, 0)] -- walls and edges excluded
```

কোনো dict বানানো হয়নি। চার-দিকের offset গুলোই *হলো* edges। এই folder-এর প্রতিটা grid problem ঠিক এই `neighbors` shape-টাই ব্যবহার করে।

### 4. Directed edges বদলায় একটাই লাইন

```python
prereqs = [("calc1", "calc2"), ("calc2", "calc3")]   # take calc1 BEFORE calc2

dadj = defaultdict(list)
for before, after in prereqs:
    dadj[before].append(after)      # one direction only — no mirror line

print(dadj["calc1"])                # ['calc2']
print(dadj["calc3"])                # []  -- calc3 points at nothing
```

Mirror লাইনটা মুছে ফেলাই হলো undirected আর directed storage-এর পুরো পার্থক্য। অর্থের পার্থক্যটা কিন্তু বিশাল: cycles, reachability, আর ordering — সব আলাদাভাবে behave করে — [topological-sort.md](topological-sort.md) এই directed দুনিয়াতেই থাকে।

## পরের ধাপের সাথে bridge

- [visual-explanation.md](visual-explanation.md) ঠিক এই road map-এর উপরেই দুটো traversal animate করে।
- [bfs.md](bfs.md) আর [dfs.md](dfs.md) প্রত্যেকে একটা করে traversal নিয়ে তার প্রতিটা classic trick নিংড়ে বের করে।
- [shortest-path.md](shortest-path.md) weights যোগ করে আর [../08-heap-priority-queue/](../08-heap-priority-queue/README.md)-এর heap-টাকে নিয়ে আসে।
- [topological-sort.md](topological-sort.md) directed, dependency-আকৃতির দুনিয়াটা handle করে।
- [../10-disjoint-set-union/](../10-disjoint-set-union/README.md) "same component?" এর উত্তর দেয় কোনো হাঁটাহাঁটি ছাড়াই।