Graph Theory (All)

ভূমিকা (Introduction)

গ্রাফ (Graph) থিওরি হলো কম্পিউটার সায়েন্স এবং ম্যাথমেটিক্সের অন্যতম গুরুত্বপূর্ণ এবং আকর্ষণীয় একটি শাখা। একটি গ্রাফ প্রধানত দুটি জিনিস দিয়ে তৈরি হয়: নোড (Node) বা ভার্টেক্স (Vertex) এবং এজ (Edge)। এজগুলোর কাজ হলো নোডগুলোর মধ্যে সম্পর্ক বা কানেকশন স্থাপন করা।

গ্রাফ সাধারণত দুই ধরনের হয়:

1. Directed Graph (ডিরেক্টেড গ্রাফ): এখানে এজগুলোর একটি নির্দিষ্ট দিক (direction) থাকে।
2. Undirected Graph (আনডিরেক্টেড গ্রাফ): এখানে এজগুলোর কোনো নির্দিষ্ট দিক থাকে না, অর্থাৎ সম্পর্ক দ্বিমুখী (bidirectional)।

এছাড়া গ্রাফের এজগুলোর ওয়েট বা ভ্যালু থাকতে পারে, যাকে Weighted Graph বলা হয়।

---

গ্রাফ রিপ্রেজেন্টেশন (Graph Representation)

যেকোনো অ্যালগরিদম ইমপ্লিমেন্ট করার আগে আমাদের জানতে হবে কিভাবে একটি গ্রাফকে মেমোরিতে স্টোর করতে হয়। মূলত দুটি জনপ্রিয় পদ্ধতি রয়েছে:

১. Adjacency Matrix

এটি একটি 2D Array (বা ম্যাট্রিক্স) যেখানে matrix[i][j] = 1 বা weight মানে হলো নোড i থেকে j এর মধ্যে একটি এজ আছে।

• সুবিধা: এজ আছে কি নেই তা $O(1)$ টাইমে চেক করা যায়।
• অসুবিধা: অনেক বেশি মেমোরি লাগে $O(V^2)$, বিশেষ করে স্পার্স গ্রাফের (Sparse Graph) জন্য এটি খুবই মেমোরি ইনফিসিয়েন্ট।

// C++ Example: Adjacency Matrix
int adjMatrix[100][100];
void addEdge(int u, int v) {
    adjMatrix[u][v] = 1;
    adjMatrix[v][u] = 1; // Undirected
}

২. Adjacency List

এখানে প্রতিটি নোডের সাথে তার প্রতিবেশী (neighbor) নোডগুলোর একটি লিস্ট রাখা হয়। C++ এ সাধারণত vector<int> adj[V] ব্যবহার করা হয়।

• সুবিধা: মেমোরি অনেক কম লাগে $O(V + E)$।
• অসুবিধা: কোনো নির্দিষ্ট এজ আছে কিনা তা চেক করতে $O(V)$ টাইম লাগতে পারে।

// C++ Example: Adjacency List
vector<int> adjList[100];
void addEdge(int u, int v) {
    adjList[u].push_back(v);
    adjList[v].push_back(u); // Undirected
}

---

গ্রাফ ট্রাভার্সাল (Graph Traversal)

গ্রাফের প্রতিটি নোড ভিজিট করার প্রসেসকে ট্রাভার্সাল বলে। এর দুটি বেসিক পদ্ধতি হলো:

BFS (Breadth-First Search)

BFS গ্রাফের প্রতিটি লেভেল (Level) অনুযায়ী ট্রাভার্স করে। এটি প্রথমে স্টার্টিং নোড থেকে ১ দূরত্বে থাকা সব নোড ভিজিট করে, তারপর ২ দূরত্বে থাকা নোডগুলো, এভাবে এগোতে থাকে। এটি ইমপ্লিমেন্ট করতে Queue ডেটা স্ট্রাকচার ব্যবহার করা হয়।

• Time Complexity: $O(V + E)$
• ব্যবহার (Applications): Unweighted graph এর ক্ষেত্রে শর্টেস্ট পাথ (Shortest Path) বের করতে, কানেক্টেড কম্পোনেন্ট (Connected Component) বের করতে এবং সোশ্যাল নেটওয়ার্কে ফ্রেন্ড সাজেশনের জন্য BFS খুবই কার্যকরী।

