Breadth-first search (BFS)

১ · ধারণা — পুকুরের ঢেউ আর বন্ধুদের মধ্যে খবর ছড়ানো

গ্রামের পুকুরে একটি ঢিল ফেলুন। পানিতে প্রথমে একটি ছোট বৃত্ত তৈরি হয়, তারপর তার বাইরে আরেকটি, তারপর আরও বড় একটি। কোনো বৃত্ত তার ভেতরের বৃত্তকে টপকে আগে দূরে পৌঁছায় না — ঢেউ ছড়ায় সমান তালে, স্তরে স্তরে. যে বিন্দুতে ঢেউ আগে পৌঁছায়, সেটি ঢিলের কাছে।

এবার একটি খবরের কথা ভাবুন। রাফি বিকেলে জানল যে কাল ক্লাস বন্ধ। সে তার পাঁচ বন্ধুকে মেসেজ দিল — এরা খবরটি পেল “এক ধাপে”. তারা আবার তাদের বন্ধুদের জানাল, যারা আগে শোনেনি — এরা পেল “দুই ধাপে”. যে একবার খবর শুনেছে, তাকে আবার জানানোর দরকার নেই। শেষে প্রত্যেকের জন্য একটি সংখ্যা দাঁড়ায়: রাফি থেকে কত ধাপ বন্ধুত্বের শিকল পেরিয়ে খবর তার কাছে এসেছে। এই সংখ্যাটিই রাফি থেকে তার দূরত্ব — বন্ধুত্বের graph-এ সবচেয়ে কম কয়টি edge পেরিয়ে পৌঁছানো যায়।

Breadth-first search (BFS, “প্রস্থ-প্রথম অনুসন্ধান”) ঠিক এই প্রক্রিয়ার অ্যালগরিদম। একটি উৎস vertex s থেকে শুরু করে প্রথমে s-এর সব প্রতিবেশী দেখা হয়, তারপর তাদের সব নতুন প্রতিবেশী, তারপর তাদেরও — যেন একটি ঢেউ। “Breadth” মানে প্রস্থ: BFS গভীরে ঢোকার আগে চওড়ায় পুরোটা শেষ করে। এর উল্টো কৌশল হলো একটি পথ ধরে যতদূর সম্ভব গভীরে যাওয়া — সেটি DFS, পরের পর্বের বিষয় (পর্ব ৪১).

গ্রাফের ভাষায় বললে (পরিভাষা আর উপস্থাপন পর্ব ৩৯-এ): উৎস s থেকে v-এর সবচেয়ে ছোট পথ-এর দৈর্ঘ্য δ(s, v) মানে s থেকে v-তে যাওয়ার যেকোনো পথের সবচেয়ে কম edge-সংখ্যা; কোনো পথ না থাকলে δ = ∞. BFS vertex-গুলোকে স্তরে ভাগ করে:

• স্তর L₀ = {s} — দূরত্ব ০.
• স্তর L₁ = s-এর সব প্রতিবেশী — দূরত্ব ১.
• স্তর L_k+1 = যারা আগের কোনো স্তরে নেই, কিন্তু L_k-এর কারও প্রতিবেশী — দূরত্ব k + 1.

যে vertex কোনো স্তরেই পড়ে না, সে s থেকে অগম্য (unreachable). এই স্তরগুলো আপনি আগেও দেখেছেন: tree-র level-order traversal (পর্ব ২৬) আসলে root থেকে BFS. পার্থক্য একটাই — tree-তে cycle নেই, তাই একই node দুবার আসার ভয় নেই; সাধারণ গ্রাফে আছে, তাই “আগে দেখেছি কি না” মনে রাখতে হয়।

২ · অ্যালগরিদম — queue, dist আর parent

BFS চালাতে তিনটি জিনিস লাগে:

• queue — যে vertex-গুলো আবিষ্কৃত হয়েছে কিন্তু যাদের প্রতিবেশী এখনো দেখা হয়নি। একে বলে frontier বা সীমান্ত — ঢেউয়ের সামনের কিনারা।
• dist[v] — উৎস থেকে v-এর দূরত্ব; শুরুতে সবার −1 (বা ∞), মানে “এখনো দেখা হয়নি”. আলাদা visited অ্যারে রাখতে পারেন, কিন্তু dist ≠ −1 নিজেই সেই কাজ করে।
• parent[v] — কোন vertex থেকে v-কে প্রথম দেখা হয়েছিল। এটি দিয়ে পরে পথ বানানো যায় (অংশ ৪).

Pseudocode — BFS from source s (0-based vertices)

BFS(G, s):
    for each vertex v:  dist[v] = -1;  parent[v] = -1
    dist[s] = 0
    Q = empty queue;  Q.push(s)
    while Q is not empty:
        u = Q.pop_front()                    // the oldest discovered vertex
        for each neighbour v of u:
            if dist[v] == -1:                // first time anyone sees v
                dist[v] = dist[u] + 1        // mark NOW, before pushing
                parent[v] = u
                Q.push_back(v)

