Depth-first search (DFS)

১ · ধারণা — সুতো হাতে গোলকধাঁধায়

গ্রিক পুরাণে Theseus যখন Minotaur-কে মারতে গোলকধাঁধায় ঢোকেন, Ariadne তাঁর হাতে একটি সুতোর বল দেন। দরজায় এক মাথা বেঁধে সুতো খুলতে খুলতে এগোলে আর কখনো পথ হারানোর ভয় নেই — যেকোনো সময় সুতো গুটিয়ে ঠিক যে পথে এসেছেন সেই পথে ফেরা যায়। এই সরল বুদ্ধিই একটি পুরো অ্যালগরিদমের বীজ।

উনিশ শতকের ফরাসি প্রকৌশলী Charles Pierre Trémaux গোলকধাঁধা সমাধানের একটি নিয়ম দেন, যা Édouard Lucas ১৮৮২ সালে তাঁর Récréations mathématiques বইয়ে প্রকাশ করেন। Trémaux-এর পদ্ধতি মোটামুটি এরকম: প্রতিটি মোড়ে যে গলিতে ঢুকছেন তার মুখে চক দিয়ে দাগ দিন। নতুন মোড়ে পৌঁছালে একটি অদেখা গলি ধরুন। নতুন গলি দিয়ে যদি এমন মোড়ে পৌঁছান যেখানে আগেই এসেছিলেন, যে গলি দিয়ে এইমাত্র এলেন সেটি ধরেই ফিরে যান। আর কোনো মোড়ে অদেখা গলি না থাকলে, যে গলি দিয়ে এই মোড়ে প্রথম এসেছিলেন, সেটি ধরে ফিরুন। এভাবে প্রতিটি গলি সর্বোচ্চ দুবার হাঁটা হয় — একবার যেতে, একবার ফিরতে — আর গোলকধাঁধার প্রতিটি জায়গা দেখা হয়ে যায়।

কম্পিউটারের ভাষায় গোলকধাঁধা একটি graph: মোড়গুলো vertex, গলিগুলো edge (পর্ব ৩৯). আর এই পদ্ধতির নাম depth-first search বা DFS — “গভীরতা আগে” খোঁজা: পাশের সব অপশন দেখার আগে একটি পথ ধরে যতদূর সম্ভব গভীরে যাওয়া। আগের পর্বের BFS ঠিক উল্টো: সে শুরুর বিন্দুর চারপাশে স্তরে স্তরে ছড়ায়, যেন পুকুরে ঢিল ছুড়লে ঢেউ ছড়ায়। BFS একটি queue ব্যবহার করে, DFS একটি stack — এই একটি পার্থক্য থেকেই দুটির সব বৈশিষ্ট্য আলাদা হয়ে যায়।

DFS-এর আসল শক্তি শুধু “সবাইকে দেখে ফেলা” নয় — সেটি BFS-ও পারে। DFS ভ্রমণের সময় এমন একটি কাঠামো রেখে যায় (কে কার মধ্য দিয়ে আবিষ্কৃত হলো, কে কখন শুরু আর কখন শেষ হলো), যা থেকে cycle, ক্রম, দুর্বল সংযোগ — গ্রাফের অনেক গভীর প্রশ্নের উত্তর রৈখিক সময়ে বেরিয়ে আসে। এই পর্বের বেশিরভাগ অংশ সেই কাঠামো নিয়েই।

২ · Recursive DFS — যতদূর পারেন গভীরে, তারপর ফেরত

সুতোর কাজটি recursion বিনামূল্যে করে দেয় (পর্ব ৭): একটি vertex থেকে প্রতিটি অদেখা প্রতিবেশীর জন্য নিজেকে ডাকুন। ডাকা ফাংশন শেষ হলে নিয়ন্ত্রণ আপনাআপনি ঠিক আগের vertex-এ ফিরে আসে — call stack-ই সুতো। একটি visited অ্যারে চকের দাগের কাজ করে, যাতে কোনো vertex দুবার শুরু না হয়।

Pseudocode — recursive DFS (0-based, adjacency lists)

DFS(u):
    visited[u] = true                  // chalk mark: never start u again
    for each v in adj[u]:              // neighbours in list order
        if not visited[v]:
            parent[v] = u              // tree edge u -> v
            DFS(v)                     // go deeper; returns when v is done
    // all neighbours of u handled: step back to parent[u]

DFS-ALL(G):
    for each vertex s:  if not visited[s]:  DFS(s)   // one tree per start

