মডিউল ১৩_৪ঃ এডজেসেন্সি লিস্ট টু এডজেসেন্সি ম্যাট্রিক্স পার্ট-২

এখন আমরা একটা weighted গ্রাফ এর লিস্টকে কিভাবে ম্যাট্রিক্স এ কনভার্ট করতে পারি সেটা দেখবো।

আগের মডিউলটা বুঝে থাকলে এইটি বুঝা খুবই সহজ। এখন আমাদের লিস্ট এ নোড এর সাথে weight ও দেওয়া থাকবে।

আমরা একটি ম্যাট্রিক্স রাখবো যার সারি এবং কলাম সংখ্যা উভয়ই হবে নোড সংখ্যার সমান। আর শুরুতে সকল এলিমেন্টে -1 রাখবো। আর শুধু যে এলিমেন্ট গুলোর সারি এবং কলাম সংখ্যা সমান তাদের 0 রাখবো। কারন তারা সেলফ নোড।

// Some code
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            mat[i][j] = -1;
            if (i == j)
                mat[i][j] = 0;
        }
    }

এবার আমরা প্রত্যেকটি নোড এর এডজেসেন্সি লিস্ট এ যাবো আর সেই লিস্ট এর প্রত্যেকটি ইনডেক্সের প্রথম ভ্যালু হচ্ছে ম্যাট্রিক্স এর সেই নোড ও সেকেন্ড ভ্যালু হচ্ছে সেই এজ এর কস্ট। তাহলে আমরা ম্যাট্রিক্স এর সেই সারি ও সেই কলামে ভ্যালু গুলো এসাইন করে দিব।

// Some code
    for (int i = 0; i < n; i++)
    {
        for (pair<int, int> child : adj[i])
        {
            int childNode = child.first;
            int cost = child.second;
            mat[i][childNode] = cost;
        }
    }

Last updated