মডিউল ১_২ঃ অ্যাডজাসেন্সি ম্যাট্রিক্স

গ্রাফ রিপ্রেজেন্টেশন

গ্রাফ রিপ্রেজেন্টেশন ৩ ভাবে করা যায়ঃ

1. Adjacency Matrix

2. Adjacency List

3. Edge List

গ্রাফের ইনপুট

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 আছে।

নিচে ইনপুটটির edge গুলো অনুসারে গ্রাফটি আঁকা হল এবং প্রতিটি edge এ ভিন্ন ভিন্ন কালার ব্যবহার করা হয়েছে অ্যাডজাসেন্সি ম্যাট্রিক্স বুঝাতে সুবিধা হওয়ার জন্য।

Unweighted graph এর অ্যাডজাসেন্সি ম্যাট্রিক্স এইভাবে যে নোড এর সাথে যে নোড এর edge আছে সেইটিতে 1 রাখা হয়, আর যে নোড এর সাথে যে নোডের কোন edge নেই সেইটিতে 0 রাখা হয়।

এখন নিচে একটি weighted graph আঁকা হল

Weighted graph এর অ্যাডজাসেন্সি ম্যাট্রিক্স এইভাবে যে নোড এর সাথে যে নোড এর edge আছে সেইটিতে weight টিরাখা হয়, আর যে নোড এর সাথে যে নোডের কোন edge সেইটিতে 0 রাখা হয়।