একটি মাত্র শর্ত — dist[v] == -1 — নিশ্চিত করে যে প্রতিটি vertex জীবনে একবারই queue-তে ঢোকে। একে বলে “push করার সময় চিহ্ন দেওয়া”, আর এটি না করলে কী বিপদ, তা অংশ ৮-এ দেখবেন। নিচের গ্রাফটি এই পর্বের প্রধান উদাহরণ: ৯টি vertex, ১০টি undirected edge — 0-1, 0-2, 1-3, 1-4, 2-4, 3-5, 4-5, 4-6, 5-7, 6-7; আর vertex 8 একা, তার কোনো edge নেই। ধরে নিন এগুলো ৯ জন বন্ধু, আর খবর শুরু হলো 0-এর কাছ থেকে। প্রতিটি vertex-এর প্রতিবেশী ছোট থেকে বড় ক্রমে রাখা (adjacency list):

শেষ অবস্থায় dist = [0, 1, 1, 2, 2, 3, 3, 4, −1]. লক্ষ করুন তৃতীয় সারিটি — queue-তে থাকা vertex-গুলোর dist সবসময় সামনে থেকে পেছনে অবনত নয় (কখনো কমে না), আর প্রথম ও শেষটির পার্থক্য সর্বোচ্চ ১. যেমন pop 1-এর পর “1 2 2”, pop 4-এর পর “3 3”. এই পর্যবেক্ষণটিই পরের অংশের প্রমাণের চাবি।

৩ · কেন সবচেয়ে ছোট পথ — স্তরের প্রমাণ

BFS শুধু “সবাইকে খুঁজে পায়” না, বরং প্রত্যেককে সবচেয়ে কম ধাপে খুঁজে পায়। এটি অনেক অ্যালগরিদমের ভিত্তি, তাই একটি পরিষ্কার প্রমাণ জানা দরকার — বিশ্ববিদ্যালয় বা চাকরির লিখিত পরীক্ষায় এটি প্রায়ই চাওয়া হয়। দাবিটি এই:

ধাপ ১ — dist কখনো আসল দূরত্বের চেয়ে কম নয়

dist[v] = dist[u] + 1 লেখা হয় কেবল যখন u-v একটি edge. তাই dist[v] = k হলে parent ধরে পেছনে হাঁটলে s থেকে v-তে k টি edge-এর একটি সত্যিকারের পথ আছে। সবচেয়ে ছোট পথ এর চেয়ে লম্বা হতে পারে না: dist[v] ≥ δ(s, v). সমস্যা থাকলে একটাই হতে পারে — BFS কোনো vertex-কে প্রয়োজনের চেয়ে লম্বা পথে পেয়েছে। সেটি যে হয় না, তা দেখাতে হবে।

ধাপ ২ — queue-র অপরিবর্তনীয় নিয়ম (invariant)

যেকোনো মুহূর্তে queue-তে সামনে থেকে পেছনে v₁, v₂, …, v_r থাকলে: dist[v₁] ≤ dist[v₂] ≤ … ≤ dist[v_r] ≤ dist[v₁] + 1. অর্থাৎ queue-তে সর্বোচ্চ দুটি ভিন্ন দূরত্ব থাকে, d আর d + 1, আর ছোটগুলো সামনে। এটি একটি invariant: শুরুতে সত্য (শুধু s), আর প্রতিটি ধাপ একে রক্ষা করে — সামনে থেকে u (dist d) বের হয়, পেছনে যারা ঢোকে তাদের dist d + 1; বাকিদের dist d বা d + 1, তাই ক্রম আর “পার্থক্য ≤ ১” দুটোই টিকে থাকে। ফল: vertex-গুলো dist-এর অবনত-নয় ক্রমে pop হয় — আগে সব স্তর ০, তারপর সব স্তর ১, এভাবে।

ধাপ ৩ — স্তর ধরে induction

দাবি: প্রতিটি k-এর জন্য, যাদের δ(s, v) = k, তারা সবাই dist = k পায়। Induction k-এর ওপর। k = 0: শুধু s, dist[s] = 0. ধরুন k পর্যন্ত সত্য, আর v-এর δ(s, v) = k + 1. একটি সবচেয়ে ছোট পথ s → … → u → v নিন; তাহলে δ(s, u) = k, তাই অনুমান অনুযায়ী dist[u] = k, আর u একসময় pop হয়। u pop হওয়ার মুহূর্তে দুটি সম্ভাবনা:

• v তখনো অদেখা — তাহলে u-ই তাকে দেখে, dist[v] = k + 1. ✔
• v আগেই দেখা — কোনো w তাকে দেখেছে, যে u-এর আগে pop হয়েছে। ধাপ ২ অনুযায়ী dist[w] ≤ dist[u] = k, তাই dist[v] = dist[w] + 1 ≤ k + 1. আবার ধাপ ১ অনুযায়ী dist[v] ≥ k + 1. তাই dist[v] = k + 1. ✔

