একটি গ্রাফের ইনসিডেন্স ম্যাট্রিক্স হলো গ্রাফকে মেমোরিতে স্টোর করার আরেকটি রিপ্রেজেন্টেশন। এই ম্যাট্রিক্সটি স্কোয়ার ম্যাট্রিক্স নয়। ইনসিডেন্স ম্যাট্রিক্সর অর্ডার V x E। এখানে V হলো ভার্টেক্সের সংখ্যা এবং E হলো গ্রাফে এজের সংখ্যা।
এই ম্যাট্রিক্সর প্রতিটি সারিতে আমরা ভার্টেক্স রাখি, এবং প্রতিটি কলামে এজ রাখি। এই রিপ্রেজেন্টেশনে একটি এজ e {u, v} এর জন্য, কলাম e-র u এবং v প্লেসে ১ দিয়ে মার্ক করা হয়।
অ্যাডজেসেন্সি ম্যাট্রিক্স রিপ্রেজেন্টেশনের কমপ্লেক্সিটি
ইনসিডেন্স ম্যাট্রিক্স রিপ্রেজেন্টেশন O(V x E) স্পেস নেয়। কমপ্লিট গ্রাফের জন্য এজের সংখ্যা হবে V(V-1)/2। তাই ইনসিডেন্স ম্যাট্রিক্স মেমোরিতে বড় স্পেস নেয়।
ইনপুট:
আউটপুট:
অ্যালগরিদম
add_edge(adj_list, u, v)
ইনপুট - একটি এজ {u,v}-এর u এবং v, এবং অ্যাডজেসেন্সি লিস্ট
আউটপুট - গ্রাফ G-এর অ্যাডজেসেন্সি লিস্ট
শুরু v কে u ইনডেক্সের লিস্টে অ্যাপেন্ড করুন u কে v ইনডেক্সের লিস্টে অ্যাপেন্ড করুন শেষ
উদাহরণ কোড
#include<iostream>
#include<list>
#include<iterator>
using namespace std;
void displayAdjList(list<int> adj_list[], int v) {
for(int i = 0; i < v; i++) {
cout << i << "--->";
list<int> :: iterator it;
for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
cout << *it << " ";
}
cout << endl;
}
}
void add_edge(list<int> adj_list[], int u, int v) {
adj_list[u].push_back(v);
adj_list[v].push_back(u);
}
main(int argc, char* argv[]) {
int v = 6; // গ্রাফে ৬টি ভার্টেক্স
list<int> adj_list[v]; // আকার ৬-এর লিস্টের অ্যারে তৈরি
add_edge(adj_list, 0, 4);
add_edge(adj_list, 0, 3);
add_edge(adj_list, 1, 2);
add_edge(adj_list, 1, 4);
add_edge(adj_list, 1, 5);
add_edge(adj_list, 2, 3);
add_edge(adj_list, 2, 5);
add_edge(adj_list, 5, 3);
add_edge(adj_list, 5, 4);
displayAdjList(adj_list, v);
}
আউটপুট
0--->4 3 1--->2 4 5 2--->1 3 5 3--->0 2 5 4--->0 1 5 5--->1 2 3 4
