একটি গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স হলো V x V আকারের একটি স্কোয়ার ম্যাট্রিক্স। V হলো গ্রাফ G-এর ভার্টেক্সের সংখ্যা। এই ম্যাট্রিক্সের প্রতিটি দিকেই V সংখ্যক ভার্টেক্স মার্ক করা থাকে। যদি গ্রাফে i থেকে j ভার্টেক্স পর্যন্ত কোনো এজ থাকে, তবে অ্যাডজেসেন্সি ম্যাট্রিক্সের i-তম সারি এবং j-তম কলামে ১ থাকবে (ওয়েটেড গ্রাফের জন্য নন-জিরো ভ্যালু), অন্যথায় সেটি ০ থাকবে।
অ্যাডজেসেন্সি ম্যাট্রিক্স রিপ্রেজেন্টেশনের কমপ্লেক্সিটি
অ্যাডজেসেন্সি ম্যাট্রিক্স রিপ্রেজেন্টেশন O(V2) স্পেস নেয়। গ্রাফে সর্বোচ্চ এজ থাকুক ন্যূনতম এজ থাকুক, উভয় কেসে একই স্পেস দরকার।
ইনপুট
আউটপুট
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 | 0 | 0 |
| 3 | 1 | 0 | 1 | 0 | 0 | 1 |
| 4 | 1 | 1 | 0 | 0 | 0 | 1 |
| 5 | 0 | 1 | 1 | 1 | 1 | 0 |
অ্যালগরিদম
add_edge(u, v)
ইনপুট - একটি এজ {u,v}-এর u এবং v
আউটপুট - গ্রাফ G-এর অ্যাডজেসেন্সি ম্যাট্রিক্স
শুরু adj_matrix[u, v] := 1 adj_matrix[v, u] := 1 শেষ
উদাহরণ কোড
#include<iostream>
using namespace std;
int vertArr[20][20]; // অ্যাডজেসেন্সি ম্যাট্রিক্স, প্রাথমিক ০
int count = 0;
void displayMatrix(int v) {
int i, j;
for(i = 0; i < v; i++) {
for(j = 0; j < v; j++) {
cout << vertArr[i][j] << " ";
}
cout << endl;
}
}
void add_edge(int u, int v) {
vertArr[u][v] = 1;
vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
int v = 6; // গ্রাফে ৬টি ভার্টেক্স
add_edge(0, 4);
add_edge(0, 3);
add_edge(1, 2);
add_edge(1, 4);
add_edge(1, 5);
add_edge(2, 3);
add_edge(2, 5);
add_edge(5, 3);
add_edge(5, 4);
displayMatrix(v);
}
আউটপুট
0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0
