# Graph traversal — BFS-এর স্তর ও DFS-এর পথ

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

BFS কাছের node-গুলো আগে খোঁজে। DFS একটি পথ ধরে যত দূর সম্ভব যায়, তারপর ফিরে আসে। নিচের ছোট উদাহরণে **কোন state বদলাচ্ছে এবং কেন বদলাচ্ছে**, তা পাশাপাশি দেখো।

## BFS — একটি maze-এ দূরত্ব বসানো

শুরু `(0,0)`। ওপর, নিচ, বাঁ বা ডানে এক ঘর যাওয়ার খরচ 1। `#` দেয়াল; `·` এখনো দেখা হয়নি। সংখ্যা মানে শুরু থেকে **সবচেয়ে কম কতটি move** লাগে। Highlight করা ঘরগুলো সেই ধাপে নতুন আবিষ্কৃত।

```dsa
kind: grid
title: BFS-এর সাতটি distance level
steps:
  - label: দূরত্ব 0 — শুরু
    rows: [[0, '·', '·', '#'], ['#', '#', '·', '·'], ['·', '·', '·', '#']]
    active: [[0, 0]]
    muted: [[0, 3], [1, 0], [1, 1], [2, 3]]
    note: Queue-তে প্রথমে শুধু (0,0)।
  - label: দূরত্ব 1 — ডানে এক ঘর
    rows: [[0, 1, '·', '#'], ['#', '#', '·', '·'], ['·', '·', '·', '#']]
    active: [[0, 1]]
    muted: [[0, 3], [1, 0], [1, 1], [2, 3]]
    note: শুরুর নিচে দেয়াল; নতুন খোলা ঘর শুধু (0,1)।
  - label: দূরত্ব 2 — আবার ডানে
    rows: [[0, 1, 2, '#'], ['#', '#', '·', '·'], ['·', '·', '·', '#']]
    active: [[0, 2]]
    muted: [[0, 3], [1, 0], [1, 1], [2, 3]]
    note: (0,1) থেকে নতুন ঘর (0,2)।
  - label: দূরত্ব 3 — নিচে বাঁক
    rows: [[0, 1, 2, '#'], ['#', '#', 3, '·'], ['·', '·', '·', '#']]
    active: [[1, 2]]
    muted: [[0, 3], [1, 0], [1, 1], [2, 3]]
    note: ডানে দেয়াল। এবার (1,2)-এ নামি।
  - label: দূরত্ব 4 — দুই নতুন ঘর
    rows: [[0, 1, 2, '#'], ['#', '#', 3, 4], ['·', '·', 4, '#']]
    active: [[1, 3], [2, 2]]
    muted: [[0, 3], [1, 0], [1, 1], [2, 3]]
    note: (1,2) থেকে ডানে ও নিচে যাওয়া যায়; দুটোর দূরত্বই 4।
  - label: দূরত্ব 5 — নিচের সারিতে বাঁয়ে
    rows: [[0, 1, 2, '#'], ['#', '#', 3, 4], ['·', 5, 4, '#']]
    active: [[2, 1]]
    muted: [[0, 3], [1, 0], [1, 1], [2, 3]]
    note: (2,2) থেকে নতুন ঘর (2,1)। (1,3) থেকে নতুন ঘর নেই।
  - label: দূরত্ব 6 — শেষ খোলা ঘর
    rows: [[0, 1, 2, '#'], ['#', '#', 3, 4], [6, 5, 4, '#']]
    active: [[2, 0]]
    muted: [[0, 3], [1, 0], [1, 1], [2, 3]]
    note: (2,0) থেকে আর নতুন ঘর মেলে না। Queue খালি হলে শেষ।
```

একই দূরত্বের ঘরগুলো মিলে একটি level। এখানে একটি level-এ দুইটি ঘর আছে, তাই **distance level আর queue থেকে pop-এর সংখ্যা এক নয়**।

| পুরো যে level process হলো | পরের level-এর নতুন ঘর | নতুন দূরত্ব |
| --- | --- | --- |
| `(0,0)` | `(0,1)` | 1 |
| `(0,1)` | `(0,2)` | 2 |
| `(0,2)` | `(1,2)` | 3 |
| `(1,2)` | `(1,3)`, `(2,2)` | 4 |
| `(1,3)`, `(2,2)` | `(2,1)` | 5 |
| `(2,1)` | `(2,0)` | 6 |
| `(2,0)` | নেই | শেষ |

Queue ছোট distance-এর node আগে process করে। আরও ছোট পথ থাকলে সেই পথের আগের node থেকেই ঘরটি আগে আবিষ্কৃত হতো। তাই **সমান edge cost-এর graph-এ** প্রথমবার পাওয়া distance-ই shortest distance। [BFS-এর পূর্ণ ব্যাখ্যা](bfs.md)।

