सी ++ प्रोग्राम एडजेंसी मैट्रिक्स को लागू करने के लिए

एक ग्राफ का आसन्न मैट्रिक्स आकार V x V का एक वर्ग मैट्रिक्स है। V ग्राफ G के शीर्षों की संख्या है। इस मैट्रिक्स में प्रत्येक पक्ष में V कोने चिह्नित हैं। यदि ग्राफ़ में i से j कोने तक कुछ किनारे हैं, तो i ^th पर आसन्न मैट्रिक्स में पंक्ति और जम्मू ^वें कॉलम में यह 1 (या भारित ग्राफ़ के लिए कुछ गैर-शून्य मान) होगा, अन्यथा वह स्थान 0 पर रहेगा।

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

• गणना करते समय आसन्न मैट्रिक्स प्रतिनिधित्व O (V2) स्थान लेता है। जब ग्राफ़ में किनारों की अधिकतम संख्या और किनारों की न्यूनतम संख्या हो, तो दोनों ही मामलों में आवश्यक स्थान समान होगा।

इनपुट:

आउटपुट:

एल्गोरिदम

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]; //the adjacency matrix initially 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) {       //function to add edge into the matrix
   vertArr[u][v] = 1;
   vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
   int v = 6;    //there are 6 vertices 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);
}

आउटपुट

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