एक ग्राफ का आसन्न मैट्रिक्स आकार V x V का एक वर्ग मैट्रिक्स है। V, ग्राफ G के शीर्षों की संख्या है। इस मैट्रिक्स में प्रत्येक पक्ष में V कोने चिह्नित हैं। यदि ग्राफ़ में i से j कोने तक कुछ किनारे हैं, तो i th पर आसन्न मैट्रिक्स में पंक्ति और जम्मू वें कॉलम में यह 1 (या भारित ग्राफ़ के लिए कुछ गैर-शून्य मान) होगा, अन्यथा वह स्थान 0 पर रहेगा।
आसन्नता मैट्रिक्स प्रतिनिधित्व की जटिलता
-
आसन्न मैट्रिक्स प्रतिनिधित्व O(V 2 . लेता है ) अंतरिक्ष की मात्रा जब इसकी गणना की जाती है। जब ग्राफ़ में किनारों की अधिकतम संख्या और किनारों की न्यूनतम संख्या हो, तो दोनों ही मामलों में आवश्यक स्थान समान होगा।
इनपुट
आउटपुट
<थ चौड़ाई="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