একটি ইউনিয়নের ছয়টি গ্রাম, দুই দিকেই চলা যায় এমন রাস্তা দিয়ে যুক্ত — একটি undirected graph. প্রতিটি গ্রামের প্রতিবেশী ছোট নম্বর আগে, এই ক্রমে রাখা (adjacency list):

   0 ----- 1          adj[0] = 1 2
   |       |          adj[1] = 0 3
   2 ----- 3 ----- 4  adj[2] = 0 3 5
   |                  adj[3] = 1 2 4
   5                  adj[4] = 3
                      adj[5] = 2

যে edge দিয়ে কোনো vertex প্রথম আবিষ্কৃত হয় (parent[v] = u), সেগুলো মিলে একটি tree — DFS tree, যার root শুরুর vertex. গ্রাফ connected না হলে DFS-ALL প্রতিটি নতুন শুরু থেকে আলাদা tree বানায়; সব মিলে একটি forest. ওপরের উদাহরণে tree-টি 0–1–3, যার নিচে 3 থেকে দুই শাখা: 3–2–5 আর 3–4. একই গ্রাফে প্রতিবেশীর ক্রম বদলালে tree-ও বদলায় — DFS-এর ফল ইনপুটের ক্রমের ওপর নির্ভর করে, তাই পরীক্ষার প্রশ্নে ক্রম সবসময় বলে দেওয়া থাকে (না থাকলে ছোট নম্বর আগে ধরুন, আর সেটি লিখে দিন)।

কেন Θ(V + E)

দুটি গণনা আলাদা করে করুন। (১) DFS(u) প্রতিটি vertex-এর জন্য ঠিক একবার ডাকা হয়, কারণ ডাকার আগেই visited দেখা হয় আর ঢুকেই দাগ দেওয়া হয় — মোট Θ(V). (২) DFS(u)-এর ভেতরের লুপ u-এর adjacency list একবার পড়ে। সব vertex মিলে লুপ ঘোরে Σ deg(u) বার, যা directed গ্রাফে E আর undirected গ্রাফে 2E (প্রতিটি edge দুই প্রান্তের তালিকায় থাকে)। যোগ করলে Θ(V + E) — গ্রাফটি একবার পড়তেই যত সময় লাগে, তার ধ্রুবক গুণ। এর চেয়ে কম সম্ভব নয়, কারণ যেকোনো edge না দেখলে সেটি হয়তো একটি অদেখা অংশে যাওয়ার একমাত্র রাস্তা।

Adjacency matrix-এ “u-এর প্রতিবেশী কারা” জানতে পুরো একটি সারি (V টি ঘর) পড়তে হয়, তাই সময় Θ(V²), E যত কমই হোক। বাড়তি জায়গা: visited, parent আর recursion-এর গভীরতা — সব O(V). Recursion-এর গভীরতা worst case-এ V − 1 (একটি লম্বা শিকলের মতো গ্রাফে), আর এই সংখ্যাটিই পরের অংশের একটি বাস্তব সমস্যার মূল।

৩ · Explicit stack দিয়ে iterative DFS — আর কেন ক্রম বদলে যায়

Recursion-এর বদলে নিজেই একটি stack রাখা যায়। সবচেয়ে প্রচলিত সংস্করণ দেখতে BFS-এর মতোই, শুধু queue-এর জায়গায় stack: একটি vertex তুলুন (pop), অদেখা হলে দাগ দিন, তারপর তার সব অদেখা প্রতিবেশীকে stack-এ ঢোকান (push). একই গ্রাফে, একই adjacency list নিয়ে চালান:

ক্রম কেন বদলাল? Stack শেষ ঢোকানো প্রতিবেশীকে আগে বের করে, তাই adjacency list উল্টো দিক থেকে পড়া হয়। দুটি সহজ সমাধান: প্রতিবেশীদের উল্টো ক্রমে push করুন (তখন এই সংস্করণ recursive-এর মতো একই ক্রমে vertex দেখে), অথবা ক্রম নিয়ে মাথা না ঘামান — শুধু “সবাইকে দেখা” বা component গোনার জন্য যেকোনো ক্রমই ঠিক।

Recursive-এর হুবহু নকল — প্রতিবেশীর সূচক মনে রাখা

Finish time বা edge-এর শ্রেণি লাগলে stack-এ শুধু vertex নয়, “এই vertex-এর কততম প্রতিবেশী পর্যন্ত দেখা হয়েছে” তা-ও রাখতে হয় — recursive ফাংশনের লুপ-ভেরিয়েবল ঠিক এটিই মনে রাখত। নিচের কোড প্রতিটি vertex-এর জন্য একটি সূচক it[u] রাখে; stack-এর ওপরের vertex-এর পরের প্রতিবেশী দেখে, সাদা হলে push, আর প্রতিবেশী ফুরোলে তবেই pop — ঠিক তখনই তার finish time:

// iterative DFS with the exact recursive order and d/f times
vector<size_t> it(n, 0);            // it[u] = next neighbour index of u
vector<int> st;
for (int s = 0; s < n; ++s) {
    if (color[s] != 0) continue;
    color[s] = 1; d[s] = ++timer; st.push_back(s);
    while (!st.empty()) {
        int u = st.back();
        if (it[u] < adj[u].size()) {
            int v = adj[u][it[u]++];    // look at the next neighbour of u
            if (color[v] == 0) { color[v] = 1; d[v] = ++timer; par[v] = u; st.push_back(v); }
        } else {                        // no neighbours left: u is finished
            color[u] = 2; f[u] = ++timer; st.pop_back();
        }
    }
}

Recursion-এর গভীরতা — কখন iterative-এ যাবেন

Recursive DFS-এর recursion depth হলো DFS tree-র সবচেয়ে লম্বা root থেকে পাতা পথ — একটি শিকলের মতো গ্রাফে V − 1. প্রতিটি ডাক call stack-এ একটি frame নেয়, আর call stack-এর জায়গা সীমিত:

• Python: ডিফল্ট recursion limit সাধারণত ১০০০; ১০^৫ vertex-এর শিকলে recursive DFS RecursionError দেবে। sys.setrecursionlimit বাড়ালে আসল C stack ফুরিয়ে প্রোগ্রাম কোনো বার্তা ছাড়াই ভেঙে পড়তে পারে; কনটেস্টে অনেকে threading.stack_size দিয়ে বড় stack-এর একটি thread-এ চালান, কিন্তু সবচেয়ে নিরাপদ হলো iterative সংস্করণ।
• C++: main thread-এর stack সাধারণত কয়েক MB — Linux-এ প্রায়ই ৮ MB, Windows-এ ডিফল্ট ১ MB. ছোট frame-এ কয়েক লাখ গভীরতা চলে যায়, কিন্তু ১০^৬ গভীরতায় stack overflow (segmentation fault) খুব সম্ভব। Judge কত বড় stack দেয় তা প্ল্যাটফর্মভেদে আলাদা — সন্দেহ হলে iterative লিখুন।

নিয়মটি সহজ: V ≤ ১০^৪-এর মতো ছোট গ্রাফ বা tree-র উচ্চতা ছোট জানা থাকলে recursive (পড়তে সহজ, ভুল কম); V লাখের ঘরে আর গ্রাফ শিকলের মতো হতে পারলে — বিশেষ করে Python-এ — iterative.

৪ · Discovery আর finish time — parenthesis theorem

এবার DFS-কে আরও একটু তথ্য রাখতে দিই। একটি ঘড়ি time রাখুন, শুরুতে 0. কোনো vertex u প্রথম দেখলে d[u] = ++time — তার discovery time; u-এর সব প্রতিবেশী শেষ হলে f[u] = ++time — তার finish time. সাথে প্রতিটি vertex-এর তিনটি রং (CLRS-এর প্রচলিত নিয়ম), যাকে তিন রঙের DFS বলে:

• সাদা (W): এখনো দেখা হয়নি (d নেই)।
• ধূসর (G): দেখা হয়েছে কিন্তু শেষ হয়নি — recursion stack-এ আছে, d আছে কিন্তু f নেই।
• কালো (B): শেষ — নিজের আর নিজের নিচের সবার কাজ সারা, d আর f দুটোই আছে।

যেকোনো মুহূর্তে ধূসর vertex-গুলো মিলে ঠিক একটি পথ: root থেকে বর্তমান vertex পর্যন্ত DFS tree-র শাখা — সুতোর যে অংশ এখনো খোলা। প্রতিটি vertex দুটি করে ছাপ পায়, তাই সময় চলে 1 থেকে 2V পর্যন্ত। এবার একটি directed graph নিন — পুরান ঢাকার ছয়টি মোড়, মাঝের গলিগুলো একমুখী:

0 → 1, 3      1 → 2      2 → 0, 3      3 → (কিছু নেই)      4 → 3, 5      5 → 4

Parenthesis theorem

উপপাদ্য (parenthesis theorem): যেকোনো গ্রাফে (directed বা undirected) DFS চালালে যেকোনো দুটি vertex u আর v-এর জন্য ঠিক একটি সত্য: (ক) [d[u], f[u]] আর [d[v], f[v]] সম্পূর্ণ আলাদা, আর কেউ কারও উত্তরসূরি নয়; (খ) [d[v], f[v]] পুরোটা [d[u], f[u]]-এর ভেতরে, আর v হলো u-এর descendant (উত্তরসূরি); (গ) উল্টোটা — u-এর ব্যবধান v-এর ভেতরে, u হলো v-এর উত্তরসূরি। আংশিক জোড়া — যেমন d[u] < d[v] < f[u] < f[v] — কখনো হয় না।

