Graphs — Concept¶

একটা শহরের 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)।

Memory picture: adjacency list¶

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

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

      A ---- B
      |      |
      |      |
      C ---- D ---- E

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

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

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

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/)।

কখন 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/)।
Connections-এর শুধু grouping লাগবে, হাঁটা না — disjoint set union (../10-disjoint-set-union/) "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¶

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¶

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 নেই¶

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 বদলায় একটাই লাইন¶

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 এই directed দুনিয়াতেই থাকে।

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

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