গ্রাফ হলো একটি নন-লিনিয়ার ডেটা স্ট্রাকচার। এটি নোড ব্যবহার করে ডেটা উপস্থাপন করে এবং তাদের সম্পর্ক এজ ব্যবহার করে। একটি গ্রাফ G-র দুটি অংশ থাকে। ভার্টেক্স এবং এজ। ভার্টেক্স সেট V দিয়ে উপস্থাপিত হয়, এবং এজ সেট E দিয়ে উপস্থাপিত হয়। তাই গ্রাফের নোটেশন হলো G(V,E)। একটি উদাহরণ দেখি।
এই গ্রাফে পাঁচটি ভার্টেক্স এবং পাঁচটি এজ আছে। এজগুলো ডিরেক্টেড। উদাহরণস্বরূপ, যদি আমরা B এবং D কানেক্ট করার এজ বেছে নিই, তবে সোর্স ভার্টেক্স B এবং ডেস্টিনেশন D। তাই আমরা B থেকে D-তে যেতে পারি কিন্তু D থেকে B-তে যেতে পারি না।
গ্রাফগুলো নন-লিনিয়ার, এবং এর কোনো রেগুলার স্ট্রাকচার নেই। মেমরিতে গ্রাফ রিপ্রেজেন্ট করার জন্য কিছু ভিন্ন স্টাইল আছে। সেগুলো হলো −
- অ্যাডজেসেন্সি ম্যাট্রিক্স রিপ্রেজেন্টেশন
- এজ লিস্ট রিপ্রেজেন্টেশন
- অ্যাডজেসেন্সি লিস্ট রিপ্রেজেন্টেশন
অ্যাডজেসেন্সি ম্যাট্রিক্স রিপ্রেজেন্টেশন
আমরা অ্যাডজেসেন্সি ম্যাট্রিক্স ব্যবহার করে একটি গ্রাফ রিপ্রেজেন্ট করতে পারি। দেওয়া ম্যাট্রিক্সটি একটি অ্যাডজেসেন্সি ম্যাট্রিক্স। এটি একটি বাইনারি, স্কোয়ার ম্যাট্রিক্স এবং i-তম রো থেকে j-তম কলামে, যদি একটি এজ থাকে, তবে সেটা ১ দিয়ে মার্ক করা হয়। অনডিরেক্টেড গ্রাফকে অ্যাডজেসেন্সি ম্যাট্রিক্স দিয়ে রিপ্রেজেন্ট করলে, ম্যাট্রিক্সটি সিমেট্রিক হবে।
এজ লিস্ট রিপ্রেজেন্টেশন
গ্রাফগুলো এক-ডাইমেনশনাল অ্যারেও রিপ্রেজেন্ট করা যায়। এটাকে এজ লিস্ট বলে। এই রিপ্রেজেন্টেশনে পাঁচটি এজ আছে, প্রতিটি এজের জন্য প্রথম এলিমেন্ট হলো সোর্স এবং দ্বিতীয়টি হলো ডেস্টিনেশন। অনডিরেক্টেড গ্রাফ রিপ্রেজেন্টেশনের জন্য এজ লিস্টে এলিমেন্টের সংখ্যা ডাবল হবে।
অ্যাডজেসেন্সি লিস্ট রিপ্রেজেন্টেশন
এটি গ্রাফ রিপ্রেজেন্টেশনের আরেকটি টাইপ। এটাকে অ্যাডজেসেন্সি লিস্ট বলে। এই রিপ্রেজেন্টেশন লিংকড লিস্টের উপর ভিত্তি করে। এই এপ্রোച്ചে, প্রতিটি নোড একটি নোডের লিস্ট ধারণ করে, যা সেটি সরাসরি সেই ভার্টেক্সের সাথে কানেক্টেড। লিস্টের শেষে, প্রতিটি নোড নাল ভ্যালুয়ের সাথে কানেক্টেড থাকে যাতে বোঝা যায় সেটি সেই লিস্টের শেষ নোড।