প্রমাণ: ধরুন d[u] < d[v] (উল্টোটা প্রতিসম)। দুটি ক্ষেত্র। প্রথম: d[v] < f[u] — অর্থাৎ v আবিষ্কৃত হলো যখন u ধূসর, তাই u তখন recursion stack-এ, আর v আবিষ্কৃত হয়েছে u-এর ডাকের ভেতরের কোনো ডাকে — v হলো u-এর উত্তরসূরি। Recursion-এ ভেতরের ডাক বাইরেরটির আগে শেষ হয়, তাই f[v] < f[u]: v-এর ব্যবধান পুরোটা u-এর ভেতরে — (খ)। দ্বিতীয়: f[u] < d[v] — u শেষ হয়ে গেছে v দেখার আগেই। তাহলে d[u] < f[u] < d[v] < f[v]: ব্যবধান দুটি আলাদা। কেউ কারও উত্তরসূরি নয়, কারণ উত্তরসূরি হলে তো প্রথম ক্ষেত্রের মতো তার ডাকের ভেতরেই আবিষ্কৃত হতো — (ক)। ∎

৫ · Edge-এর শ্রেণিবিভাগ — tree, back, forward, cross

DFS প্রতিটি edge (u, v) প্রথমবার পরীক্ষা করার মুহূর্তে v-এর রং দেখেই edge-টির শ্রেণি বলে দেওয়া যায় — একে বলে edge classification:

লক্ষ করুন, cross edge সবসময় “পরে” আবিষ্কৃত vertex থেকে “আগে” শেষ হওয়া vertex-এ যায় — কখনো উল্টো নয়। কেন? যদি u আগে আবিষ্কৃত হতো আর u → v edge থাকত, তবে u ধূসর থাকতেই DFS u-এর তালিকা থেকে v দেখত, তখন v সাদা হলে v u-এর উত্তরসূরি হয়ে যেত। আর একটি ব্যবহারিক তথ্য: back edge ছাড়া বাকি তিন শ্রেণিতে f[v] < f[u]; শুধু back edge-এ f[v] ≥ f[u]. পর্ব ৪২-এর topological sort এই সত্যের ওপর দাঁড়িয়ে।

Undirected গ্রাফে শুধু tree আর back

উপপাদ্য: undirected গ্রাফের DFS-এ প্রতিটি edge হয় tree edge, নয়তো back edge — forward বা cross edge থাকে না। (Undirected গ্রাফে প্রতিটি edge দুবার দেখা যায়, তাই শ্রেণি ধরা হয় যে দিক থেকে প্রথম দেখা হলো সেই অনুযায়ী।) প্রমাণ: edge {u, v}, আর ধরুন d[u] < d[v]. v হলো u-এর প্রতিবেশী, তাই u শেষ হওয়ার আগে DFS অবশ্যই v-কে দেখবে (u-এর তালিকায় v আছে) — অর্থাৎ v আবিষ্কৃত আর শেষ হয় u ধূসর থাকতেই। এখন দুটি সম্ভাবনা। যদি edge-টি প্রথম দেখা হয় u-এর দিক থেকে, তখনো v সাদা (নইলে v-এর দিক থেকে আগেই দেখা হতো, কারণ v আবিষ্কৃত হলেই নিজের তালিকা দেখে) — তাই tree edge. যদি প্রথম দেখা হয় v-এর দিক থেকে, তখন u ধূসর — back edge. ∎ অংশ ২-এর ডায়াগ্রামে ঠিক এটিই দেখেছেন: ছয়টি edge-এর পাঁচটি tree, একটি (2 → 0) back.

পুরো কোড — সময়, শ্রেণি আর প্রতিটি back edge-এর cycle

এবার অংশ ৪-এর একমুখী গলির গ্রাফে পুরো DFS-ALL. প্রতিটি edge পরীক্ষার সময় তার শ্রেণি ছাপা হয়; back edge u → v পেলে par ধরে u থেকে v পর্যন্ত ওপরে উঠে cycle-টিও দেখানো হয় (v ধূসর, তাই v নিশ্চিতভাবে u-এর পূর্বপুরুষ — উঠলে পৌঁছাবেই)। শেষে প্রতিটি vertex-এর d, f, parent আর বন্ধনীর মালা।

