গ্রাফ — সংযোগের মানচিত্র, আর তাতে পথ খোঁজার দুই কৌশল (BFS ও DFS)

১ · গ্রাফ — চারপাশের সব সংযোগের এক ভাষা

ধরুন আপনি মিরপুরে থাকেন, যাবেন মতিঝিল। Google Maps খুললেন, কয়েক মুহূর্তেই রাস্তা দেখিয়ে দিল। Facebook খুললেন, পাশে লেখা “People you may know” — এমন কয়েকজন, যাঁদের সাথে আপনার অনেক বন্ধু মিলে যায়। ল্যাপটপে একটি সফটওয়্যার ইনস্টল করলেন, সে নিজেই আরও দশটি দরকারি প্যাকেজ খুঁজে এনে ঠিক ক্রমে বসিয়ে দিল।

তিনটি একেবারে আলাদা কাজ। কিন্তু ভেতরে একই প্রশ্ন: “কে কার সাথে যুক্ত, আর এক জায়গা থেকে আরেক জায়গায় কীভাবে পৌঁছাব?” এই ধরনের প্রশ্নের জন্য কম্পিউটার বিজ্ঞানের যে কাঠামো, তার নাম graph (গ্রাফ)।

এখানে “graph” মানে স্কুলের x-y অক্ষের লেখচিত্র নয়। এখানে গ্রাফের দুটি মাত্র উপাদান:

• Vertex (বা node): জিনিসগুলো — একটি স্টেশন, একজন মানুষ, একটি ওয়েব পেজ, একটি কোর্স।
• Edge: দুটি জিনিসের মাঝের সংযোগ — দুই স্টেশনের মাঝের লাইন, দুজনের বন্ধুত্ব, এক পেজ থেকে আরেক পেজের লিংক।

২ · গ্রাফের রকমফের — দিক, ওজন আর ঘুরে আসা পথ

সব গ্রাফ এক রকম নয়। কোড লেখার আগে তিনটি প্রশ্নের উত্তর জেনে নিতে হয়, কারণ এর ওপর নির্ভর করে কোন algorithm কাজ করবে।

আরও দুটি শব্দ এই পর্বে বারবার আসবে। একটি vertex-এর সাথে কয়টি edge যুক্ত, তাকে বলে তার degree. আর কয়েকটি edge পেরিয়ে যদি আবার শুরুর vertex-এ ফিরে আসা যায়, সেই ঘুরে আসা পথটিকে বলে cycle.

এই পর্বের সব উদাহরণে আমরা একটি কাল্পনিক ছোট রুট-মানচিত্র ব্যবহার করব — ঢাকার সাতটি পরিচিত এলাকা, আর তাদের মাঝে আটটি সরাসরি বাস/মেট্রো সংযোগ। (বাস্তবের রুট এমন নয়; শুধু বোঝার সুবিধার জন্য বানানো।) প্রতিটি এলাকার একটি নম্বর আছে, কারণ C-তে আমরা vertex-কে নম্বর দিয়েই চিনব:

 [0] Mirpur ---- [1] Agargaon ---- [3] Farmgate ---- [5] Shahbag
  |                                 |                 |
  |                                 |                 |
 [2] Mohakhali ------------------- [4] Gulshan ----- [6] Motijheel

এখানে V (vertex-এর সংখ্যা) = ৭, আর E (edge-এর সংখ্যা) = ৮। গ্রাফটি undirected আর ওজনহীন — প্রতিটি সংযোগ মানে “এক স্টপেজ”। খেয়াল করুন, এতে অন্তত দুটি ছোট cycle আছে।

৩ · C-তে গ্রাফ রাখার দুই উপায় — matrix আর list

কাগজে গ্রাফ আঁকা সহজ। কিন্তু কম্পিউটারের মেমরিতে তো ছবি রাখা যায় না — রাখতে হবে সংখ্যা। প্রশ্ন একটাই: “কে কার সাথে যুক্ত” — এই তথ্যটি কোন আকারে রাখব? দুটি জনপ্রিয় উত্তর আছে, আর দুটিই আপনি আগের পর্বগুলোতে শেখা জিনিস দিয়ে বানাতে পারবেন।

