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

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

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

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

आउटपुट

<थ चौड़ाई="10">0
<थ चौड़ाई="10">1
<थ चौड़ाई="10">2
<थ चौड़ाई="10">3
<थ चौड़ाई="10">4
<थ चौड़ाई="9">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]; //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