#include <iostream>
#include <string>
#include <vector>
using namespace std;
const vector<vector<int>> adj = {{1, 3}, {2}, {0, 3}, {}, {3, 5}, {4}};  // one-way lanes
const int n = adj.size();
vector<int> color(n, 0), d(n, 0), f(n, 0), par(n, -1);   // 0 white, 1 grey, 2 black
int timer = 0;
string paren;
void dfs(int u) {
    color[u] = 1; d[u] = ++timer; paren += "(" + to_string(u) + " ";
    for (int v : adj[u]) {
        string kind;
        if (color[v] == 0) kind = "tree";
        else if (color[v] == 1) kind = "back";              // v is still on the path
        else kind = d[u] < d[v] ? "forward" : "cross";      // v is already finished
        cout << kind << string(8 - kind.size(), ' ') << u << " -> " << v;
        if (kind == "back") {                                // walk up from u to v
            string cyc = to_string(u);
            for (int x = u; x != v; x = par[x]) cyc = to_string(par[x]) + " -> " + cyc;
            cout << "   cycle: " << cyc << " -> " << v;
        }
        cout << '\n';
        if (color[v] == 0) { par[v] = u; dfs(v); }
    }
    color[u] = 2; f[u] = ++timer; paren += to_string(u) + ") ";
}
int main() {
    for (int s = 0; s < n; ++s)
        if (color[s] == 0) dfs(s);
    for (int v = 0; v < n; ++v)
        cout << v << ": d=" << d[v] << " f=" << f[v] << " parent=" << par[v] << '\n';
    paren.pop_back();
    cout << paren << '\n';
}

tree    0 -> 1
tree    1 -> 2
back    2 -> 0   cycle: 0 -> 1 -> 2 -> 0
tree    2 -> 3
forward 0 -> 3
cross   4 -> 3
tree    4 -> 5
back    5 -> 4   cycle: 4 -> 5 -> 4
0: d=1 f=8 parent=-1
1: d=2 f=7 parent=0
2: d=3 f=6 parent=1
3: d=4 f=5 parent=2
4: d=9 f=12 parent=-1
5: d=10 f=11 parent=4
(0 (1 (2 (3 3) 2) 1) 0) (4 (5 5) 4)

adj = [[1, 3], [2], [0, 3], [], [3, 5], [4]]   # one-way lanes
n = len(adj)
color, d, f, par = [0] * n, [0] * n, [0] * n, [-1] * n   # 0 white, 1 grey, 2 black
timer = 0
paren = []

def dfs(u):
    global timer
    color[u] = 1
    timer = d[u] = timer + 1                       # discovery time
    paren.append(f"({u}")
    for v in adj[u]:
        if color[v] == 0:
            kind = "tree"
        elif color[v] == 1:
            kind = "back"                              # v is still on the path
        else:
            kind = "forward" if d[u] < d[v] else "cross"   # v is already finished
        line = f"{kind:<8}{u} -> {v}"
        if kind == "back":                             # walk up from u to v
            cyc, x = [u], u
            while x != v:
                x = par[x]
                cyc.append(x)
            line += "   cycle: " + " -> ".join(map(str, reversed(cyc))) + f" -> {v}"
        print(line)
        if color[v] == 0:
            par[v] = u
            dfs(v)
    color[u] = 2
    timer = f[u] = timer + 1                       # finish time
    paren.append(f"{u})")

for s in range(n):
    if color[s] == 0:
        dfs(s)
for v in range(n):
    print(f"{v}: d={d[v]} f={f[v]} parent={par[v]}")
print(" ".join(paren))

tree    0 -> 1
tree    1 -> 2
back    2 -> 0   cycle: 0 -> 1 -> 2 -> 0
tree    2 -> 3
forward 0 -> 3
cross   4 -> 3
tree    4 -> 5
back    5 -> 4   cycle: 4 -> 5 -> 4
0: d=1 f=8 parent=-1
1: d=2 f=7 parent=0
2: d=3 f=6 parent=1
3: d=4 f=5 parent=2
4: d=9 f=12 parent=-1
5: d=10 f=11 parent=4
(0 (1 (2 (3 3) 2) 1) 0) (4 (5 5) 4)

নিজের গ্রাফে চালিয়ে দেখুন

নিচের ভিজ্যুয়ালাইজারে u>v আকারে edge লিখে (vertex 0–11) “নতুন গ্রাফ” চাপুন, তারপর ধাপে ধাপে এগোন। প্রতিটি বৃত্তে vertex-এর নম্বর আর d/f; সাদা, ধূসর, কালো রং; নিচে প্রতিটি edge-এর শ্রেণি (সবুজ tree, লাল back, নীল forward, বেগুনি cross রঙে)। শুরুতে ওপরের গ্রাফটিই দেওয়া।

