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

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


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

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

  • यह प्रतिनिधित्व अनडायरेक्टेड ग्राफ के लिए O(V+2E) और डायरेक्टेड ग्राफ के लिए O(V+E) लेता है। यदि एज की संख्या बढ़ती है, तो आवश्यक स्पेस भी बढ़ जाएगा।

इनपुट:

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

आउटपुट:

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

एल्गोरिदम

add_edge(adj_list, u, v)

इनपुट - एक एज {u,v} के u और v, और एडजेसेंसी लिस्ट

आउटपुट - ग्राफ G का एडजेसेंसी लिस्ट

Begin
    इंडेक्स u पर लिस्ट में v जोड़ें
    इंडेक्स v पर लिस्ट में u जोड़ें
End

उदाहरण कोड

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

void displayAdjList(list adj_list[], int v) {
    for (int i = 0; i < v; i++) {
        cout << i << "--->";
        list::iterator it;
        for (it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
            cout << *it << " ";
        }
        cout << endl;
    }
}

void add_edge(list adj_list[], int u, int v) {
    // v को लिस्ट u में, और u को लिस्ट v में जोड़ें
    adj_list[u].push_back(v);
    adj_list[v].push_back(u);
}

main(int argc, char* argv[]) {
    int v = 6; // ग्राफ में 6 वर्टेक्स हैं
    // 6 आकार का लिस्ट्स का ऐरे बनाएं
    list adj_list[v];
    
    add_edge(adj_list, 0, 4);
    add_edge(adj_list, 0, 3);
    add_edge(adj_list, 1, 2);
    add_edge(adj_list, 1, 4);
    add_edge(adj_list, 1, 5);
    add_edge(adj_list, 2, 3);
    add_edge(adj_list, 2, 5);
    add_edge(adj_list, 5, 3);
    add_edge(adj_list, 5, 4);
    
    displayAdjList(adj_list, v);
}

आउटपुट

0--->4 3
1--->2 4 5
2--->1 3 5
3--->0 2 5
4--->0 1 5
5--->1 2 3 4

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

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

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

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

  1. C++ प्रोग्राम: DFS का उपयोग करके निर्देशित ग्राफ की कनेक्टिविटी जांचना C++ प्रोग्राम: DFS का उपयोग करके निर्देशित ग्राफ की कनेक्टिविटी जांचना

    ग्राफ की कनेक्टिविटी जांचने के लिए, हम किसी भी ट्रैवर्सल एल्गोरिदम का उपयोग करके सभी नोड्स को पार करने का प्रयास करेंगे। ट्रैवर्सल पूरा होने के बाद, यदि कोई नोड है, जिसे विज़िट नहीं किया गया है, तो ग्राफ जुड़ा हुआ नहीं है। निर्देशित ग्राफ के लिए, हम कनेक्टिविटी जांचने के लिए सभी नोड्स से ट्रैवर्स