আর s থেকে অগম্য v-এর কাছে কোনো পথই নেই, তাই কেউ তাকে push করে না — dist[v] = −1 থাকে, যা δ = ∞-এর সাথে মেলে। ∎

BFS tree আর edge-এর ধরন

প্রতিটি আবিষ্কৃত v (s বাদে) থেকে parent[v]-এর দিকে একটি edge রাখলে একটি tree পাওয়া যায় — BFS tree, যার root s. পৌঁছানো যায় এমন V′ টি vertex থাকলে এতে ঠিক V′ − 1 টি edge. ওপরের গ্রাফে ৮টি vertex পৌঁছানো যায়, tree-তে ৭টি edge: 0-1, 0-2, 1-3, 1-4, 3-5, 4-6, 5-7. বাকি তিনটি (2-4, 4-5, 6-7) non-tree edge. প্রমাণ থেকে একটি গুরুত্বপূর্ণ ফল আসে: undirected গ্রাফে যেকোনো edge (u, v)-এর জন্য |dist[u] − dist[v]| ≤ 1 — একটি edge হয় একই স্তরের দুজনকে জোড়ে, নয়তো পাশাপাশি দুই স্তরকে; কখনো একটি স্তর টপকে যায় না। (যুক্তি: u আগে pop হলে v তখন অদেখা থাকলে dist[v] = dist[u] + 1, আর দেখা থাকলে ধাপ ২-এ dist[v] ≤ dist[u] + 1.) অংশ ৭-এর bipartite যাচাই এই ফলের ওপর দাঁড়িয়ে। Directed graph-এ একটি edge u → v-এর জন্য dist[v] ≤ dist[u] + 1 সত্য, কিন্তু উল্টো দিকে edge অনেক স্তর পেছনেও যেতে পারে।

৪ · পথ পুনর্গঠন, কোড আর জটিলতা

dist শুধু বলে “কত ধাপ”; গুগল ম্যাপের মতো “কোন পথে” জানতে parent লাগে। parent[v] হলো v-এর ঠিক আগের vertex একটি সবচেয়ে ছোট পথে। তাই লক্ষ্য t থেকে শুরু করে parent ধরে উৎস পর্যন্ত হাঁটুন, তারপর ক্রমটি উল্টে দিন — এটিই path reconstruction. পথের দৈর্ঘ্য dist[t], তাই খরচ O(dist[t]) — BFS-এর তুলনায় নগণ্য। একটি parent অ্যারেই সবার পথ ধরে রাখে, O(V) জায়গায়।

একটি সূক্ষ্ম বিষয়: 0 থেকে 7-এ ৪ ধাপের পথ দুটি — 0 1 3 5 7 আর 0 1 4 5 7. BFS যেটি দেবে, তা নির্ভর করে adjacency list-এ প্রতিবেশীর ক্রমের ওপর: এখানে 3 আগে pop হয়েছিল, তাই 5-এর parent 3. পরীক্ষায় “একটি সবচেয়ে ছোট পথ” লিখলে যেকোনোটি ঠিক; কিন্তু অনলাইন জাজে যদি নির্দিষ্ট একটি পথ চায় (যেমন lexicographically ছোটটি), তাহলে প্রতিবেশী সাজিয়ে রাখার মতো বাড়তি নিয়ম লাগে।

পুরো কোড — BFS, dist, parent আর পথ

নিচের প্রোগ্রাম ওপরের গ্রাফে 0 থেকে BFS চালায়, pop-এর ক্রম, dist আর parent ছাপে, তারপর 7, 6 আর 8-এর পথ বানায়। C++-এ queue হিসেবে std::queue; Python-এ collections.deque — কারণ Python list-এর pop(0) প্রতিবার পুরো list সরায়, O(n).

#include <algorithm>
#include <initializer_list>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
void show(const char* name, const vector<int>& a) {
    cout << name; for (int x : a) cout << ' ' << x; cout << '\n';
}
int main() {
    int n = 9;                                   // vertex 8 has no roads at all
    vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4},
                                    {3, 5}, {4, 5}, {4, 6}, {5, 7}, {6, 7}};
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }  // undirected
    vector<int> dist(n, -1), parent(n, -1), order;   // dist -1 = not discovered yet
    queue<int> q; dist[0] = 0; q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop(); order.push_back(u);
        for (int v : adj[u])
            if (dist[v] == -1) {                     // mark when PUSHING, not when popping
                dist[v] = dist[u] + 1; parent[v] = u; q.push(v);
            }
    }
    show("order :", order); show("dist  :", dist); show("parent:", parent);
    for (int t : {7, 6, 8}) {
        if (dist[t] == -1) { cout << "0 -> " << t << ": unreachable\n"; continue; }
        vector<int> path;                            // walk parent pointers back from t
        for (int x = t; x != -1; x = parent[x]) path.push_back(x);
        reverse(path.begin(), path.end());
        cout << "0 -> " << t << ": " << dist[t] << " hops:";
        show("", path);
    }
}