const $ = id => document.getElementById(id);
let snaps = [], at = 0;                        // one snapshot per DFS event
function build() {
  const pairs = $("ed").value.trim().split(/[\s,]+/).filter(Boolean).map(s => s.split(">").map(Number));
  if (!pairs.length || pairs.some(p => p.length !== 2 || p.some(x => !Number.isInteger(x) || x < 0 || x > 11)))
    return void ($("msg").textContent = "format: u>v pairs, vertices 0..11");
  const n = 1 + Math.max(...pairs.flat()), adj = Array.from({ length: n }, () => []);
  for (const [u, v] of pairs) adj[u].push(v);
  adj.forEach(a => a.sort((x, y) => x - y));
  const col = Array(n).fill(0), d = Array(n).fill(0), f = Array(n).fill(0), path = [], kinds = [];
  let t = 0;
  snaps = [];
  const snap = msg => snaps.push({ msg, col: [...col], d: [...d], f: [...f], path: [...path], kinds: [...kinds] });
  function visit(u) {                          // recursive DFS: white 0, grey 1, black 2
    col[u] = 1; d[u] = ++t; path.push(u); snap(`t=${t}: discover ${u}`);
    for (const v of adj[u]) {
      const k = col[v] === 0 ? "tree" : col[v] === 1 ? "back" : d[u] < d[v] ? "forward" : "cross";
      kinds.push(`${u}>${v} ${k}`); snap(`edge ${u}->${v}: ${k}`);
      if (col[v] === 0) visit(v);
    }
    col[u] = 2; f[u] = ++t; path.pop(); snap(`t=${t}: finish ${u}`);
  }
  for (let s = 0; s < n; s++) if (col[s] === 0) visit(s);
  at = 0; show();
}
function show() {
  const s = snaps[at];
  $("vs").innerHTML = s.col.map((c, v) => `<span class="v c${c}">${v}<small>${s.d[v] || "."}/${s.f[v] || "."}</small></span>`).join("");
  $("ek").innerHTML = s.kinds.map(k => `<span class="${k.split(" ")[1]}">${k}</span>`).join(" ");
  $("msg").textContent = `step ${at + 1}/${snaps.length}: ${s.msg} | grey path: ${s.path.join(" ") || "-"}`;
}
$("nx").onclick = () => { if (at < snaps.length - 1) { at++; show(); } };
$("pv").onclick = () => { if (at > 0) { at--; show(); } };
$("go").onclick = build;
build();
snaps.forEach((s, i) => console.log(`${String(i + 1).padStart(2)}. ${s.msg}`));

 1. t=1: discover 0
 2. edge 0->1: tree
 3. t=2: discover 1
 4. edge 1->2: tree
 5. t=3: discover 2
 6. edge 2->0: back
 7. edge 2->3: tree
 8. t=4: discover 3
 9. t=5: finish 3
10. t=6: finish 2
11. t=7: finish 1
12. edge 0->3: forward
13. t=8: finish 0
14. t=9: discover 4
15. edge 4->3: cross
16. edge 4->5: tree
17. t=10: discover 5
18. edge 5->4: back
19. t=11: finish 5
20. t=12: finish 4

৬ · Cycle detection — undirected-এ parent, directed-এ তিন রং

Undirected গ্রাফ: “দেখা প্রতিবেশী, কিন্তু parent নয়”

Undirected গ্রাফে back edge মানেই cycle, আর অংশ ৫ বলছে tree আর back ছাড়া কিছু নেই। কিন্তু একটি ফাঁদ আছে: v থেকে তার parent u-তে ফেরার edge-টিও “দেখা প্রতিবেশী” — অথচ সেটি একই tree edge, উল্টো দিক থেকে। তাই নিয়ম: দেখা প্রতিবেশী পেলে, সে parent না হলে তবেই cycle.

Pseudocode — cycle in an undirected graph (0-based)

hasCycle(u, p):                  // p = the vertex we came from (-1 at a root)
    seen[u] = true
    for each v in adj[u]:
        if not seen[v]:
            if hasCycle(v, u): return true
        else if v != p:          // seen, and not the edge we arrived by
            return true          // back edge u - v closes a cycle
    return false
// run hasCycle(s, -1) for every unseen s; time O(V + E)

সতর্কতা: u আর p-এর মধ্যে দুটি আলাদা রাস্তা থাকলে (multigraph — যেমন দুই গ্রামের মধ্যে একটি পাকা রাস্তা আর একটি সাঁকো), সেটি দৈর্ঘ্য ২-এর একটি cycle, কিন্তু v != p শর্ত দুটিকেই বাদ দেয়। সমাধান: parent vertex নয়, যে edge দিয়ে এসেছেন তার নম্বর মনে রাখুন, আর শুধু সেই edge-টি বাদ দিন। এই কৌশল পর্ব ৪৬-এর bridge খোঁজাতেও লাগবে। আরেকটি বিকল্প: পর্ব ৩৩-এর DSU, যা edge একে একে নিয়ে একই প্রশ্নের উত্তর দেয়।

