Adjacency Matrix & Adjacency List

Adjacency Matrix:

অ্যাডজেসেন্ট নোড সম্পর্কে আমরা Graph Theory Introduction এ জেনেছি। একটি নোডের অ্যাডজেসেন্ট নোড হচ্ছে সেই নোডের পাশের নোডগুলো যেগুলো ওই নোডের সাথে এজের মাধ্যমে যুক্ত। এখন আমরা জানবো কিভাবে ম্যাট্রিক্স তৈরি করে বা 2D Array তৈরি করে কোন নোডের অ্যাডজেসেন্ট নোড নির্ণয়ের পদ্ধতি।

উপরে একটি আনডিরেক্টেড গ্রাফ দেয়া আছে। গ্রাফের পাশে একটি টেবিল দেখতে পাচ্ছ। এটি আমাদের অ্যাডজেসেন্সি ম্যাট্রিক্স। ম্যাট্রিক্সের $\left[i\right]\left[j\right]$ ঘরে $1$ দেই  যদি $i$ থেকে $j$ তে কোনো এজ থাকে, না থাকলে $0$ বসিয়ে দেই। গ্রাফটি যদি ডিরেক্টেড গ্রাফ হতো এবং প্রতিটি এজের যদি Weight দেয়া থাকতো তাহলে এমন হতো-

 

এখানে যেহেতু Weight দেয়া আছে সেহেতু এক নোড থেকে অন্য নোডে যেতে যেই কস্ট বা ওয়েইট আছে তা ম্যাট্রিক্সের $\left[i\right]\left[j\right]$ ঘরে বসানো হয়েছে। এক নোড থেকে অন্য নোডে যাওয়া না গেলে সেই ক্ষেত্রে ম্যাট্রিক্সের $\left[i\right]\left[j\right]$ ঘরে ইনফিনিটি value অর্থাৎ Integer বা  Long এর ম্যাক্সিমাম value বসানো হয়েছে। 

অ্যাডজেসেন্সি ম্যাট্রিক্সের সারকথা: সময় ও মেমরির অনেক অপচয় হয় অ্যাডজেসেন্সি ম্যাট্রিক্স ব্যবহার করলে। এটি অ্যাডজেসেন্সি ম্যাট্রিক্সের প্রধান সমস্যা। আবার সুবিধাও আছে- যেমন দুটি নোডের মধ্যে সংযোগ আছে কিনা বা দুটি নোডের এজের কস্ট কত তা খুব সহজেই ম্যাট্রিক্সের [u][v] এর value থেকে জেনে নিতে পারেন।

  

Adjacency List:

উপরের অ্যাডজেসেন্সি ম্যাট্রিক্সকে এবার আমরা অ্যাডজেসেন্সি লিস্টের মধ্যে প্রকাশ করব। 

উপরের গ্রাফ ও ম্যাট্রিক্স লক্ষ্য কর। একটি নোডের সাথে যেসকল নোড যুক্ত আছে সেসকল নোডগুলোকে নিচের নিয়মে লিস্টে সাজাই -

এটিই হচ্ছে উপরের অ্যাডজেসেন্সি ম্যাট্রিক্সের অ্যাডজেসেন্সি লিস্ট। সহজ না ব্যাপারটি ?? এবার এসো এই লিস্টকে কিভাবে প্রোগ্রামিং এর মাধ্যমে ইমপ্লিমেন্ট করবে তা নিয়ে আলোচনা করি। এই লিস্টকে স্টোর দুই ভাবে করতে পারো। Array ব্যবহার করে বা Vector ব্যবহার করে। আমি ভেক্টর ব্যবহার করে কিভাবে অ্যাডজেসেন্সি লিস্ট স্টোর করতে হয় তা জানাবো কারণ Vector, Array এর তুলনায় কম স্পেস অপচয় করে। ভেক্টর ব্যবহার করে অ্যাডজেসেন্সি লিস্ট স্টোর করার আগে STL দিয়ে কিভাবে ভেক্টরে ডাটা রাখা যায় তা এই লিংক থেকে জেনে নাও-STL-Vector Tutorial Link

ভেক্টর দিয়ে অ্যাডজেসেন্সি লিস্ট ইনপুট নেয়ার Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector <int> G[100];
    int n, m, u, v;
    scanf("%d%d", &n, &m);  //n is number of node & m is number of edge
    for(int i=0; i<m; i++)
    {
        scanf("%d%d", &u, &v);  //u and v are two two node of an edge
        G[u].push_back(v);
        G[v].push_back(u); // For bidirectional edge
    }
    for(int i=0; i<=n; i++)
    {
        for(int j=0; j<G[i].size(); j++)
        {
            printf("%d ",G[i][j]);
        }
        printf("\n");
    }
    return 0;
}