एक ग्राफ का इन्सिडेंस मैट्रिक्स ग्राफ को मेमोरी में स्टोर करने का एक और प्रतिनिधित्व है। यह मैट्रिक्स एक वर्ग मैट्रिक्स नहीं है। इन्सिडेंस मैट्रिक्स का ऑर्डर V x E होता है। जहां V वर्टेक्स की संख्या है और E ग्राफ में एज की संख्या है।
इस मैट्रिक्स की प्रत्येक पंक्ति में हम वर्टेक्स रखते हैं, और प्रत्येक कॉलम में एज रखे जाते हैं। इस प्रतिनिधित्व में एक एज e {u, v} के लिए, इसे कॉलम e के स्थान u और v के लिए 1 द्वारा मार्क किया जाएगा।
एडजेसेंसी मैट्रिक्स प्रतिनिधित्व की जटिलता
इन्सिडेंस मैट्रिक्स प्रतिनिधित्व गणना के दौरान O(V x E) मात्रा में स्पेस लेता है। पूर्ण ग्राफ के लिए एज की संख्या V(V-1)/2 होगी। इसलिए इन्सिडेंस मैट्रिक्स मेमोरी में अधिक स्पेस लेता है।
इनपुट
आउटपुट
| E0 |
E1 |
E2 |
E3 |
E4 |
E5 |
E6 |
E7 |
E8 |
|
|---|---|---|---|---|---|---|---|---|---|
| 0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
| 2 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
| 3 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
| 4 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
| 5 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
एल्गोरिदम
add_edge(u, v)
इनपुट - एक एज {u,v} के u और v
आउटपुट - ग्राफ G का इन्सिडेंस मैट्रिक्स
सबसे पहले, इन्सिडेंस मैट्रिक्स के लिए एज काउंट ed_cnt 0 है।
Begin
ed_cnt := ed_cnt + 1
inc_matrix[u, ed_cnt] := 1
inc_matrix[v, ed_cnt] := 1
End
उदाहरण कोड (C++)
#include <iostream>
using namespace std;
int inc_arr[20][20]; // इन्सिडेंस मैट्रिक्स रखने के लिए प्रारंभिक ऐरे
int ed_no = 0;
void displayMatrix(int v, int e) {
int i, j;
for (i = 0; i < v; i++) {
for (j = 0; j < e; j++) {
cout << inc_arr[i][j] << " ";
}
cout << endl;
}
}
void add_edge(int u, int v) {
// एज नंबर के साथ मैट्रिक्स में एज जोड़ने का फंक्शन
inc_arr[u][ed_no] = 1;
inc_arr[v][ed_no] = 1;
ed_no++; // एज नंबर बढ़ाएं
}
main(int argc, char* argv[]) {
int v = 6; // ग्राफ में 6 वर्टेक्स हैं
int e = 9; // ग्राफ में 9 एज हैं
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, e);
}
आउटपुट
1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1
