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

परिचय

यह प्रोग्राम इनसिडेंस लिस्ट का उपयोग करके ग्राफ को दर्शाता है और इस एल्गोरिदम की समय जटिलता O(e) है।

एल्गोरिदम

वर्टेक्स 'v' और एज 'e' की संख्या का इनपुट लें और e[][] में दिए गए ग्राफ के 'e' वर्टेक्स जोड़े का इनपुट लें। प्रत्येक एज के लिए उस कनेक्शन में शामिल संबंधित वर्टेक्स प्रिंट करें।

उदाहरण कोड

#include <iostream>
using namespace std;

int main() {
    int i, v, e, j, c;
    cout << "ग्राफ के वर्टेक्स की संख्या दर्ज करें: ";
    cin >> v;
    cout << "\nग्राफ के एज की संख्या दर्ज करें: ";
    cin >> e;
    int edge[e][2];
    for (i = 0; i < e; i++) {
        cout << "\nएज " << i+1 << " के लिए वर्टेक्स जोड़ा दर्ज करें";
        cout << "\nV(1): ";
        cin >> edge[i][0];
        cout << "V(2): ";
        cin >> edge[i][1];
    }
    cout << "\n\nदिए गए ग्राफ के लिए इनसिडेंस लिस्ट प्रतिनिधित्व: ";
    for (i = 0; i < e; i++) {
        // प्रत्येक वर्टेक्स के लिए, उसके आसन्न वर्टेक्स प्रिंट करें।
        cout << "\n\tE(" << i+1 << ") -> { ";
        cout << "V(" << edge[i][0] << ") , " << "V(" << edge[i][1] << ")";
        cout << " }";
    }
    return 0;
}

आउटपुट

ग्राफ के वर्टेक्स की संख्या दर्ज करें: 3
ग्राफ के एज की संख्या दर्ज करें: 4
एज 1 के लिए वर्टेक्स जोड़ा दर्ज करें
V(1): 2
V(2): 1
एज 2 के लिए वर्टेक्स जोड़ा दर्ज करें
V(1): 1
V(2): 2
एज 3 के लिए वर्टेक्स जोड़ा दर्ज करें
V(1): 3
V(2): 2
एज 4 के लिए वर्टेक्स जोड़ा दर्ज करें
V(1): 2
V(2): 3
दिए गए ग्राफ के लिए इनसिडेंस लिस्ट प्रतिनिधित्व:
E(1) -> { V(2) , V(1) }
E(2) -> { V(1) , V(2) }
E(3) -> { V(3) , V(2) }
E(4) -> { V(2) , V(3) }