002 — Find if Path Exists in Graph

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• Original source: Classic reachability exercise
• Platform: LeetCode — https://leetcode.com/problems/find-if-path-exists-in-graph/
• Topic: graphs
• Difficulty: Easy
• Pattern: reachability (BFS / DFS traversal)
• Basic idea inherited from: queue দিয়ে BFS (../../04-stack-and-queue/); first-arrival traversal

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

n টা node (0 থেকে n-1 পর্যন্ত নম্বর দেওয়া) আর কিছু undirected edges দেওয়া আছে। তোমাকে দুটো node দেওয়া হবে — source আর destination। বলো: edge ধরে হেঁটে কি source থেকে destination-এ আদৌ পৌঁছানো যায়? শুধু হ্যাঁ/না — পথের দৈর্ঘ্য বা পথটা কী, কিছুই লাগবে না।

উদাহরণ

0 -- 1 -- 2        source = 0, destination = 2  -> True (0->1->2)

0 -- 1     3 -- 4   source = 0, destination = 4 -> False (আলাদা দ্বীপ)

Input ও output

উদাহরণ

Input : n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: True

Input : n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: False

Edge case (একটাই node): n = 1, edges = [], source = 0, destination = 0 -> True

চেনা উদাহরণে বোঝা

একটা শহরের road map ভাবো (../concept.md-এর সেই map)। মোড়গুলো node, রাস্তাগুলো edge। তুমি বাসা (source) থেকে stadium (destination)-এ যেতে পারবে কিনা জানতে চাও। তুমি বাসা থেকে বেরিয়ে এক এক করে পৌঁছানো-যায় এমন প্রতিটা মোড়ে যাও, দেখা মোড় গুলো মনে রাখো (যাতে ঘুরে না আসো)। stadium-এ যদি পৌঁছাও — হ্যাঁ; পুরো এলাকা ঘুরেও না পেলে — না।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

মূল ভিত হলো queue দিয়ে BFS (../../04-stack-and-queue/)। একটা queue জিনিসগুলো arrival order-এ process করে; BFS সেই queue-তে start node ঢুকিয়ে দিয়ে বারবার front pop করে আর তার unseen neighbors enqueue করে। "পৌঁছানো যায় কি" প্রশ্নটা মানেই — start থেকে traversal চালিয়ে দেখো destination কখনো queue-তে আসে কিনা।

ভেতরের যুক্তি

লুকানো logic: reachability হলো connectivity। source থেকে destination-এ পথ আছে তখনই, যখন তারা একই connected component-এ থাকে। BFS (বা DFS) start node থেকে যা যা ছোঁয়া সম্ভব সব ছুঁয়ে ফেলে — পুরো component-টা। তাই destination যদি সেই ছোঁয়া-set-এ আসে, পথ আছে; না এলে নেই। visited set নিশ্চিত করে প্রতিটা node বড়জোর একবার process হয়, cycle থাকলেও loop হয় না।

কী দিয়ে তথ্য রাখব

• Adjacency list (dict of lists) — edge list থেকে বানানো; undirected বলে প্রতিটা edge দুই দিকেই যোগ হয়।
• Queue (collections.deque) — BFS frontier ধরে রাখে; arrival order বজায় রাখে।
• Visited set — কোন node ইতিমধ্যে claim হয়েছে, যাতে cycle-এ আটকে না যাই।

এটি কেন উপযুক্ত

Adjacency list fit করে কারণ real graph sparse — প্রতিটা node হাতে গোনা কয়েকটাকে ছোঁয়, আর neighbor list করতে লাগে শুধু O(deg)। Queue fit করে কারণ BFS-এর গোটা চরিত্রই first-in-first-out: যা আগে discover হয়, আগে explore হয়। Visited set fit করে কারণ graph পেছনে loop করতে পারে — set ছাড়া BFS চিরকাল ঘুরতে থাকত।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সরল চিন্তা: source থেকে সব সম্ভাব্য পথ চেষ্টা করে দেখি destination-এ পৌঁছায় কিনা — প্রতিটা branch-এ recurse করে, সব সম্ভাবনা ঘুরে।