order : 0 1 2 3 4 5 6 7
dist  : 0 1 1 2 2 3 3 4 -1
parent: -1 0 0 1 1 3 4 5 -1
0 -> 7: 4 hops: 0 1 3 5 7
0 -> 6: 3 hops: 0 1 4 6
0 -> 8: unreachable

from collections import deque

n = 9                                  # vertex 8 has no roads at all
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (3, 5), (4, 5), (4, 6), (5, 7), (6, 7)]
adj = [[] for _ in range(n)]
for u, v in edges:                     # undirected: store both directions
    adj[u].append(v); adj[v].append(u)
def bfs(s):
    dist, parent = [-1] * n, [-1] * n  # dist -1 = not discovered yet
    dist[s] = 0
    q, order = deque([s]), []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            if dist[v] == -1:          # mark when PUSHING, not when popping
                dist[v], parent[v] = dist[u] + 1, u
                q.append(v)
    return dist, parent, order
def path(parent, t):                   # walk parent pointers back from t
    p = []
    while t != -1:
        p.append(t)
        t = parent[t]
    return p[::-1]
dist, parent, order = bfs(0)
print("order :", *order)
print("dist  :", *dist)
print("parent:", *parent)
for t in (7, 6, 8):
    if dist[t] == -1:
        print(f"0 -> {t}: unreachable")
    else:
        print(f"0 -> {t}: {dist[t]} hops:", " ".join(map(str, path(parent, t))))

order : 0 1 2 3 4 5 6 7
dist  : 0 1 1 2 2 3 3 4 -1
parent: -1 0 0 1 1 3 4 5 -1
0 -> 7: 4 hops: 0 1 3 5 7
0 -> 6: 3 hops: 0 1 4 6
0 -> 8: unreachable

জটিলতা — O(V + E), আর matrix-এ কেন O(V²)

হিসাবটি দুই ভাগে করুন। (১) প্রতিটি vertex সর্বোচ্চ একবার push আর একবার pop হয়, কারণ push হয় কেবল dist = −1 থেকে বদলানোর সময়, আর সেটি একবারই ঘটে — মোট O(V). (২) একটি vertex u pop হলে তার adjacency list একবার পুরো দেখা হয়, deg(u) টি ধাপে। সব u মিলে Σ deg(u) = 2E (undirected) বা E (directed) — handshake lemma. মোট সময় Θ(V + E) (শুরুতে dist অ্যারে বানানো Θ(V) সহ)। বাড়তি জায়গা Θ(V): dist, parent আর queue — queue-তে একসাথে সর্বোচ্চ V টি vertex থাকে। গ্রাফ রাখতে আরও Θ(V + E).

গ্রাফ যদি adjacency matrix-এ থাকে, তাহলে u-এর প্রতিবেশী খুঁজতে পুরো সারি — V টি ঘর — দেখতে হয়, প্রতিবেশী যত কমই হোক। V টি vertex-এর প্রতিটির জন্য V: Θ(V²). ঘন গ্রাফে (E ≈ V²) দুটো প্রায় সমান, কিন্তু রাস্তার নেটওয়ার্ক বা সামাজিক গ্রাফের মতো বিরল (sparse) গ্রাফে পার্থক্য বিশাল:

৫ · গ্রিডে BFS — ঢাকার রাস্তার গোলকধাঁধা

অনেক সমস্যায় গ্রাফ সরাসরি দেওয়া থাকে না, কিন্তু লুকিয়ে থাকে। ধরুন ঢাকার একটি এলাকার মানচিত্র একটি গ্রিড: প্রতিটি ঘর একটি মোড়, . মানে খোলা, # মানে মেট্রোরেল বা ড্রেনের কাজের জন্য বন্ধ। আপনি S-এ (বাসস্ট্যান্ড) আছেন, যেতে হবে T-তে (হাসপাতাল), আর প্রতি ধাপে ওপর, নিচ, বাঁ বা ডান পাশের খোলা ঘরে যাওয়া যায়। সবচেয়ে কম কয় ধাপ?

এখানে প্রতিটি খোলা ঘর একটি vertex, আর পাশাপাশি দুটি খোলা ঘরের মধ্যে একটি edge — একটি grid graph. গ্রাফটি আলাদা করে বানানোর দরকার নেই: প্রতিবেশী হিসাব করে নেওয়া যায় (r ± 1, c) আর (r, c ± 1) থেকে। এমন গ্রাফকে বলে implicit graph. R × C গ্রিডে V ≤ R·C আর প্রতিটি ঘরের সর্বোচ্চ ৪টি প্রতিবেশী, তাই E ≤ 2·R·C, আর BFS O(R·C) সময় ও জায়গা নেয়। dr[], dc[] অ্যারে দিয়ে চার দিকের লুপ লেখা কনটেস্টের প্রচলিত কৌশল; ৮ দিকে বা দাবার ঘোড়ার চালে চলতে শুধু অ্যারে দুটি বদলান।

