C++ प्रोग्राम इंसीडेंस मैट्रिक्स का उपयोग करके ग्राफ का प्रतिनिधित्व करने के लिए

एक ग्राफ की घटना मैट्रिक्स मेमोरी में स्टोर करने के लिए ग्राफ का एक और प्रतिनिधित्व है। यह मैट्रिक्स एक वर्ग मैट्रिक्स नहीं है। आपतन मैट्रिक्स का क्रम V x E है। जहाँ V शीर्षों की संख्या है और E ग्राफ़ में किनारों की संख्या है।

इस मैट्रिक्स की प्रत्येक पंक्ति में हम कोने रख रहे हैं, और प्रत्येक कॉलम में किनारों को रखा गया है। इस निरूपण में एक किनारे e {u, v} के लिए, इसे कॉलम e के स्थान u और v के लिए 1 से चिह्नित किया जाएगा।

आसन्नता मैट्रिक्स प्रतिनिधित्व की जटिलता

• घटना मैट्रिक्स प्रतिनिधित्व O(Vx E) स्थान लेता है जबकि इसकी गणना की जाती है। पूर्ण ग्राफ के लिए किनारों की संख्या V(V-1)/2 होगी। इसलिए आपतन मैट्रिक्स मेमोरी में अधिक जगह लेता है।

इनपुट

आउटपुट

एल्गोरिदम

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]; //initial array to hold incidence matrix
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) { //function to add edge into the matrix with edge number
   inc_arr[u][ed_no] = 1;
   inc_arr[v][ed_no] = 1;
   ed_no++; //increase the edge number
}
main(int argc, char* argv[]) {
   int v = 6; //there are 6 vertices in the graph
   int e = 9; //there are 9 edges in the graph
   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