• Adjacency matrix: V × V মাপের একটি 2D array (পর্ব ২১)। adj[i][j] = 1 মানে i আর j যুক্ত, 0 মানে নয়। ঠিক যেন বাসের ভাড়ার চার্ট — বাঁ দিকে “কোথা থেকে”, ওপরে “কোথায়”।
• Adjacency list: প্রতিটি vertex-এর জন্য শুধু তার প্রতিবেশীদের একটি তালিকা — linked list (পর্ব ৩৩) বা dynamic array (পর্ব ২০) দিয়ে। ঠিক যেন মোবাইলের contact list — শুধু যাঁদের চেনেন, তাঁদের নাম।

নিচের ডায়াগ্রামে একই রুট-মানচিত্র দুই আকারে দেখুন, আর ডান পাশে মেমরির হিসাব খেয়াল করুন:

 [0] Mirpur -- [1] Agargaon -- [3] Farmgate -- [5] Shahbag
  |                             |               |
 [2] Mohakhali --------------- [4] Gulshan --- [6] Motijheel

      0 1 2 3 4 5 6
  0:  0 1 1 0 0 0 0   Mirpur
  1:  1 0 0 1 0 0 0   Agargaon
  2:  1 0 0 0 1 0 0   Mohakhali
  3:  0 1 0 0 1 1 0   Farmgate
  4:  0 0 1 1 0 0 1   Gulshan
  5:  0 0 0 1 0 0 1   Shahbag
  6:  0 0 0 0 1 1 0   Motijheel

      0 1 2 3 4 5 6
  3:  0 1 0 0 1 1 0   Farmgate
                ↑ adj[3][5] == 1 → হ্যাঁ, এক ধাপেই উত্তর

  0 Mirpur    → 1 → 2
  1 Agargaon  → 0 → 3
  2 Mohakhali → 0 → 4
  3 Farmgate  → 1 → 4 → 5
  4 Gulshan   → 2 → 3 → 6
  5 Shahbag   → 3 → 6
  6 Motijheel → 4 → 5

Matrix : 100000 x 100000 = 10,000,000,000 ঘর
         1 byte করে ধরলেও  ≈ 10 GB  (প্রায় সবই 0)
List   : 100000 head (8 byte) + 400000 entry (16 byte)
         মোট               ≈ 7 MB

কোনটি কখন নেবেন, তার উত্তর নির্ভর করে গ্রাফটি কতটা “ঘন”। যে গ্রাফে প্রায় সবাই সবার সাথে যুক্ত, তাকে বলে dense graph; আর যেখানে প্রত্যেকে মাত্র অল্প কয়েকজনের সাথে যুক্ত, তাকে বলে sparse graph.

C-তে adjacency list-এর একটি সাধারণ রূপ দেখতে এমন — পর্ব ৩৩-এর linked list-এর node, শুধু ভেতরে থাকে প্রতিবেশীর নম্বর:

struct Edge {
    int to;               /* প্রতিবেশী vertex-এর নম্বর */
    struct Edge *next;    /* এই vertex-এর পরের প্রতিবেশী */
};
struct Edge *head[V];     /* প্রতিটি vertex-এর তালিকার মাথা, শুরুতে NULL */

৪ · BFS — পুকুরে ঢিল ছোড়ার মতো, স্তরে স্তরে খোঁজা

শান্ত পুকুরে একটি ঢিল ফেলুন। প্রথমে ছোট একটি বৃত্ত, তারপর তার বাইরে আরেকটি, তারপর আরও বড়। ঢেউ কখনো একদিকে লাফিয়ে দূরে চলে যায় না — সব দিকে সমানভাবে, স্তরে স্তরে ছড়ায়। BFS (Breadth-First Search) ঠিক এভাবে গ্রাফ খোঁজে: আগে শুরুর জায়গা থেকে ১ ধাপ দূরের সবাই, তারপর ২ ধাপ দূরের সবাই, তারপর ৩ ধাপ।

এই “আগে এলে আগে” ক্রম রাখার জন্য দরকার একটি queue (পর্ব ৩৪) — বাসস্ট্যান্ডের লাইনের মতো, যে আগে দাঁড়িয়েছে সে আগে উঠবে। BFS-এর পুরো নিয়ম মাত্র চার লাইনে:

এবার Mirpur থেকে BFS চালাই। নিচে প্রতিটি এলাকার পাশে তার দূরত্ব (কয় স্টপেজ) লেখা আছে। ঝাপসা এলাকাগুলো এখনো খুঁজে পাওয়া যায়নি; লাল দাগের এলাকাটি এই ধাপে queue থেকে বের হয়েছে:

 [0] Mirpur -- [1] Agargaon -- [3] Farmgate -- [5] Shahbag
  |                             |               |
 [2] Mohakhali --------------- [4] Gulshan --- [6] Motijheel