#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int main() {
    vector<string> g = {"S...#.....",               // S = start, T = target, # = closed road
                        ".##.#.###.",
                        ".#..#...#.",
                        ".#.####.#.",
                        ".#......#.",
                        ".####.#.#.",
                        "......#..T"};
    int R = g.size(), C = g[0].size();
    vector<vector<int>> d(R, vector<int>(C, -1));
    vector<vector<pair<int, int>>> from(R, vector<pair<int, int>>(C));
    int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};  // up, down, left, right
    queue<pair<int, int>> q; d[0][0] = 0; q.push({0, 0});
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;   // outside the map
            if (g[nr][nc] == '#' || d[nr][nc] != -1) continue;      // wall or already seen
            d[nr][nc] = d[r][c] + 1; from[nr][nc] = {r, c}; q.push({nr, nc});
        }
    }
    cout << "shortest path S -> T: " << d[R - 1][C - 1] << " steps\n";
    for (auto p = from[R - 1][C - 1]; p != make_pair(0, 0); p = from[p.first][p.second])
        g[p.first][p.second] = '*';                  // draw the path, T back to S
    for (const string& row : g) cout << row << '\n';
}

shortest path S -> T: 17 steps
S***#.....
.##*#.###.
.#**#...#.
.#*####.#.
.#******#.
.####.#*#.
......#**T

নিজে চালিয়ে দেখুন — ঢেউ কীভাবে ছড়ায়

নিচের টুলে একই মানচিত্র। “চালিয়ে দেখুন”, তারপর BFS চালান চাপুন: ঘরগুলো queue থেকে বের হওয়ার ক্রমে জ্বলবে, প্রতিটিতে S থেকে দূরত্ব; গাঢ় নীল = এখনকার ঢেউ, শেষে কমলা = সবচেয়ে ছোট পথ। কোনো রাস্তার ঘরে চাপ দিলে সেটি বন্ধ বা খোলা হয়।

const MAP = ["S...#.....", ".##.#.###.", ".#..#...#.", ".#.####.#.", ".#......#.", ".####.#.#.", "......#..T"];
let g = MAP.map(row => [...row]), timer = null;
const R = g.length, C = g[0].length, $ = id => document.getElementById(id);
function bfs() {                                   // same BFS as the C++ program
  const d = g.map(row => row.map(() => -1)), from = {}, seen = [[0, 0]]; d[0][0] = 0;
  for (let i = 0; i < seen.length; i++) {          // the array is the queue; i = its front
    const [r, c] = seen[i];
    for (const [a, b] of [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]])
      if (a >= 0 && a < R && b >= 0 && b < C && g[a][b] !== "#" && d[a][b] === -1) {
        d[a][b] = d[r][c] + 1; from[a + "," + b] = [r, c]; seen.push([a, b]);
      }
  }
  const path = new Set();                          // walk back from T, like parent[]
  for (let p = from[(R - 1) + "," + (C - 1)]; p && (p[0] || p[1]); p = from[p + ""]) path.add(p + "");
  return { d, seen, path };
}
function draw(res, k) {                            // show the first k cells taken from the queue
  const shown = new Set(res.seen.slice(0, k).map(x => x + "")), done = k >= res.seen.length;
  const wave = k > 0 ? res.d[res.seen[k - 1][0]][res.seen[k - 1][1]] : -1;
  let h = ""; for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
    const key = r + "," + c, ch = g[r][c], on = shown.has(key);
    const cls = ch === "#" ? "w" : !on ? "" : done && res.path.has(key) ? "p" : res.d[r][c] === wave ? "f" : "v";
    h += `<div class="c ${cls}" data-k="${key}">${ch === "S" || ch === "T" ? ch : on ? res.d[r][c] : ""}</div>`;
  }
  const t = res.d[R - 1][C - 1]; $("grid").innerHTML = h;
  $("msg").textContent = !done ? `ঢেউ এখন দূরত্ব ${wave}-এ` : t < 0 ? "T-তে পৌঁছানোর কোনো পথ নেই" : `সবচেয়ে ছোট পথ ${t} ধাপ, দেখা ঘর ${res.seen.length}টি`;
}
function play() {
  clearInterval(timer); const res = bfs(); let k = 0;
  timer = setInterval(() => { draw(res, ++k); if (k >= res.seen.length) clearInterval(timer); }, 70);
}
$("grid").onclick = e => {                         // click a road cell to open or close it
  const k = e.target.dataset.k; if (!k) return; const [r, c] = k.split(",").map(Number);
  if (g[r][c] === "." || g[r][c] === "#") { g[r][c] = g[r][c] === "#" ? "." : "#"; clearInterval(timer); draw(bfs(), 0); }
};
$("go").onclick = play; $("rs").onclick = () => { g = MAP.map(row => [...row]); clearInterval(timer); draw(bfs(), 0); };
const res0 = bfs();
console.log(`shortest path S -> T: ${res0.d[R - 1][C - 1]} steps`);
g.forEach((row, r) => console.log(row.map((ch, c) => (res0.path.has(r + "," + c) ? "*" : ch)).join("")));
draw(res0, res0.seen.length);

