Graph, BFS ও DFS: graph interview সমস্যা সমাধান

Graph হলো edge দিয়ে সংযুক্ত node (vertex)-এর সেট। Edge directed (একমুখী) বা undirected হতে পারে এবং weight (খরচ) বহন করতে পারে। Graph মানচিত্র, সামাজিক network, ওয়েব লিংক, কাজের dependency ও grid মডেল করে।

Graph উপস্থাপন

• Adjacency list: প্রতিটি node-এর প্রতিবেশীর তালিকা। O(V + E) space নেয়। সাধারণ পছন্দ।
• Adjacency matrix: V বাই V table। দ্রুত edge খোঁজা, O(V²) space, ছোট বা ঘন graph-এ ভালো।
• Edge list: জোড়ার তালিকা। সরল ইনপুট ফরম্যাট।

// edges: [[0,1],[0,2],[1,3]]  (undirected)
function buildGraph(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { graph[a].push(b); graph[b].push(a); }
  return graph;
}

অনেক সমস্যা বদলে grid দেয়। প্রতিটি cell একটি node, প্রতিবেশী ওপর, নিচ, বাম ও ডান (সীমা যাচাই করুন)।

Depth-first search (DFS)

একটি পথ ধরে যতটা সম্ভব গভীরে যান, তারপর backtrack করুন। Recursion বা স্পষ্ট stack ব্যবহার করুন। Cycle-এ অসীম loop এড়াতে visited set রাখুন।

function dfs(graph, start) {
  const visited = new Set();
  function go(node) {
    visited.add(node);
    for (const next of graph[node]) if (!visited.has(next)) go(next);
  }
  go(start);
  return visited;
}
// সময় O(V + E), space O(V)

ভালো: connected component খোঁজা, cycle শনাক্ত, topological sort, সব পথ অনুসন্ধান ও flood fill।

Breadth-first search (BFS)

Queue দিয়ে স্তর ধরে অনুসন্ধান করুন। Unweighted graph-এ BFS শুরু থেকে সংক্ষিপ্ততম পথ (সবচেয়ে কম edge) খোঁজে।

function shortestPath(graph, start, target) {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  for (let i = 0; i < queue.length; i++) {      // index pointer ধীর shift() এড়ায়
    const node = queue[i];
    if (node === target) return dist.get(node);
    for (const next of graph[node]) {
      if (!dist.has(next)) { dist.set(next, dist.get(node) + 1); queue.push(next); }
    }
  }
  return -1;
}
// সময় O(V + E), space O(V)

একই node বহুবার যোগ এড়াতে node enqueue করার সময়ই visited চিহ্নিত করুন, dequeue-র সময় নয়।

প্যাটার্ন ১: grid ও flood fill (Number of Islands)

Grid-এ সংযুক্ত 1-এর দল গুনুন।

function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;
  function sink(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== "1") return;
    grid[r][c] = "0";                          // visited চিহ্ন
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === "1") { count++; sink(r, c); }
  return count;
}
// সময় O(rows * cols)

লক্ষ্য করুন: এটি ইনপুট বদলায়। তা উল্লেখ করুন, বা আলাদা visited set ব্যবহার করুন। বিশাল grid-এ খুব গভীর recursion stack ভরিয়ে দিতে পারে, তাই BFS বা স্পষ্ট stack নিরাপদ হতে পারে।

Multi-source BFS: একসাথে অনেক cell দিয়ে queue শুরু করুন (যেমন Rotting Oranges, 01 Matrix)।

প্যাটার্ন ২: cycle শনাক্ত

• Undirected graph: DFS-এর সময় parent নয় এমন visited node-এ পৌঁছালে cycle।
• Directed graph: তিনটি অবস্থা ব্যবহার করুন (অদেখা, বর্তমান পথে, শেষ)। বর্তমান পথে থাকা node-এ পৌঁছালে cycle।

প্যাটার্ন ৩: topological sort (dependency)

Directed acyclic graph (DAG)-এর জন্য এমন ক্রম বানান যেখানে প্রতিটি edge আগে থেকে পরে যায়। কোর্স schedule ও build ক্রমে ব্যবহৃত।

Kahn-এর algorithm (BFS):

১. প্রতিটি node-এর in-degree (আগত edge) গুনুন। ২. in-degree 0 এমন সব node queue-তে রাখুন। ৩. একটি node বের করে ক্রমে যোগ করুন, তার প্রতিবেশীর in-degree কমান এবং 0 হলে queue-তে রাখুন। ৪. ক্রমে graph-এর চেয়ে কম node থাকলে cycle আছে।

function canFinish(n, prerequisites) {
  const graph = Array.from({ length: n }, () => []), indeg = new Array(n).fill(0);
  for (const [course, pre] of prerequisites) { graph[pre].push(course); indeg[course]++; }
  const queue = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
  let done = 0;
  for (let i = 0; i < queue.length; i++) {
    done++;
    for (const next of graph[queue[i]]) if (--indeg[next] === 0) queue.push(next);
  }
  return done === n;
}

প্যাটার্ন ৪: connected component ও Union-Find

Edge আসার সাথে কোন node সংযুক্ত ট্র্যাক করতে Union-Find (disjoint set) path compression সহ প্রায় O(1)-এ find ও union সমর্থন করে। "connected component-এর সংখ্যা", "redundant connection" ও Kruskal-এর minimum spanning tree-তে ব্যবহার করুন।

Unweighted graph-এর বাইরে

• Dijkstra-এর algorithm: অঋণাত্মক weight-এ সংক্ষিপ্ততম পথ, priority queue দিয়ে, O((V + E) log V)।
• Bellman-Ford: ঋণাত্মক weight সামলায়।
• 0-1 BFS ও A* কাজের রূপভেদ।

DFS নাকি BFS

লক্ষ্য	পছন্দ
Unweighted graph-এ সংক্ষিপ্ততম পথ	BFS
Component গোনা, flood fill	যেকোনোটি
Cycle শনাক্ত, topological ক্রম, সব পথ	DFS (বা Kahn-এর BFS)
অতি গভীর graph (stack overflow ঝুঁকি)	BFS বা iterative DFS

সাধারণ ভুল

• Visited set ভুলে যাওয়া, ফলে অসীম loop।
• BFS-এ অনেক দেরিতে visited চিহ্নিত করা।
• বিচ্ছিন্ন graph না সামলানো (প্রতিটি node-কে শুরু হিসেবে loop করুন)।
• ভুল grid সীমা, বা cell আবার দেখা।
• Graph বানানোর সময় directed ও undirected edge গুলিয়ে ফেলা।

অনুশীলনের সমস্যা

Number of Islands, Clone Graph, Rotting Oranges, Course Schedule, Course Schedule II, Pacific Atlantic Water Flow, Word Ladder, Number of Connected Components, Network Delay Time।

মূল কথা: adjacency list বানান, সংক্ষিপ্ততম পথ ও স্তর ক্রমে BFS, component ও cycle-এ DFS, dependency-তে Kahn-এর algorithm ব্যবহার করুন, এবং সবসময় visited node ট্র্যাক করুন।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ২ (data structure ও আচরণ): 3 নম্বর (মোট 5)। আগের লেখা: Binary tree ও BST: traversal ও interview প্যাটার্ন.