## DFS — গভীরে যাওয়া, তারপর ফিরে আসা

এবার ছয়টি node-এর একটি undirected graph। রেখার দুই দিকেই যাওয়া যায়। প্রতিবেশী একাধিক হলে alphabetically ছোট নাম আগে নেব।

```mermaid
flowchart TD
  A((A)) --- B((B))
  A --- C((C))
  B --- D((D))
  C --- E((E))
  D --- F((F))
  E --- F
```

| Node | সাজানো প্রতিবেশী |
| --- | --- |
| A | B, C |
| B | A, D |
| C | A, E |
| D | B, F |
| E | C, F |
| F | D, E |

Recursive DFS-এর call stack-এ বাম দিক bottom, ডান দিক top। প্রথম ছয় ধাপে node আবিষ্কার হয়; পরের ধাপগুলোতে অসমাপ্ত call শেষ করি।

| ধাপ | কাজ | কাজের পরে call stack | নতুন visited |
| --- | --- | --- | --- |
| 1 | A visit; B-তে যাব | `A` | A |
| 2 | B visit; A দেখা, D-তে যাব | `A B` | B |
| 3 | D visit; B দেখা, F-এ যাব | `A B D` | D |
| 4 | F visit; D দেখা, E-তে যাব | `A B D F` | F |
| 5 | E visit; C-তে যাব | `A B D F E` | E |
| 6 | C visit; A ও E দুটোই দেখা | `A B D F E C` | C |
| 7 | C শেষ; E-তে ফিরি | `A B D F E` | — |
| 8 | E-এর F-ও দেখা; F-এ ফিরি | `A B D F` | — |
| 9 | F শেষ; D-তে ফিরি | `A B D` | — |
| 10 | D শেষ; B-তে ফিরি | `A B` | — |
| 11 | B শেষ; A-তে ফিরি | `A` | — |
| 12 | A-এর পরের neighbor C আগেই দেখা | `A` | — |
| 13 | A শেষ | খালি | — |

```dsa
kind: array
title: একই graph-এ দুই traversal-এর সম্পূর্ণ visit order
steps:
  - label: DFS — একটি পথ ধরে গভীরে
    values: [A, B, D, F, E, C]
    indices: false
    note: ফেরার ক্রম C → E → F → D → B → A; ফেরার সময় আবার visit গুনি না।
  - label: BFS — কাছের node আগে
    values: [A, B, C, D, E, F]
    indices: false
    note: দূরত্বের স্তর A; তারপর B ও C; তারপর D ও E; সবশেষে F।
```

BFS-এর ক্রম shortest distance খুঁজতে কাজে লাগে। DFS-এর যাওয়া-ফেরার ক্রম দিয়ে connected component, cycle ও finish time বোঝা যায়; directed acyclic graph-এ topological order-ও পাওয়া যায়।

## `visited` কখন বসাতে হবে

এই graph-এ visited বাদ দিলে DFS শুরুতেই `A → B → A` ফিরে আসে। তাই D পর্যন্ত পৌঁছানোর আগেই একই দুই node বারবার চলতে থাকে।

```mermaid
flowchart LR
  start["প্রতিবেশী পাওয়া গেল"] --> seen{"আগে আবিষ্কৃত?"}
  seen -->|হ্যাঁ| skip["এড়িয়ে যাও"]
  seen -->|না| mark["visited চিহ্ন দাও"]
  mark --> next["BFS: queue-তে দাও / DFS: ভেতরে যাও"]
```

BFS-এ **queue-তে ঢোকানোর সময়** visited বসাও। Pop করার সময় পর্যন্ত অপেক্ষা করলে একাধিক neighbor একই node আবার queue-তে ঢোকাতে পারে। অপ্রয়োজনীয় কাজ বাড়ে এবং distance/count update-এর যুক্তি ভুল হওয়ার সুযোগ তৈরি হয়।

## নিজে চেষ্টা করো

1. Maze-এর `(0,3)` দেয়াল সরালে কোন distance বদলায়?
2. Maze-এ DFS চালাও; neighbor order ওপর, নিচ, বাঁ, ডান। ঘরগুলোতে visit order লেখো, তারপর BFS distance-এর সঙ্গে তুলনা করো।
3. A–F graph-এ উল্টো alphabetical neighbor order নিলে DFS-এর output কী হয়?
4. Cycle `B–D–F–E–C–A–B`-তে DFS কোন edge দেখে cycle ধরতে পারবে? Undirected graph-এ যে parent থেকে এসেছ তার edge-কে আলাদা করতে ভুলবে না।

চলমান উদাহরণ: [VisuAlgo graph traversal](https://visualgo.net/en/dfsbfs)। আরও পড়া: [BFS](https://cp-algorithms.com/graph/breadth-first-search.html), [DFS](https://cp-algorithms.com/graph/depth-first-search.html)।