shortest path S -> T: 17 steps
S***#.....
.##*#.###.
.#**#...#.
.#*####.#.
.#******#.
.####.#*#.
......#**T

৬ · Multi-source BFS আর 0-1 BFS

Multi-source BFS — নিকটতম হাসপাতাল বা ফায়ার স্টেশন

ধরুন শহরের গ্রিডে কয়েকটি ফায়ার স্টেশন আছে, আর প্রতিটি মোড়ের জন্য জানতে চাই নিকটতম স্টেশন কত ধাপ দূরে। সরল উপায়: প্রতিটি স্টেশন থেকে আলাদা BFS চালিয়ে প্রতিটি ঘরে সর্বনিম্ন রাখা — k টি স্টেশনে O(k·R·C). অনেক ভালো উপায়: সব স্টেশনকে শুরুতেই dist = 0 দিয়ে একসাথে queue-তে রাখুন, তারপর সাধারণ BFS. এটিই multi-source BFS, আর এর খরচ একটি BFS-এর সমান, O(R·C).

কেন ঠিক? একটি কাল্পনিক “super source” S* ভাবুন, যা প্রতিটি স্টেশনের সাথে একটি edge দিয়ে যুক্ত। S* থেকে BFS-এর প্রথম স্তরে ঠিক সব স্টেশন, আর প্রতিটি ঘরের dist = ১ + নিকটতম স্টেশনের দূরত্ব। Multi-source BFS সরাসরি সেই প্রথম স্তর থেকে শুরু করে, তাই অংশ ৩-এর প্রমাণ হুবহু খাটে। একই কৌশলে সমাধান হয় “কয়েকটি ঘরে আগুন লাগলে কত মিনিটে সব পুড়বে” বা “ঝুড়ির কয়েকটি পচা আম থেকে কত দিনে সব পচবে” ধাঁচের পরিচিত সমস্যা।

0-1 BFS — ওজন যখন শুধু ০ বা ১

কিছু সমস্যায় edge-এর ওজন দুই রকম: ০ আর ১. যেমন একটি রাস্তায় টোল দিতে হয় (১), অন্যটিতে না (০), আর প্রশ্ন “সবচেয়ে কম কয়বার টোল”; অথবা একটি গ্রিডে প্রতিটি ঘরে একটি তীর আছে — তীরের দিকে যাওয়া বিনা খরচে (০), অন্য দিকে যেতে তীর বদলাতে হয় (১). সাধারণ BFS এখানে ভুল, কারণ সে শুধু edge গোনে। Dijkstra (পর্ব ৪৩) ঠিক উত্তর দেয়, O((V + E) log V)-এ। কিন্তু একটি deque দিয়ে আরও ভালো করা যায় — 0-1 BFS:

Pseudocode — 0-1 BFS (weights are 0 or 1, 0-based vertices)

dist[v] = INF for all v;  dist[s] = 0;  DQ = deque with s
while DQ is not empty:
    u = DQ.pop_front()
    for each edge (u, v, w):
        if dist[u] + w < dist[v]:            // relax: found a cheaper way
            dist[v] = dist[u] + w
            if w == 0: DQ.push_front(v)      // same distance as u: serve it next
            else:      DQ.push_back(v)       // one more: wait behind the others

কেন ঠিক: সাধারণ BFS-এর মতোই একটি invariant — deque-তে সামনে থেকে পেছনে dist অবনত নয়, আর সর্বোচ্চ দুটি মান থাকে, d আর d + 1. সামনে থেকে বের হওয়া u-এর dist d সবচেয়ে ছোট; ওজন ০-এর প্রতিবেশী dist d পেয়ে সামনে যায়, ওজন ১-এর প্রতিবেশী d + 1 পেয়ে পেছনে — দুটোতেই ক্রম টিকে থাকে। তাই deque ঠিক Dijkstra-র priority queue-র মতো সবসময় সবচেয়ে ছোট dist-এর vertex আগে দেয়, কিন্তু প্রতিটি কাজ O(1). মোট সময় O(V + E): একটি vertex একাধিকবার ঢুকতে পারে (ওপরের 3-এর মতো), কিন্তু প্রতিবার dist কমে, আর deque-তে মাত্র দুটি মান থাকে বলে সর্বোচ্চ দুবার। সতর্কতা: এখানে “push-এর সময় visited” চলবে না — dist কমলে আবার ঢোকাতেই হবে; শর্তটি dist[u] + w < dist[v], যাকে বলে relaxation. আর ওজন ২ বা তার বেশি হলে এই কৌশল খাটে না; তখন Dijkstra.

৭ · একই BFS, নানা প্রশ্ন — bipartite, component আর state space

