C++ में ग्राफ स्ट्रक्चर्ड स्टैक का कार्यान्वयन

इस C++ प्रोग्राम में हम ग्राफ स्ट्रक्चर्ड स्टैक को लागू करते हैं।

एल्गोरिदम

Begin
    Function graphStructuredStack(int **adjMat, int s, int bNode):
        ऐरे adjMat, स्रोत s और बॉटम नोड bNode लें
        stackFound = false इनिशियलाइज़ करें
        sVertex = 1 से noOfNodes तक
            dVertex = 1 से noOfNodes तक
                this->adjMat[sVertex][dVertex] = adjMat[sVertex][dVertex]
            Done
        Done
        स्रोत को mystack में पुश करें।
        while (!mystack.empty())
            element = mystack.top()
            गंतव्य d = 1 इनिशियलाइज़ करें
            while (d <= noOfNodes)
                if (this->adjMat[element][d] == 1)
                    गंतव्य को mystack में पुश करें
                    par[d] = element
                    this->adjMat[element][d] = 0
                    if (d == bNode)
                        stackFound = true सेट करें
                        ब्रेक
                    done
                element = d
                d = 1
                कंटिन्यू
            done
            d बढ़ाएं
            done
            if (stackFound)
                node = bNode से node != s तक
                    node को istack में पुश करें
                s को istack में पुश करें
                stackList.push_back(istack)
                stackFound = false अपडेट करें
            done
        mystack से तत्व पॉप करें
        done
        इटरेटर = stackList.begin()
        while (इटरेटर != stackList.end())
            इटरेटर बढ़ाएं
            while (!stack.empty())
                स्टैक के शीर्ष तत्व को प्रिंट करें
                स्टैक से तत्व पॉप करें
            done
        done
End.

उदाहरण कोड

#include <iostream>
#include <cstdlib>
#include <stack>
#include <list>
using namespace std;

class GraphStructuredStack {
private:
    list< stack<int> > stackList;
    stack<int> mystack;
    int noOfNodes;
    int **adjMat;
    int *par;

public:
    GraphStructuredStack(int noOfNodes) {
        this->noOfNodes = noOfNodes;
        adjMat = new int*[noOfNodes + 1];
        this->par = new int[noOfNodes + 1];
        for (int i = 0; i < noOfNodes + 1; i++)
            adjMat[i] = new int[noOfNodes + 1];
    }

    void graphStructuredStack(int **adjMat, int s, int bNode) {
        bool stackFound = false;
        for (int sVertex = 1; sVertex <= noOfNodes; sVertex++) {
            for (int dVertex = 1; dVertex <= noOfNodes; dVertex++) {
                this->adjMat[sVertex][dVertex] = adjMat[sVertex][dVertex];
            }
        }
        mystack.push(s);
        int element, d;
        while (!mystack.empty()) {
            element = mystack.top();
            d = 1;
            while (d <= noOfNodes) {
                if (this->adjMat[element][d] == 1) {
                    mystack.push(d);
                    par[d] = element;
                    this->adjMat[element][d] = 0;
                    if (d == bNode) {
                        stackFound = true;
                        break;
                    }
                    element = d;
                    d = 1;
                    continue;
                }
                d++;
            }
            if (stackFound) {
                stack<int> istack;
                for (int node = bNode; node != s; node = par[node]) {
                    istack.push(node);
                }
                istack.push(s);
                stackList.push_back(istack);
                stackFound = false;
            }
            mystack.pop();
        }
        list<stack<int> >::iterator iterator;
        iterator = stackList.begin();
        while (iterator != stackList.end()) {
            stack<int> stack = *iterator;
            iterator++;
            while (!stack.empty()) {
                cout << stack.top() << "\t";
                stack.pop();
            }
            cout << endl;
        }
    }
};

int main() {
    int noofnodes;
    cout << "Enter number of nodes: ";
    cin >> noofnodes;
    GraphStructuredStack gss(noofnodes);
    int source, bottom;
    int **adjMatrix;
    adjMatrix = new int*[noofnodes + 1];
    for (int i = 0; i < noofnodes + 1; i++)
        adjMatrix[i] = new int[noofnodes + 1];
    cout << "Enter the graph matrix: " << endl;
    for (int sVertex = 1; sVertex <= noofnodes; sVertex++) {
        for (int dVertex = 1; dVertex <= noofnodes; dVertex++) {
            cin >> adjMatrix[sVertex][dVertex];
        }
    }
    cout << "Enter the source node: ";
    cin >> source;
    cout << "Enter the bottom node: ";
    cin >> bottom;
    cout << "The stacks are: " << endl;
    gss.graphStructuredStack(adjMatrix, source, bottom);
    return 0;
}

आउटपुट

Enter number of nodes: 4
Enter the graph matrix:
1 1 1 0
0 1 1 0
1 0 0 0
1 1 1 1
Enter the source node: 3
Enter the bottom node: 1
The stacks are:
3 1