Directed গ্রাফ: back edge ⇔ cycle

Directed গ্রাফে “দেখা vertex পেলেই cycle” ভুল — forward আর cross edge-ও দেখা (কালো) vertex-এ যায়, অথচ কোনো cycle বানায় না। সঠিক নিয়মটি রঙে লুকিয়ে আছে:

প্রমাণ (⇐): back edge u → v মানে v ধূসর, অর্থাৎ u-এর পূর্বপুরুষ: DFS tree-তে v থেকে u পর্যন্ত একটি পথ আছে। সেই পথ আর u → v মিলে একটি cycle. প্রমাণ (⇒): ধরুন গ্রাফে একটি cycle c আছে। c-এর vertex-গুলোর মধ্যে যে সবার আগে আবিষ্কৃত হলো, তাকে v বলুন, আর c-তে v-এর ঠিক আগের vertex-কে u (অর্থাৎ u → v একটি edge আছে)। d[v] মুহূর্তে c-এর বাকি সব vertex সাদা, তাই v থেকে cycle ধরে u পর্যন্ত একটি সব-সাদা পথ আছে। White-path theorem অনুযায়ী u হবে v-এর উত্তরসূরি — u আবিষ্কৃত আর শেষ হবে v ধূসর থাকতেই। তাই DFS যখন u → v edge পরীক্ষা করবে, v তখনো ধূসর: back edge. ∎ খেয়াল করুন, DFS কোথা থেকে শুরু করল বা প্রতিবেশী কোন ক্রমে, তাতে কিছু যায় আসে না — cycle থাকলে back edge আসবেই।

Pseudocode — cycle in a directed graph, stop at the first back edge (0-based)

visit(u):                        // colour: 0 white, 1 grey, 2 black
    colour[u] = 1
    for each v in adj[u]:
        if colour[v] == 1: report cycle v -> ... -> u -> v (walk parent from u up to v); return true
        if colour[v] == 0:
            parent[v] = u
            if visit(v): return true
    colour[u] = 2                // finished: no cycle through u can be found later
    return false

নিচের গ্রাফে একটি “হীরা” (0 → 1 → 3 আর 0 → 2 → 3) আছে, যেখানে দুটি পথ একই vertex-এ মেলে কিন্তু কোনো cycle নেই; আর আলাদা একটি সত্যিকারের cycle. Edge: 0 → 1, 2; 1 → 3; 2 → 3, 4; 4 → 2.

বাস্তবে এই প্রশ্ন প্রায় সবখানে: কোর্সের prerequisite-এ চক্র আছে কি না (A-র আগে B, B-র আগে A হলে কেউ ভর্তি হতে পারবে না), Excel-এর সূত্রে circular reference, software package-এর dependency-তে চক্র, অপারেটিং সিস্টেমে deadlock (কে কার জন্য অপেক্ষা করছে, তার গ্রাফে চক্র)। সব ক্ষেত্রে একই তিন রঙের DFS, Θ(V + E).

৭ · Component, flood fill আর পথ খোঁজা

Connected component গোনা

Undirected গ্রাফে DFS-ALL যতবার নতুন শুরু করে, ঠিক ততটি connected component — প্রতিটি DFS tree একটি component-এর সব vertex ধরে, কারণ শুরুর vertex থেকে যাওয়া যায় এমন সবাইকে DFS দেখবেই। প্রতিটি vertex-এ component-এর নম্বর লিখে রাখলে পরে “u আর v কি যুক্ত?” প্রশ্নের উত্তর O(1)-এ। গ্রাফ না বদলালে এটি DSU-এর চেয়েও সহজ; বদলাতে থাকলে (edge যোগ হতে থাকলে) DSU (পর্ব ৩৩).

Flood fill — গ্রামের মানচিত্রে পুকুর গোনা

একটি ইউনিয়ন পরিষদ জানতে চায় এলাকায় কয়টি আলাদা পুকুর আছে, মাছ চাষের জরিপের জন্য। স্যাটেলাইট মানচিত্রটি একটি গ্রিড: W = পানি, . = মাটি। পাশাপাশি (ওপর, নিচ, বাঁ, ডান) পানির ঘরগুলো মিলে একটি পুকুর। এখানে গ্রাফটি আলাদা করে বানাতে হয় না — প্রতিটি ঘর একটি vertex, পাশের ঘরগুলো তার প্রতিবেশী (grid graph). প্রতিটি অদেখা পানির ঘর পেলে গণনা এক বাড়ান আর সেখান থেকে DFS চালিয়ে পুরো পুকুরটিতে দাগ দিন — যেন Paint-এর বালতি দিয়ে একটি অংশ রং করা। এটিই flood fill.