Bipartite যাচাই — দুই রঙে রাঙানো

একটি বিতর্ক উৎসবে অংশগ্রহণকারীদের দুই দলে ভাগ করতে হবে, যাতে প্রতিটি “প্রতিপক্ষ” জোড়া আলাদা দলে পড়ে। গ্রাফের ভাষায়: vertex-গুলোকে দুই রঙে রাঙানো যায় কি, যাতে প্রতিটি edge-এর দুই প্রান্ত আলাদা রঙের? এমন গ্রাফই bipartite graph. BFS দিয়ে উত্তর সহজ: জোড় স্তরের সবাই এক রং, বিজোড় স্তরের সবাই অন্য রং. তারপর প্রতিটি edge দেখুন — কোনো edge-এর দুই প্রান্তের রং এক হলে গ্রাফ bipartite নয়। কোডে আলাদা অ্যারেও লাগে না: color[v] = dist[v] % 2, আর BFS চলার সময়ই কোনো দেখা প্রতিবেশীর dist যদি dist[u]-এর সমান হয়, সংঘাত।

কেন এটি নিখুঁত পরীক্ষা: অংশ ৩ থেকে জানি প্রতিটি edge হয় পাশাপাশি দুই স্তরকে জোড়ে (রং আলাদা, ঠিক আছে), নয়তো একই স্তরের দুজনকে। একই স্তর k-এর u আর v-এর মধ্যে edge থাকলে, BFS tree-তে u আর v থেকে ওপরে উঠে তাদের প্রথম সাধারণ পূর্বপুরুষ (ancestor) a-তে পৌঁছান। a থেকে u আর a থেকে v — দুটি পথের দৈর্ঘ্যই k − dist[a], সমান। দুটি পথ আর edge u-v মিলে একটি cycle, যার দৈর্ঘ্য 2(k − dist[a]) + 1 — বিজোড়. বিজোড় দৈর্ঘ্যের odd cycle-কে দুই রঙে রাঙানো অসম্ভব। তাই: same-layer edge নেই ⇔ গ্রাফ bipartite ⇔ কোনো বিজোড় cycle নেই। প্রধান উদাহরণের গ্রাফে প্রতিটি edge পাশাপাশি স্তরে, তাই সেটি bipartite: {0, 3, 4, 7} আর {1, 2, 5, 6}. এতে 1-2 edge যোগ করলে একই স্তর ১-এর দুজন যুক্ত — cycle 0-1-2, দৈর্ঘ্য ৩, আর গ্রাফ আর bipartite নয়। একাধিক component থাকলে প্রতিটি থেকে আলাদা BFS চালাতে হবে। Edge যখন একে একে আসে আর প্রতিটির পর উত্তর চাই, তখন parity DSU (পর্ব ৩৩) বেশি সুবিধাজনক।

Connected component গোনা

একটি BFS শুধু উৎসের connected component-টি ঘুরে আসে। সবগুলো পেতে বাইরে একটি লুপ: প্রতিটি vertex v-এর জন্য, যদি v এখনো অদেখা হয়, component-এর গণনা এক বাড়ান আর v থেকে BFS চালান (dist অ্যারে সবার জন্য একবারই −1 দিয়ে শুরু, প্রতি BFS-এ নতুন করে নয়)। মোট সময় তবু O(V + E), কারণ প্রতিটি vertex আর edge সব BFS মিলে একবারই দেখা হয়। ওপরের গ্রাফে উত্তর ২: {0, …, 7} আর {8}. মানচিত্রে দ্বীপ গোনা বা ছবি আঁকার সফটওয়্যারের “রং ঢালার বালতি” — এই “flood fill” কাজটিও ঠিক এটাই।

State space-এ BFS — যখন vertex মানে একটি অবস্থা

BFS-এর সবচেয়ে শক্তিশালী ব্যবহার এমন সমস্যায়, যেখানে কোনো গ্রাফ চোখে পড়ে না: প্রতিটি সম্ভাব্য অবস্থা (state) একটি vertex, আর এক চালে যাওয়া একটি edge. “সবচেয়ে কম কয় চালে?” — প্রশ্নটি তখন state space-এ সবচেয়ে ছোট পথ।

