C++ में ट्री के लिए प्रुफर कोड बनाना

प्रुफर कोड एक ट्री को विशिष्ट रूप से पहचानता है जिसे उपयोगकर्ता द्वारा ग्राफ प्रतिनिधित्व के रूप में 1 से p तक लेबल के साथ दिया जाता है। इस ट्री में p (मान उपयोगकर्ता द्वारा दिया गया) नोड लेबल होते हैं। इसमें p - 2 मानों का अनुक्रम होता है।

एल्गोरिदम

Begin
    i, j, ver, edg, minimum, p को इंटीजर डेटाटाइप के रूप में घोषित करें
    "Enter the number of vertexes: " प्रिंट करें
    ver का मान दर्ज करें
    edg = ver-1 इनिशियलाइज़ करें
    EDG[edg][2], DG[ver+1] को इंटीजर डेटाटाइप के रूप में घोषित करें
        DG[ver+1] = {0} से इनिशियलाइज़ करें
    "This tree has (edg का मान) edges for (ver का मान) vertexes" प्रिंट करें
    "There are (edg का मान) pairs of vertexes in the tree" प्रिंट करें
    for(i = 0; i < edg; i++)
        "Enter the value of vertex pair for edge " प्रिंट करें
        "Enter the value of V(1) vertex: " प्रिंट करें
        EDG[i][0] का मान दर्ज करें
        "Enter the value of V(2) vertex: " प्रिंट करें
        EDG[i][1] का मान दर्ज करें
        DG[EDG[i][0]]++
        DG[EDG[i][1]]++
    "The Prufer code for the tree is: { " प्रिंट करें
        for(i = 0; i < ver-2; i++)
            minimum = 10000
            for(j = 0; j < edg; j++)
                if(DG[EDG[j][0]] == 1) then
                    if(minimum > EDG[j][0]) then
                        minimum = EDG[j][0]
                        p = j
                if(DG[EDG[j][1]] == 1) then
                    if(minimum > EDG[j][1]) then
                        minimum = EDG[j][1]
                        p = j
            DG[EDG[p][0]]--
            DG[EDG[p][1]]--
            if(DG[EDG[p][0]] == 0) then
                EDG[p][1] का मान प्रिंट करें
            else
                EDG[p][0] का मान प्रिंट करें
    "}" प्रिंट करें
End

उदाहरण

#include <iostream>
using namespace std;

int main() {
    int i, j, ver, edg, minimum, p;
    cout << "Enter the number of vertexes: ";
    cin >> ver;
    cout << endl;
    edg = ver - 1;
    int EDG[edg][2], DG[ver+1] = {0};
    cout << "This tree has " << edg << " edges for " << ver << " vertexes.\n";
    cout << "There are " << edg << " pairs of vertexes in the tree.\n";
    
    for (i = 0; i < edg; i++) {
        cout << "Enter the value of vertex pair for edge " << i+1 << ":\n";
        cout << "Enter the value of V(1) vertex: ";
        cin >> EDG[i][0];
        cout << "Enter the value of V(2) vertex: ";
        cin >> EDG[i][1];
        DG[EDG[i][0]]++;
        DG[EDG[i][1]]++;
    }
    
    cout << "\nThe Prufer code for the tree is: { ";
    // दिए गए ट्री का प्रुफर कोड प्रिंट करें
    for (i = 0; i < ver-2; i++) {
        minimum = 10000;
        for (j = 0; j < edg; j++) {
            if (DG[EDG[j][0]] == 1) {
                if (minimum > EDG[j][0]) {
                    minimum = EDG[j][0];
                    p = j;
                }
            }
            if (DG[EDG[j][1]] == 1) {
                if (minimum > EDG[j][1]) {
                    minimum = EDG[j][1];
                    p = j;
                }
            }
        }
        DG[EDG[p][0]]--; // चयनित वर्टेक्स को हटाकर उसकी डिग्री 0 करें
        DG[EDG[p][1]]--; // दूसरे वर्टेक्स की डिग्री घटाएं, क्योंकि हमने EDG हटा दिया
        if (DG[EDG[p][0]] == 0)
            cout << EDG[p][1] << " ";
        else
            cout << EDG[p][0] << " ";
    }
    cout << "}";
    return 0;
}

आउटपुट

Enter the number of vertexes: 5
This tree has 4 edges for 5 vertexes.
There are 4 pairs of vertexes in the tree.
Enter the value of vertex pair for edge 1:
Enter the value of V(1) vertex: 2
Enter the value of V(2) vertex: 3
Enter the value of vertex pair for edge 2:
Enter the value of V(1) vertex: 5
Enter the value of V(2) vertex: 6
Enter the value of vertex pair for edge 3:
Enter the value of V(1) vertex: 7
Enter the value of V(2) vertex: 8
Enter the value of vertex pair for edge 4:
Enter the value of V(1) vertex: 9
Enter the value of V(2) vertex: 10
The Prufer code for the tree is: { 4 8 4 }