Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


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

एडजेसेंसी मैट्रिक्स प्रतिनिधित्व की जटिलता

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

इनपुट

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

आउटपुट


0
1
2
3
4
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]; // एडजेसेंसी मैट्रिक्स प्रारंभ में 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) {
    // मैट्रिक्स में एज जोड़ने का फंक्शन
    vertArr[u][v] = 1;
    vertArr[v][u] = 1;
}

main(int argc, char* argv[]) {
    int v = 6; // ग्राफ में 6 वर्टेक्स हैं
    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 0
1 0 1 0 0 1
1 1 0 0 0 1
0 1 1 1 1 0

  1. C++ प्रोग्राम: लिंक्ड लिस्ट का उपयोग करके ग्राफ प्रतिनिधित्व करना C++ प्रोग्राम: लिंक्ड लिस्ट का उपयोग करके ग्राफ प्रतिनिधित्व करना

    एक ग्राफ का इन्सिडेंस मैट्रिक्स ग्राफ को मेमोरी में स्टोर करने का एक और प्रतिनिधित्व है। यह मैट्रिक्स एक वर्ग मैट्रिक्स नहीं है। इन्सिडेंस मैट्रिक्स का ऑर्डर V x E होता है। जहां V वर्टेक्स की संख्या है और E ग्राफ में एज की संख्या है। इस मैट्रिक्स की प्रत्येक पंक्ति में हम वर्टेक्स रखते हैं, और प्रत

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

    एक ग्राफ का एडजेसेंसी लिस्ट प्रतिनिधित्व एक लिंक्ड लिस्ट प्रतिनिधित्व है। इस प्रतिनिधित्व में हमारे पास लिस्ट्स का एक ऐरे होता है। ऐरे का आकार V होता है। यहां V वर्टेक्स की संख्या है। दूसरे शब्दों में, हम कह सकते हैं कि हमारे पास V संख्या की अलग-अलग लिस्ट्स को स्टोर करने के लिए एक ऐरे है। यदि एक लि

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

    एक ग्राफ का इन्सिडेंस मैट्रिक्स ग्राफ को मेमोरी में स्टोर करने का एक और प्रतिनिधित्व है। यह मैट्रिक्स एक वर्ग मैट्रिक्स नहीं है। इन्सिडेंस मैट्रिक्स का ऑर्डर V x E होता है। जहां V वर्टेक्स की संख्या है और E ग्राफ में एज की संख्या है। इस मैट्रिक्स की प्रत्येक पंक्ति में हम वर्टेक्स रखते हैं, और प्रत