• পানির জগ: একটি ৩ লিটার আর একটি ৫ লিটারের জগ, কোনো দাগ নেই। ঠিক ৪ লিটার মাপতে কম কয় চাল? অবস্থা = (ছোট জগে কত, বড় জগে কত); চাল = একটি জগ ভরা, খালি করা, বা একটি থেকে আরেকটিতে ঢালা (যতক্ষণ না একটি খালি বা অন্যটি ভরা হয়)। মোট অবস্থা মাত্র ৪ × ৬ = ২৪টি। (0, 0) থেকে BFS বলে সবচেয়ে কম ৬ চাল: (0,0) → (0,5) → (3,2) → (0,2) → (2,0) → (2,5) → (3,4).
• Word ladder: COLD থেকে WARM, প্রতি ধাপে একটি অক্ষর বদলে, আর প্রতিটি মধ্যবর্তী শব্দ অভিধানে থাকতে হবে: COLD → CORD → CARD → WARD → WARM. এখানে প্রতিটি শব্দ একটি vertex, এক অক্ষরের পার্থক্য একটি edge. পুরো গ্রাফ আগে বানানোর দরকার নেই: একটি শব্দের প্রতিটি অবস্থানে ২৬টি অক্ষর বসিয়ে দেখুন অভিধানের hash set-এ আছে কি না — L অক্ষরের শব্দে প্রতি vertex-এ 26·L টি সম্ভাব্য প্রতিবেশী।
• ধাঁধা আর খেলা: ৮-টাইলের স্লাইডিং পাজলে অবস্থা মানে টাইলগুলোর বিন্যাস — 9!/2 = ১,৮১,৪৪০টি পৌঁছানো যায় এমন অবস্থা, BFS-এর জন্য সহজ। দাবার বোর্ডে ঘোড়াকে এক ঘর থেকে আরেক ঘরে নিতে কম কয় চাল — ৬৪টি অবস্থা।

State space-এ অবস্থাকে একটি tuple, string বা পূর্ণসংখ্যায় এনকোড করে visited রাখুন (hash map বা অ্যারেতে), আর আগে হিসাব করুন অবস্থা কয়টি — সেটিই সময় আর মেমরি ঠিক করে (ভাবনার প্রশ্ন ০৫)।

৮ · সাধারণ ভুল — pop-এর সময় visited আর অন্যান্য ফাঁদ

BFS-এর কোড ছোট, কিন্তু ভুলের জায়গা কম নয়। সবচেয়ে প্রচলিতটি দেখতে নিরীহ: visited চিহ্ন দেওয়া হয় vertex queue থেকে বের হওয়ার সময়, ঢোকার সময় নয় — ফলে একই vertex বারবার queue-তে ঢোকে। একটি ছোট গ্রাফে দেখুন:

এই ভুলের তিন রূপ: (ক) ডায়াগ্রামের মতো pop-এর পর “আগেই visited হলে বাদ” পরীক্ষা থাকলে উত্তর ঠিক, কিন্তু queue-তে Θ(E) টি উপাদান; (খ) সেই পরীক্ষাও না থাকলে একই vertex বারবার প্রসারিত হয়; (গ) পরীক্ষা ছাড়াই push-এর সময় dist লিখলে পরে আসা লম্বা পথ সঠিক dist-কে মুছে দেয় — উত্তরই ভুল। সমাধান একটাই: যে মুহূর্তে প্রথম দেখলেন, সেই মুহূর্তে চিহ্ন দিন আর push করুন।

৯ · AI-এর যুগে BFS — কোড নিখুঁত দেখায়, ফাঁদ থাকে ভেতরে

“একটি গ্রিডে BFS লিখে দাও” — AI কয়েক সেকেন্ডে কোড দেবে, কিন্তু BFS-এর ভুল compile error দেয় না, আর ছোট উদাহরণে উত্তরও প্রায়ই ঠিক আসে। AI-এর লেখা কোডে বারবার যা দেখা যায়: pop-এর সময় visited, Python-এ list দিয়ে queue, ওজনওয়ালা গ্রাফে BFS-কে “shortest path” বলে চালিয়ে দেওয়া, আর complexity-তে “O(V + E)” লেখা যখন কোডটি আসলে adjacency matrix ঘাঁটছে। আপনার কাজ হলো প্রতিটি দাবি নিজে যাচাই করা।

BFS-এর কোডে AI সাধারণত যেসব ভুল করে

BFS-এর কোড যাচাইয়ের চেকলিস্ট

• dist আর parent লেখা হয় push-এর সময়, আর প্রতিটি vertex ঠিক একবার push হয় — একটি counter দিয়ে মিলিয়ে দেখেছি
• ছোট একটি গ্রাফ হাতে dry run করে queue আর dist-এর প্রতিটি অবস্থা কোডের আউটপুটের সাথে মিলিয়েছি
• Edge case: উৎস = লক্ষ্য, অগম্য লক্ষ্য, একটিমাত্র vertex, সব দেয়ালে ঘেরা গ্রিড, ১ × n গ্রিড
• শত শত এলোমেলো ছোট গ্রাফে উত্তর মিলিয়েছি একটি brute force-এর সাথে (সব পথ গুনে দেখা, বা Floyd-Warshall) — stress testing
• queue হিসেবে O(1) pop-এর স্ট্রাকচার ব্যবহার করেছি, আর বড় ইনপুটে (১০^৬ ঘরের গ্রিড) সময় মেপেছি
• AI-এর complexity দাবি কোডের লুপ দেখে নিজে মিলিয়েছি, আর ওজনওয়ালা গ্রাফে BFS ব্যবহার হয়নি তা নিশ্চিত করেছি