एक ग्राफ का एडजेसेंसी मैट्रिक्स V x V आकार का एक वर्ग मैट्रिक्स होता है। V ग्राफ G के वर्टेक्स की संख्या है। इस मैट्रिक्स में प्रत्येक तरफ V वर्टेक्स मार्क किए जाते हैं। यदि ग्राफ में i से j वर्टेक्स तक कुछ एज हैं, तो एडजेसेंसी मैट्रिक्स में i-वीं पंक्ति और j-वें कॉलम में 1 होगा (या वेटेड ग्राफ के लिए कुछ नॉन-ज़ीरो वैल्यू), अन्यथा वह स्थान 0 रखेगा।
एडजेसेंसी मैट्रिक्स प्रतिनिधित्व की जटिलता:
एडजेसेंसी मैट्रिक्स प्रतिनिधित्व गणना के दौरान O(V²) मात्रा में स्पेस लेता है। जब ग्राफ में अधिकतम एज और न्यूनतम एज होते हैं, दोनों ही मामलों में आवश्यक स्पेस समान होगा।
इनपुट:
आउटपुट:
| 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 का एडजेसेंसी मैट्रिक्स
Begin
adj_matrix[u, v] := 1
adj_matrix[v, u] := 1
End
उदाहरण कोड
#include <iostream>
using namespace std;
int vertArr[20][20]; // एडजेसेंसी मैट्रिक्स प्रारंभ में 0
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; // ग्राफ में 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 0 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0
