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

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

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

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

इनपुट:

आउटपुट:

एल्गोरिदम

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