एक ग्राफ का इन्सिडेंस मैट्रिक्स ग्राफ को मेमोरी में स्टोर करने का एक और प्रतिनिधित्व है। यह मैट्रिक्स एक वर्ग मैट्रिक्स नहीं है। इन्सिडेंस मैट्रिक्स का ऑर्डर V x E होता है। जहां V वर्टेक्स की संख्या है और E ग्राफ में एज की संख्या है।
इस मैट्रिक्स की प्रत्येक पंक्ति में हम वर्टेक्स रखते हैं, और प्रत्येक कॉलम में एज रखे जाते हैं। इस प्रतिनिधित्व में एक एज e {u, v} के लिए, इसे कॉलम e के स्थान u और v के लिए 1 द्वारा मार्क किया जाएगा।
एडजेसेंसी मैट्रिक्स प्रतिनिधित्व की जटिलता
इन्सिडेंस मैट्रिक्स प्रतिनिधित्व गणना के दौरान O(V x E) मात्रा में स्पेस लेता है। पूर्ण ग्राफ के लिए एज की संख्या V(V-1)/2 होगी। इसलिए इन्सिडेंस मैट्रिक्स मेमोरी में अधिक स्पेस लेता है।
इनपुट:

आउटपुट:

एल्गोरिदम
add_edge(adj_list, u, v)
इनपुट - एक एज {u,v} के u और v, और एडजेसेंसी लिस्ट
आउटपुट - ग्राफ G का एडजेसेंसी लिस्ट
Begin
इंडेक्स u पर लिस्ट में v जोड़ें
इंडेक्स v पर लिस्ट में u जोड़ें
End
उदाहरण कोड
#include <iostream> #include <list> #include <iterator> using namespace std; void displayAdjList(listadj_list[], int v) { for (int i = 0; i < v; i++) { cout << i << "--->"; list ::iterator it; for (it = adj_list[i].begin(); it != adj_list[i].end(); ++it) { cout << *it << " "; } cout << endl; } } void add_edge(list adj_list[], int u, int v) { // v को लिस्ट u में, और u को लिस्ट v में जोड़ें adj_list[u].push_back(v); adj_list[v].push_back(u); } main(int argc, char* argv[]) { int v = 6; // ग्राफ में 6 वर्टेक्स हैं // 6 आकार का लिस्ट्स का ऐरे बनाएं list 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