উদাহরণ

পথ খোঁজো 0 থেকে:
  0 -> 1 -> 2 ?   পৌঁছে গেছে!
  অন্য candidate: 0 -> 2, এটিও goal-এ পৌঁছায়। visited ছাড়া cycle-এ ফিরে যাওয়ার ঝুঁকি থাকে।

কোথায় বেশি কাজ হচ্ছে

visited ছাড়া সব পথ আলাদা করে ঘোরা exponential হয়ে যেতে পারে — একই node বারবার ভিন্ন পথে ছোঁয়া হয়, আর cycle থাকলে চিরকাল ঘোরে। আসল কথা: কোন পথে পৌঁছালাম তা পাত্তা দিই না, শুধু পৌঁছানো-যায় কিনা চাই। তাই প্রতিটা node একবার ছুঁলেই যথেষ্ট — visited set দিয়ে O(V + E)-তে নামা যায়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: প্রতিটা node বড়জোর একবার visit করলেই reachability পুরো বোঝা হয়ে যায়। একবার কোনো node "ছোঁয়া" হয়ে গেলে তার থেকে যা যা পৌঁছানো যায়, সেগুলো একবারই explore করলে চলে — আবার এলে নতুন কিছু পাওয়ার নেই।

আরও কম কাজে সমাধান

Edge list থেকে adjacency list বানাও। source-কে queue আর visited-এ রাখো। তারপর: front pop করো, প্রতিটা unseen neighbor-কে mark করে enqueue করো; কোনো neighbor destination হলেই True। Queue খালি হয়ে গেলে আর কিছু পৌঁছানোর নেই — False। একই কাজ DFS দিয়েও হয় (queue-র জায়গায় stack); reachability-তে দুটোই সমান।

ভাবনার পরিবর্তন

মোচড়: "সব পথ খুঁজব" না ভেবে ভাবো "source-এর component-টা পুরো ছুঁয়ে ফেলব আর দেখব destination সেই component-এ পড়ল কিনা।" path enumeration থেকে নেমে এসো একবারের traversal-এ।

ছবিতে বোঝা

n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2:

উদাহরণ

adjacency list:
  0 -> [1, 2]
  1 -> [0, 2]
  2 -> [1, 0]

BFS (queue front .. back):
  start: seen = {0}      queue = [0]
  pop 0  -> neighbor 1 (নতুন, enqueue), 2 == destination!  -> True

       0
      / \
     1---2   <- 2 destination, 0 থেকে সরাসরি পৌঁছানো যায়

ছোট input-এ ধাপে ধাপে

n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5:

1. adjacency: 0:[1,2], 1:[0], 2:[0], 3:[5,4], 5:[3,4], 4:[5,3]
2. seen = {0}, queue = [0]
3. pop 0 → neighbor 1 (নতুন, enqueue), 2 (নতুন, enqueue)। কেউ destination 5 না।
4. pop 1 → neighbor 0 (seen)। নতুন কিছু না।
5. pop 2 → neighbor 0 (seen)। নতুন কিছু না।
6. queue খালি। 5 কখনো ছোঁয়া হয়নি → return False। (5 অন্য component-এ।)

কোড ও ব্যাখ্যা

Python

Python

from collections import deque, defaultdict

def valid_path(n, edges, source, destination):
    if source == destination:        # নিজের কাছে নিজে — সবসময় পৌঁছানো যায়
        return True

    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)             # undirected: দুই দিকেই register করো

    seen = {source}
    q = deque([source])              # queue: ../../04-stack-and-queue/ থেকে
    while q:
        node = q.popleft()           # front pop (FIFO)
        for nxt in adj[node]:
            if nxt == destination:
                return True
            if nxt not in seen:
                seen.add(nxt)        # push করার সময় mark করো (pop-এ নয়)
                q.append(nxt)
    return False

