গ্রাফ থিওরিতে হাতেখড়ি

প্রোগ্রামিং জগতে 'গ্রাফ' বলতে আমরা স্কুলের খাতায় আঁকা এক্স-অক্ষ বা ওয়াই-অক্ষের গ্রাফকে বুঝি না। ডেটা স্ট্রাকচারে গ্রাফ (Graph) হলো কোনো জিনিসের মধ্যে সম্পর্ক (Relationship) প্রকাশ করার একটা দারুণ পদ্ধতি।

উদাহরণ হিসেবে ফেসবুকের কথা ধরি। ফেসবুকে তুমি এবং তোমার বন্ধুরা সবাই একেকজন মানুষ। তুমি যদি তোমার কোনো বন্ধুর সাথে কানেক্টেড থাকো (Friend), তাহলে তোমাদের দুজনের মাঝে একটা সম্পর্ক আছে। এটিকে প্রোগ্রামিংয়ের ভাষায় বলা হয় গ্রাফ।

গ্রাফের মৌলিক উপাদান

গ্রাফ মূলত দুটি জিনিস দিয়ে তৈরি:

1. Node (বা Vertex): গ্রাফের প্রতিটি উপাদান। যেমন: ফেসবুকে প্রতিটি মানুষের প্রোফাইল এক একটি নোড।
2. Edge (বা Link): নোডগুলোর ভেতরের কানেকশন। যেমন: দুজন মানুষের ভেতরের বন্ধুত্বের সম্পর্ক।

গ্রাফের ধরণ (Types of Graphs)

১. আনডাইরেক্টেড গ্রাফ (Undirected Graph)

ফেসবুকের বন্ধুত্বের মতো। তুমি যদি রহিমের বন্ধু হও, রহিমও তোমার বন্ধু। এখানে সম্পর্কটা উভমুখী। এজগুলোর কোনো নির্দিষ্ট দিক থাকে না।

২. ডাইরেক্টেড গ্রাফ (Directed Graph / Digraph)

টুইটার বা ইন্সটাগ্রামের ফলোয়ার সিস্টেমের মতো। তুমি ক্রিস্টিয়ানো রোনালদোকে ফলো করতে পারো, কিন্তু সে তোমাকে ফলো ব্যাক নাও করতে পারে। এখানে এজের নির্দিষ্ট দিক (তীর চিহ্ন) থাকে।

৩. ওয়েইটেড গ্রাফ (Weighted Graph)

অনেক সময় একটা কানেকশনের একটা মান বা ওয়েইট (Weight) থাকে। যেমন Google Maps। একটা শহর থেকে আরেকটা শহরে যাওয়ার অনেকগুলো রাস্তা (Edge) থাকতে পারে, কিন্তু প্রতিটি রাস্তার দূরত্ব (Weight) ভিন্ন হয়।

প্রোগ্রামিংয়ে গ্রাফ কীভাবে রাখা যায়?

গ্রাফকে মেমরিতে সাধারণত দুটি উপায়ে রাখা হয়:

১. Adjacency Matrix: এটা একটা 2D অ্যারে বা ম্যাট্রিক্স। যদি নোড A এর সাথে নোড B এর কানেকশন থাকে, তবে আমরা ম্যাট্রিক্সের [A][B] ঘরে 1 রাখি, না থাকলে 0 রাখি।

• সুবিধা: কানেকশন আছে কিনা সেটা $O(1)$ টাইমে চেক করা যায়।
• অসুবিধা: মেমরি প্রচুর নষ্ট হয়, কমপ্লেক্সিটি $O(V^2)$।

২. Adjacency List: এটা মূলত প্রতিটি নোডের জন্য একটা আলাদা লিস্ট। নোড A এর লিস্টে শুধু তার connected বন্ধুদের নামগুলো রাখা হয়।

• সুবিধা: মেমরি বেচে যায়। শুধু যেটুকু কানেকশন আছে সেটুকু সেভ হয়।
• অসুবিধা: দুইটা নোড কানেক্টেড কিনা সেটা চেক করতে লিনিয়ার সার্চ করতে হয়।

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int nodes = 5;
    // ৫টি নোডের জন্য ৫টি ভেক্টর তৈরি করলাম
    vector<int> adj_list[nodes + 1];

    // 1 এবং 2 এর মাঝে কানেকশন (Undirected Edge)
    adj_list[1].push_back(2);
    adj_list[2].push_back(1);

    // 1 এবং 3 এর মাঝে কানেকশন
    adj_list[1].push_back(3);
    adj_list[3].push_back(1);

    cout << "Node 1 is connected to: ";
    for (int node : adj_list[1]) {
        cout << node << " "; // Output: 2 3
    }
}

গ্রাফের ওপর প্রচুর চমৎকার অ্যালগরিদম আছে (যেমন: Shortest Path, DFS, BFS)। পরবর্তী পর্বগুলোতে আমরা সেগুলো নিয়ে বিস্তারিত জানবো!