// count ponds: 'W' = water, '.' = land; 4 directions (up, down, left, right)
int fill(vector<string>& g, int r, int c) {             // returns the pond size
    if (r < 0 || r >= (int)g.size() || c < 0 || c >= (int)g[0].size() || g[r][c] != 'W') return 0;
    g[r][c] = '#';                                         // mark BEFORE recursing
    return 1 + fill(g, r - 1, c) + fill(g, r + 1, c) + fill(g, r, c - 1) + fill(g, r, c + 1);
}
// for every cell (r, c) in row-major order: if g[r][c] == 'W' -> ++ponds; size = fill(g, r, c)

তিনটি সতর্কতা। (১) Recursion-এর আগে দাগ দিন — পরে দিলে দুটি পাশাপাশি পানির ঘর একে অন্যকে অনন্তকাল ডাকতে থাকবে। (২) ৪ না ৮ দিক — কোণাকুণি ছোঁয়া ঘরকে একই পুকুর ধরবেন কি না, তা সমস্যা বলে দেয়; উত্তর পুরো বদলে যেতে পারে (অনুশীলন ৩)। (৩) গভীরতা — ১০০০ × ১০০০ গ্রিডে একটি সাপের মতো আঁকাবাঁকা পুকুর থাকলে recursion ১০^৬ গভীর হতে পারে; তখন explicit stack বা BFS. জায়গা worst case O(R · C).

পথ খোঁজা — কিন্তু সবচেয়ে ছোট নয়!

s থেকে t-তে যাওয়া যায় কি না, আর গেলে কোন পথে — DFS এটি সহজেই বলে: s থেকে DFS চালান, parent রাখুন; t দেখা হলে t থেকে parent ধরে s পর্যন্ত উঠে উল্টে দিন। কিন্তু অংশ ২-এর গ্রাফে 0 থেকে 2-এর পথ চাইলে DFS দেবে 0 → 1 → 3 → 2 (৩টি রাস্তা), অথচ সরাসরি রাস্তা 0 – 2 আছে (১টি)। DFS প্রথম যে পথে পৌঁছায় সেটিই দেয়, আর সেটি তার গভীরে যাওয়ার অভ্যাসের কারণে প্রায়ই লম্বা। ওজনহীন গ্রাফে সবচেয়ে ছোট পথ চাইলে BFS (পর্ব ৪০); ওজনসহ হলে Dijkstra (পর্ব ৪৩).

৮ · BFS বনাম DFS, আর সামনের প্রয়োগ

সংক্ষেপে: “কত কাছে?” প্রশ্নে BFS, “কাঠামোটা কেমন?” প্রশ্নে DFS. শুধু সবাইকে দেখা বা component গোনায় যেকোনোটি; তখন যেটি লিখতে আর ডিবাগ করতে স্বচ্ছন্দ, সেটিই।

সামনের পর্বগুলোতে DFS

৯ · AI-এর যুগে DFS — ছোট কোড, সূক্ষ্ম ভুল

“DFS লিখে দাও” বললে যেকোনো AI সহকারী দশ লাইনের পরিষ্কার কোড দেবে, আর ছোট উদাহরণে সেটি ঠিকই চলবে। DFS-এর ভুল সাধারণত লুকিয়ে থাকে বিশেষ গঠনের গ্রাফে — হীরা, multigraph, লম্বা শিকল, একাধিক component — যেগুলো AI-এর নিজের পরীক্ষায় থাকে না। আর ব্যাখ্যায় AI প্রায়ই নিশ্চিত সুরে বলে “DFS shortest path দেয়” বা “iterative আর recursive DFS একই ক্রমে চলে”, যা সাধারণভাবে সত্য নয়।

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

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

• প্রতিটি vertex থেকে DFS-ALL চালিয়েছি, শুধু 0 থেকে নয়; একাধিক component-এর গ্রাফে পরীক্ষা করেছি
• Directed cycle-এ ধূসর আর কালো আলাদা করেছি; হীরা আর self-loop দুটোই পরীক্ষা করেছি
• Edge case: একটি vertex, কোনো edge নেই, সম্পূর্ণ গ্রাফ, multigraph, লম্বা শিকল
• ছোট এলোমেলো গ্রাফে ফল মিলিয়েছি একটি brute force-এর সাথে (যেমন সব vertex থেকে পৌঁছানো যায় কি না দেখে cycle যাচাই) — stress testing
• Recursion-এর গভীরতা হিসাব করেছি; Python-এ বা ১০^৫+ গভীরতায় iterative সংস্করণ রেখেছি
• AI-এর complexity দাবি (Θ(V + E) list-এ, Θ(V²) matrix-এ) নিজে গুনে মিলিয়েছি; “DFS shortest path দেয়” দাবি বাতিল করেছি