void BFS(int start) {
    vector<bool> visited(V, false);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        
        for (int v : adjList[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

DFS (Depth-First Search)

DFS গ্রাফের যতটা গভীরে (Depth) যাওয়া যায় ততটা যায়। একটি পাথ ধরে একদম শেষ পর্যন্ত গিয়ে তারপর ব্যাকট্র্যাক (Backtrack) করে অন্য পাথ খোঁজে। এটি Stack (অথবা Recursion) ব্যবহার করে ইমপ্লিমেন্ট করা হয়।

• Time Complexity: $O(V + E)$
• ব্যবহার (Applications): গ্রাফে সাইকেল (Cycle) ডিটেক্ট করতে, টপোলজিক্যাল সর্টিং (Topological Sorting) এ এবং মেজ বা পাজল সলভিং এ DFS অনেক বেশি ব্যবহৃত হয়।

void DFS(int u, vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";
    
    for (int v : adjList[u]) {
        if (!visited[v]) {
            DFS(v, visited);
        }
    }
}

---

টপোলজিক্যাল সর্টিং (Topological Sorting)

টপোলজিক্যাল সর্টিং শুধুমাত্র Directed Acyclic Graph (DAG) এর ক্ষেত্রেই সম্ভব। এটি নোডগুলোর এমন একটি লিনিয়ার অর্ডারিং যেখানে প্রতিটি ডিরেক্টেড এজ U -> V এর জন্য, U সবসময় অর্ডারিং-এ V এর আগে আসে।

• ব্যবহার: টাস্ক শিডিউলিং (Task Scheduling), প্রজেক্ট বিল্ড সিস্টেমে ডিপেন্ডেন্সি রেজোলিউশন (Dependency Resolution) যেমন: একটি প্যাকেজ ইনস্টল করার আগে তার ডিপেন্ডেন্সি প্যাকেজগুলো ইনস্টল করা।

DFS ব্যবহার করে এটি খুব সহজেই ইমপ্লিমেন্ট করা যায়। আমরা যখন একটি নোডের সব প্রতিবেশী ভিজিট করা শেষ করি, তখন সেই নোডটিকে একটি Stack এ পুশ করি। শেষে Stack থেকে পপ করলেই অর্ডারিং পাওয়া যায়।

---

শর্টেস্ট পাথ অ্যালগরিদম (Shortest Path Algorithms)

গ্রাফে এক নোড থেকে অন্য নোডে যাওয়ার সবচেয়ে কম দূরত্বের (বা খরচের) পথ বের করার জন্য বেশ কিছু অ্যালগরিদম আছে।

১. Dijkstra's Algorithm

Dijkstra পজিটিভ ওয়েটেড (Positive Weighted) গ্রাফে সিঙ্গল সোর্স শর্টেস্ট পাথ (Single Source Shortest Path) বের করতে ব্যবহৃত হয়। এটি মূলত একটি গ্রিডি অ্যালগরিদম যা Priority Queue (বা Min-Heap) ব্যবহার করে সবচেয়ে কম খরচের নোডটি বেছে নেয়।

• Time Complexity: $O(E \log V)$
• অসুবিধা: যদি গ্রাফে কোনো নেগেটিভ ওয়েট (Negative Weight) এজ থাকে, তাহলে Dijkstra ঠিকমতো কাজ নাও করতে পারে।

void dijkstra(int start) {
    vector<int> dist(V, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

২. Bellman-Ford Algorithm

যেখানে Dijkstra ফেইল করে, সেখানে Bellman-Ford কাজে আসে। এটি নেগেটিভ ওয়েটেড গ্রাফেও শর্টেস্ট পাথ বের করতে পারে। এটি ডাইনামিক প্রোগ্রামিং অ্যাপ্রোচ ফলো করে এবং গ্রাফের সব এজগুলোকে $V-1$ বার রিল্যাক্স (Relax) করে।

• Time Complexity: $O(V \times E)$
• ব্যবহার: নেগেটিভ ওয়েট সাইকেল (Negative Weight Cycle) ডিটেক্ট করতে এটি দারুণ কাজ করে। যদি $V$ তম বারেও কোনো শর্টেস্ট পাথ আপডেট হয়, তার মানে গ্রাফে নেগেটিভ সাইকেল আছে।

৩. Floyd-Warshall Algorithm

এটি একটি All-pairs shortest path অ্যালগরিদম। অর্থাৎ, গ্রাফের যেকোনো দুটি নোডের মধ্যকার শর্টেস্ট পাথ এটি একসাথে ক্যালকুলেট করে দেয়।

• Time Complexity: $O(V^3)$
• ব্যবহার: ছোট গ্রাফের (যেখানে নোড সংখ্যা কম) জন্য এটি খুব সিম্পল এবং ইফেক্টিভ।

---

মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree - MST)

একটি স্প্যানিং ট্রি হলো গ্রাফের এমন একটি সাবগ্রাফ যা গ্রাফের সবগুলো নোডকে কানেক্ট করে, কিন্তু কোনো সাইকেল থাকে না। আর Minimum Spanning Tree (MST) হলো সেই স্প্যানিং ট্রি যার এজগুলোর ওয়েটের যোগফল সবচেয়ে কম।

১. Kruskal's Algorithm

Kruskal's অ্যালগরিদম গ্রিডি অ্যাপ্রোচ ফলো করে। এটি প্রথমে সবগুলো এজকে তাদের ওয়েট অনুযায়ী ছোট থেকে বড় সর্ট করে নেয়। এরপর একে একে এজগুলো নেয়, কিন্তু খেয়াল রাখে যেন কোনো সাইকেল তৈরি না হয়। সাইকেল ডিটেক্ট করতে Disjoint Set (Union-Find) ডেটা স্ট্রাকচার ব্যবহার করা হয়।

• Time Complexity: $O(E \log E)$
• ব্যবহার: স্পার্স গ্রাফের (যেখানে এজের সংখ্যা কম) জন্য এটি বেশি উপযোগী।

২. Prim's Algorithm

Prim's অ্যালগরিদম Dijkstra এর মতই কাজ করে। এটি একটি নির্দিষ্ট স্টার্টিং নোড থেকে শুরু হয় এবং সবসময় সবচেয়ে কম ওয়েটের কানেক্টেড এজটি বেছে নিয়ে ট্রি কে বড় করতে থাকে। এটিও Priority Queue ব্যবহার করে ইমপ্লিমেন্ট করা যায়।

• Time Complexity: $O(E \log V)$
• ব্যবহার: ডেন্স গ্রাফের (Dense Graph - যেখানে এজের সংখ্যা অনেক বেশি) জন্য এটি Kruskal এর চেয়ে ভালো পারফর্ম করে।

---

রিয়েল ওয়ার্ল্ড অ্যাপ্লিকেশন (Real World Applications of Graph Theory)

গ্রাফ থিওরি আমাদের দৈনন্দিন জীবনের বিভিন্ন প্রযুক্তির পেছনে বিশাল ভূমিকা পালন করে:

1. Google Maps ও Navigation: শর্টেস্ট পাথ অ্যালগরিদম (যেমন A* বা Dijkstra) ব্যবহার করে সবচেয়ে কম সময়ের বা দূরত্বের রাস্তা বের করা হয়।
2. Social Networks (Facebook/LinkedIn): "People You May Know" বা মিউচুয়াল ফ্রেন্ড সাজেশন মূলত BFS এবং গ্রাফ অ্যালগরিদমের উপর ভিত্তি করে কাজ করে।
3. Computer Networks ও Routing: ইন্টারনেটে এক রাউটার থেকে অন্য রাউটারে ডেটা প্যাকেট পাঠানোর জন্য Shortest Path (যেমন OSPF প্রোটোকল) ব্যবহার করা হয়।
4. Web Crawlers: গুগলের সার্চ ইঞ্জিন ক্রলাররা ওয়েব পেজগুলোর লিংকের গ্রাফ তৈরি করতে ট্রাভার্সাল (BFS/DFS) ব্যবহার করে।
5. Operating Systems: প্রসেস শিডিউলিং, ডেডলক ডিটেকশন (Deadlock Detection) এর জন্য রিসোর্স অ্যালোকেশন গ্রাফ (Resource Allocation Graph) এবং സൈকেল ডিটেকশন অ্যালগরিদম ব্যবহার হয়।
6. E-commerce Recommendation: ইউজার এবং প্রোডাক্টের বাইপারটাইট গ্রাফ (Bipartite Graph) অ্যানালাইসিস করে রিকমেন্ডেশন সিস্টেম তৈরি করা হয়।

উপসংহার

গ্রাফ থিওরি শুধুমাত্র কিছু ডেটা স্ট্রাকচার আর অ্যালগরিদম নয়, এটি বাস্তব জগতের জটিল সমস্যাগুলোকে গাণিতিক মডেলে পরিণত করে সমাধান করার একটি শক্তিশালী হাতিয়ার। BFS/DFS থেকে শুরু করে শর্টেস্ট পাথ এবং MST – প্রতিটি অ্যালগরিদমই ইন্টারভিউ থেকে শুরু করে রিয়েল প্রজেক্টে বারবার ফিরে আসে।