এবার এই পুরো কাজটি C-তে। কোডে আলাদা visited array রাখিনি — dist[v] == -1 মানেই “এখনো খুঁজে পাওয়া যায়নি”। আর queue বানানো হয়েছে একটি সাধারণ array আর দুটি index (head, tail) দিয়ে, যেমনটি পর্ব ৩৪-এ দেখেছেন:

#include <stdio.h>
#define N 7
const char *name[N] = {"Mirpur", "Agargaon", "Mohakhali", "Farmgate", "Gulshan", "Shahbag", "Motijheel"};
int adj[N][N];

int main(void) {
    int e[8][2] = {{0,1}, {0,2}, {1,3}, {2,4}, {3,4}, {3,5}, {4,6}, {5,6}};
    for (int i = 0; i < 8; i++) adj[e[i][0]][e[i][1]] = adj[e[i][1]][e[i][0]] = 1;
    int dist[N], queue[N], head = 0, tail = 0;
    for (int i = 0; i < N; i++) dist[i] = -1;        /* -1 = not visited yet */
    dist[0] = 0; queue[tail++] = 0;                   /* start at Mirpur */
    while (head < tail) {
        int u = queue[head++];                        /* take from the front */
        for (int v = 0; v < N; v++)
            if (adj[u][v] && dist[v] == -1) { dist[v] = dist[u] + 1; queue[tail++] = v; }
    }
    for (int i = 0; i < N; i++) printf("%-10s %d stops\n", name[i], dist[i]);
    return 0;
}

৫ · কেন BFS সবচেয়ে কম ধাপের পথ দেয় — আর কখন দেয় না

ওপরের ফলাফলটি কাকতালীয় নয়। BFS যেকোনো ওজনহীন গ্রাফে নিশ্চিতভাবে shortest path — সবচেয়ে কম edge-এর পথ — দেয়। যুক্তিটি সহজ:

• Queue-তে সবসময় আগে দূরত্ব d-এর সবাই, তারপর দূরত্ব d + 1-এর সবাই — কখনো উল্টো নয়।
• তাই একটি vertex-কে প্রথমবার যে স্তরে পাওয়া যায়, তার চেয়ে কাছের কোনো স্তরে সে থাকতে পারে না — থাকলে আগের ঢেউয়েই ধরা পড়ত।
• আর visited চিহ্ন থাকায় পরে কেউ তার দূরত্ব বাড়িয়ে নষ্ট করতে পারে না।

শুধু দূরত্ব নয়, পুরো পথটি পেতে চাইলে আরেকটি ছোট array রাখুন — parent array. নতুন vertex v-কে যখন u থেকে পাওয়া যায়, লিখে রাখুন parent[v] = u. শেষে গন্তব্য থেকে parent ধরে ধরে উল্টো হাঁটলে শুরুতে পৌঁছাবেন — ঠিক যেমন ধাপ ৮-এ আমরা Motijheel থেকে Mirpur-এ ফিরেছিলাম।

৬ · DFS — গোলকধাঁধায় এক দেয়াল ধরে গভীরে যাওয়া

এবার অন্য একটি কৌশল। ধরুন আপনি একটি গোলকধাঁধার ভেতরে, হাতে একটি চক। প্রতিটি মোড়ে চক দিয়ে দাগ দেন (visited). একটি পথ ধরে যতদূর যাওয়া যায় এগিয়ে যান। সামনে দেয়াল, বা সব রাস্তাই দাগ দেওয়া? তাহলে শেষ যে মোড়ে একটি না-দেখা রাস্তা ছিল, সেখানে ফিরে আসুন, আর সেই রাস্তা ধরুন। একে বলে backtracking, আর এই পুরো কৌশলটির নাম DFS (Depth-First Search).

BFS-এর “আগে এলে আগে” ক্রমের জন্য লাগত queue. DFS-এর “সবশেষে যেখানে এসেছি, সেখান থেকেই আবার শুরু” ক্রমের জন্য লাগে উল্টোটি — stack (পর্ব ৩৪)। আর recursion-এ (পর্ব ১৫) এই stack আমাদের ফ্রি দেওয়া থাকে: প্রতিটি ফাংশন কল call stack-এ একটি নতুন frame রাখে, আর ফাংশন শেষ হলে আগের জায়গায় ফিরে যায়। তাই recursive DFS মাত্র কয়েক লাইনের:

void dfs(int u) {
    visited[u] = 1;                       /* চক দিয়ে দাগ */
    for (int v = 0; v < N; v++)
        if (adj[u][v] && !visited[v])
            dfs(v);                       /* গভীরে যাও; ফিরে এলে পরের রাস্তা */
}                                         /* সব রাস্তা শেষ → ফেরত (backtrack) */

একই রুট-মানচিত্রে Mirpur থেকে DFS চালাই। প্রতিবেশীদের দেখা হবে ছোট নম্বর থেকে বড় নম্বরের ক্রমে। ডান পাশে call stack কতটা লম্বা হচ্ছে, খেয়াল করুন:

 [0] Mirpur -- [1] Agargaon -- [3] Farmgate -- [5] Shahbag
  |                             |               |
 [2] Mohakhali --------------- [4] Gulshan --- [6] Motijheel

DFS কোথায় কাজে লাগে

৭ · DFS দিয়ে cycle ধরা, আর কোর্সের সঠিক ক্রম সাজানো

আপনার কম্পিউটারে apt, npm বা pip দিয়ে কিছু ইনস্টল করলে package manager প্রথমে একটি directed গ্রাফ বানায়: “app-এর লাগবে web আর log; web-এর লাগবে json…”। তারপর ঠিক করে কোনটি আগে বসাতে হবে। কিন্তু যদি json-এর লাগে util, আর util-এর লাগে web, আর web-এর লাগে json? তাহলে কেউই আগে বসতে পারবে না — একটি cycle. ভালো package manager বা build system তখন ইনস্টল শুরুই করে না, স্পষ্ট জানিয়ে দেয় কোথায় চক্র।

Directed গ্রাফে cycle ধরতে DFS-এর একটি ছোট উন্নতি লাগে। শুধু “দেখেছি/দেখিনি” নয়, তিনটি অবস্থা রাখতে হয়: 0 = এখনো দেখিনি, 1 = এখন এর ভেতরে আছি (stack-এ চলছে), 2 = পুরো শেষ। DFS চলতে চলতে যদি এমন কাউকে পাই যার অবস্থা 1 — মানে নিজের চলমান পথেই ফিরে এসেছি, অর্থাৎ cycle:

#include <stdio.h>
#define N 5
const char *pkg[N] = {"app", "web", "json", "log", "util"};
int dep[N][N], state[N];             /* 0 = new, 1 = on current path, 2 = done */

int dfs(int u, int depth) {
    printf("%*s%s\n", depth * 2, "", pkg[u]);
    state[u] = 1;
    for (int v = 0; v < N; v++) {
        if (!dep[u][v]) continue;
        if (state[v] == 1) { printf("CYCLE: %s -> %s\n", pkg[u], pkg[v]); return 1; }
        if (state[v] == 0 && dfs(v, depth + 1)) return 1;
    }
    state[u] = 2;
    return 0;
}
int main(void) {
    dep[0][1] = dep[0][3] = dep[1][2] = dep[2][4] = dep[3][4] = dep[4][1] = 1;
    if (!dfs(0, 0)) printf("No cycle - install order is safe\n");
    return 0;
}

Topological sort — কোন কোর্স আগে পড়বেন

Cycle না থাকলে একটি সুন্দর জিনিস করা যায়: সব vertex-কে এমন ক্রমে সাজানো, যাতে প্রতিটি “আগে লাগবে” সম্পর্ক মানা হয়। একে বলে topological sort. নিজে নিজে প্রোগ্রামিং শেখার একটি ছোট পরিকল্পনা ধরি — কোন কোর্সের আগে কোনটা পড়া দরকার:

• DSA (Data Structures) পড়ার আগে লাগবে C (প্রোগ্রামিং).
• Algo (Algorithms) পড়ার আগে লাগবে DSA আর Math (Discrete Math) — দুটোই।
• AI পড়ার আগে লাগবে Algo.