# ---- tests ----
assert valid_path(3, [[0, 1], [1, 2], [2, 0]], 0, 2) is True
assert valid_path(6, [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], 0, 5) is False
assert valid_path(1, [], 0, 0) is True            # একটাই node
assert valid_path(2, [[0, 1]], 0, 1) is True
print("সব test pass!")

কোডের প্রতিটি অংশ

• if source == destination: return True — শুরু আর শেষ এক হলে পথ আছেই (length-0 path)।
• adj[u].append(v) / adj[v].append(u) — undirected, তাই edge দুই দিকেই বসাও; এই দ্বিগুণ লাইন ভুললে অর্ধেক graph হারিয়ে যায়।
• seen = {source} / q = deque([source]) — start node একসাথে visited আর queue-তে।
• q.popleft() — deque-এর O(1) front pop; list.pop(0) ব্যবহার করলে BFS চুপিচুপি quadratic হয়ে যায়।
• if nxt == destination: return True — destination ছোঁয়ামাত্র থামো।
• seen.add(nxt) ঠিক q.append(nxt)-এর পাশে — push করার সময় mark, যাতে একই node queue-তে বারবার না ঢোকে।

Output মিলিয়ে দেখা

valid_path(3, [[0,1],[1,2],[2,0]], 0, 2): adjacency 0:[1,2]। pop 0 → neighbor 1 enqueue, তারপর 2 == destination → True। দ্বিতীয় test-এ 0 আর 5 আলাদা component, queue খালি হয়ে False। বাকি দুটোও মেলে। শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O(V + E) — adjacency list বানাতে O(V + E), আর BFS-এ প্রতিটা node একবার pop হয়, প্রতিটা edge constant সংখ্যকবার দেখা হয়।

অতিরিক্ত জায়গা

O(V + E) — adjacency list O(V + E), আর queue ও visited set মিলে O(V)।

যে ভুলগুলো এড়াতে হবে

• undirected graph-এ edge শুধু এক দিকে যোগ করা (adj[u].append(v) করে adj[v].append(u) ভুলে যাওয়া) — অর্ধেক পথ গায়েব।
• seen.add কে pop-এর সময় করা — তখন একই node queue-তে বহুবার ঢুকে BFS ফুলে যায়।
• deque-এর বদলে list দিয়ে pop(0) — প্রতি pop O(n), পুরো BFS quadratic।
• source == destination edge case না ভাবা (যদিও এখানে আগেই ধরা হয়েছে)।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: queue-র FIFO আচরণ (../../04-stack-and-queue/) আর graph traversal (../bfs.md)। এটা সেই six-line BFS reachability — ../concept.md-এর "stadium-এ পৌঁছাতে পারব?" snippet-এরই problem রূপ। এখান থেকেই components, shortest path, multi-source — সব BFS-পরিবার শুরু।

পরের অনুশীলন

• Number of Provinces (পুরো graph-এ কয়টা component) — https://leetcode.com/problems/number-of-provinces/ (এই tracker-এর #6)
• Number of Islands (grid-এ reachability/components) — https://leetcode.com/problems/number-of-islands/ (#4)
• Graph Valid Tree (connectivity + cycle) — https://leetcode.com/problems/graph-valid-tree/

কৌশলটি মনে রাখুন

Reachability via traversal: "A থেকে B-তে পৌঁছানো যায় কি" = A থেকে BFS/DFS চালিয়ে দেখা B ছোঁয়া হলো কিনা। visited set দিয়ে O(V + E), cycle থাকলেও নিরাপদ। distance লাগলে BFS, না লাগলে যেকোনোটা।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "পৌঁছানো-যায়-কি = একই component-এ কিনা = start থেকে একবার traversal।" যখনই 'connected?', 'reachable?', 'path exists?' দেখবে — adjacency list বানাও, queue-তে start ঢোকাও, visited discipline মেনে front pop করতে থাকো; destination ছুঁলে True, queue খালি হলে False।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।