মডিউল ১৩_২ঃ এডজেসেন্সি লিস্ট ও এজ লিস্ট
Previousমডিউল ১৩_১ঃ এডজেসেন্সি ম্যাট্রিক্সNextমডিউল ১৩_৩ঃ এডজেসেন্সি লিস্ট টু এডজেসেন্সি ম্যাট্রিক্স পার্ট-১
Last updated
Last updated
অ্যাডজাসেন্সি লিস্টটি আমরা ইমপ্লিমেন্ট করি একটি array of vector দিয়ে।
এখন array of vector নিয়ে বিস্তারিত আলোচনা করছি। Array of vector সম্পর্কে জানার আগে array of int বিষয়টি একটু জেনে নি। Array of int আমরা এইভাবে declare করে থাকি, int arr[5]; তাহলে উপরে statement এর ফলে ৫ সাইজের একটি array declare হবে, যেইটির প্রতিটি index এআমরা int types এর data রাখতে পারবো।
Array of vector কে আমরা এইভাবে declare করে থাকি, vector<int> arr[5]; তাহলে উপরে statement এর ফলে ৫ সাইজের একটি array declare হবে, যেইটির প্রতিটি index এ আমরা একটি করে vector রাখতে পারবো।
6 6 0 1 1 5 0 4 0 3 3 4 2 4 এইখানে গ্রাফের প্রথমে ইনপুট নেয়া N ( Number of nodes ) এবং E ( Number of edges ) উপরের ইনপুটে N=6 এবং E=6 , এই এরপরই E বার ইনপুট নিয়া হয়েছে কোন নোড কোন নোডের সাথে connection আছে।
উপরের দেয়া ইনপুটে আমরা দেখতেছি, 0 নোড 1 , 3 , 4 নোডের সাথে connected. 1 নোড 0, 5 নোডের সাথে connected. 2 নোড 4 নোডের সাথে connected. 3 নোড 0, 4 নোডের সাথে connected. 4 নোড 0, 3, 2 নোডের সাথে connected. 5 নোড 1 নোডের সাথে connected. এখন আমরা এই গ্রাফের ইনপুটকে অ্যাডজাসেন্সি লিস্ট এর মধ্যে রাখতে array of vector টি এইরকম হবে।
এইভাবে আমরা অ্যাডজাসেন্সি লিস্টটি ইমপ্লিমেন্ট করতে পারি array of vector দিয়ে।
Edge লিস্ট হচ্ছে এমন একটি লিস্ট যেখানে কোন একটা গ্রাফের edge গুলো রাখা হয়।
6 6 0 1 1 5 0 4 0 3 3 4 2 4
উপরের দেয়া গ্রাফের ইনপুটে গ্রাফের edge (0, 1), (1, 5), (0, 4), (0, 3), (3, 4), (2, 4) আছে, এই edge গুলোকে আমরা কোন একটি লিস্টের মধ্যে রাখবো সেইটিই হচ্ছে edge list।
প্রতিটি edge ২টি নোড দেয়া থাকে। এই প্রতিটি edge এর নোড ২টিকে দিয়ে আমরা একটি pair<int, int> বানিয়ে, সেই pair<int,int> টিকে কোন একটা লিস্টের মধ্যে রাখলে লিস্টটিতে নিচে দেখানো চিত্রের মত edge থাকবে।
