অ্যাডজেসেন্সি লিস্ট (Adjacency List)
অ্যাডজেসেন্সি লিস্ট একটি জনপ্রিয় গ্রাফ রিপ্রেজেন্টেশন পদ্ধতি, যা গ্রাফের ভেরটেক্সগুলির মধ্যে সম্পর্ক (এজ) সংরক্ষণ করে। এটি বিশেষত গ্রাফের তথ্য সংরক্ষণে স্থান সাশ্রয়ী এবং কার্যকরী।
অ্যাডজেসেন্সি লিস্টের গঠন
অ্যাডজেসেন্সি লিস্ট সাধারণত একটি তালিকা (list) বা অ্যারে (array) ব্যবহার করে তৈরি করা হয়, যেখানে প্রতিটি ভেরটেক্সের জন্য একটি আলাদা তালিকা থাকে। প্রতিটি তালিকা ঐ ভেরটেক্সের সাথে সংযুক্ত অন্যান্য ভেরটেক্সগুলির একটি সেট ধারণ করে।
- ভেরটেক্সের তালিকা: গ্রাফের প্রতিটি ভেরটেক্সের জন্য একটি এডজেসেন্সি লিস্ট তৈরি করা হয়।
- এজগুলির সংরক্ষণ: প্রতিটি ভেরটেক্সের লিস্টে সেই ভেরটেক্সের সাথে সরাসরি সংযুক্ত ভেরটেক্সের নাম অন্তর্ভুক্ত থাকে।
উদাহরণ
ধরা যাক একটি গ্রাফ আছে যার ভেরটেক্সসমূহ A, B, C, D, এবং এজসমূহ A-B, A-C, B-D, C-D।
অ্যাডজেসেন্সি লিস্ট হবে:
এখানে:
- A এর সাথে B এবং C সংযুক্ত।
- B এর সাথে A এবং D সংযুক্ত।
- C এর সাথে A এবং D সংযুক্ত।
- D এর সাথে B এবং C সংযুক্ত।
সুবিধা
- স্থান সাশ্রয়ী: অ্যাডজেসেন্সি লিস্ট স্থান সাশ্রয়ী, কারণ এটি শুধুমাত্র কার্যকরী এজগুলির তথ্য সংরক্ষণ করে। এটি বিশেষ করে বড় এবং স্পার্স গ্রাফের জন্য কার্যকরী।
- সহজ ডেটা অ্যাক্সেস: ভেরটেক্সের সাথে সংযুক্ত সকল ভেরটেক্স পাওয়া সহজ।
- ডাইনামিক: নতুন ভেরটেক্স এবং এজ যুক্ত করা সহজ, যা গ্রাফের গঠন পরিবর্তন করার জন্য কার্যকরী।
অসুবিধা
- এজ চেক করার সময়: একটি নির্দিষ্ট ভেরটেক্সের সাথে একটি নির্দিষ্ট ভেরটেক্সের সংযোগ আছে কিনা তা পরীক্ষা করতে O(V) সময় লাগতে পারে, যেখানে V হল ভেরটেক্সের সংখ্যা।
- এজের সংখ্যা বেশি হলে পারফরম্যান্স: যদি একটি গ্রাফের এজ সংখ্যা খুব বেশি হয় তবে লিস্টের মধ্যে ভেরটেক্সের সংযোগ খুঁজে পাওয়া কিছুটা কঠিন হতে পারে।
সারসংক্ষেপ
অ্যাডজেসেন্সি লিস্ট একটি গুরুত্বপূর্ণ গ্রাফ রিপ্রেজেন্টেশন পদ্ধতি, যা ভেরটেক্সগুলির মধ্যে সম্পর্ক সংরক্ষণ করে। এটি স্থান সাশ্রয়ী এবং কার্যকরী, বিশেষ করে স্পার্স গ্রাফগুলির জন্য। গ্রাফের বিভিন্ন প্রয়োজনে অ্যাডজেসেন্সি লিস্ট একটি সুবিধাজনক সমাধান প্রদান করে।
Read more