সবচেয়ে সহজ পদ্ধতিটি এমন: প্রতিটি কোর্সের in-degree গুনুন — অর্থাৎ তার আগে কয়টি কোর্স বাকি। যার বাকি শূন্য, সেটি এখনই নেওয়া যায়। নিলে, তার ওপর নির্ভরশীল কোর্সগুলোর বাকি একটি করে কমে যায়। (এটি Kahn-এর পদ্ধতি নামে পরিচিত, আর ভেতরে একটি queue ব্যবহার করে — BFS-এর আত্মীয়। DFS দিয়েও করা যায়: DFS শেষ হওয়ার ক্রমটি উল্টে দিলেই topological ক্রম।)

 C ------> DSA ------> Algo ------> AI
                       ^
 Math -----------------+

৮ · গতি, তুলনা আর বাস্তবের গ্রাফ

BFS আর DFS দুটোরই খরচ O(V + E) (adjacency list ব্যবহার করলে)। কারণটি গুনে দেখা যায়: visited চিহ্নের জন্য প্রতিটি vertex একবারই queue/stack-এ ঢোকে — মোট V বার; আর প্রতিটি vertex-এর প্রতিবেশী-তালিকা একবারই হাঁটা হয় — সব তালিকা মিলিয়ে মোট entry মোটামুটি 2E. Matrix ব্যবহার করলে প্রতিবেশী খুঁজতে প্রতিবার পুরো সারি দেখতে হয়, তাই খরচ হয় O(V²)। এই “গুনে দেখা”র আনুষ্ঠানিক রূপ — time complexity আর Big-O — নিয়েই পরের পর্ব।

যেখানে প্রতিদিন গ্রাফ চলছে

• ম্যাপ ও রাইড-শেয়ারিং অ্যাপ: রাস্তার মোড় vertex, রাস্তা edge, ওজন হলো যানজটসহ আনুমানিক সময়। Dijkstra-র ধারণার ওপর দাঁড়ানো উন্নত পদ্ধতি দিয়ে পথ বের হয়।
• Package manager ও build system: dependency-র directed গ্রাফ, topological sort দিয়ে ইনস্টলের ক্রম, cycle থাকলে স্পষ্ট error.
• Web crawler: সার্চ ইঞ্জিনের প্রোগ্রাম কয়েকটি পরিচিত পেজ থেকে শুরু করে লিংক ধরে ধরে নতুন পেজ খোঁজে — অনেকটা BFS-এর মতো, আর visited তালিকা ছাড়া একই পেজ বারবার নামাত।
• নেটওয়ার্ক রাউটিং: ইন্টারনেটের router-গুলো নিজেদের মধ্যে একটি গ্রাফ; OSPF-এর মতো প্রোটোকল Dijkstra দিয়ে প্যাকেট পাঠানোর পথ হিসাব করে (দেখুন Computer Networks কোর্স)।

৯ · AI-এর যুগে গ্রাফ কোড — কোথায় চোখ রাখবেন

“C-তে BFS লিখে দাও” — যেকোনো AI কয়েক সেকেন্ডে দিয়ে দেবে, আর ছোট উদাহরণে সেটি চলবেও। সমস্যা হয় যখন আপনার আসল ডেটা আসে: হাজার হাজার vertex, cycle, বিচ্ছিন্ন অংশ, ওজন। AI-এর গ্রাফ কোডের ভুলগুলো সাধারণত ছোট গ্রাফে লুকিয়ে থাকে, বড় গ্রাফে ফেটে বেরোয়।

AI সাধারণত যেসব গ্রাফ-ভুল করে

AI-এর গ্রাফ কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Visited (বা dist == -1) চিহ্ন আছে, আর BFS-এ সেটি queue-তে ঢোকানোর সময় দেওয়া হয়েছে
• একটি cycle-ওয়ালা ছোট গ্রাফ আর একটি বিচ্ছিন্ন অংশওয়ালা গ্রাফ দিয়ে চালিয়েছি — দুটোতেই ঠিকঠাক থেমেছে
• Representation গ্রাফের মাপের সাথে মানানসই — বড় sparse গ্রাফে matrix নয়
• Algorithm প্রশ্নের সাথে মানানসই — কম ধাপ = BFS, ওজনওয়ালা কম খরচ = Dijkstra, cycle/ক্রম = DFS
• গভীর গ্রাফে recursion-এর সীমা ভেবেছি, দরকারে নিজের stack ব্যবহার করেছি
• অন্তত একটি ফল (দূরত্ব বা পথ) হাতে হিসাব করে মিলিয়েছি