이 C++ 프로그램에서 Graph Structured Stack을 구현합니다.
알고리즘
Begin Function graphStructuredStack(int **adjMat, int s,int bNode): Take an array adjMat, source s and bottom node bNode initialize stackFound = false for sVertex = 1 to noOfNodes for dVertex = 1 to noOfNodes this->adjMat[sVertex][dVertex] = adjMat[sVertex][dVertex] Done Done Push source into mystack. while (!mystack.empty()) element = mystack.top() Initialize destination, d=1 while (d <= noOfNodes) if (this->adjMat[element][d] == 1) Push destination into mystack par[d] = element this->adjMat[element][d] = 0 if (d == bNode) Set, stackFound = true Break done element = d d = 1 Continue done Increment d done if (stackFound) for node = bNode to node!=s push node into istack Push s into istack stackList.push_back(istack) update, stackFound = false done pop element from mystack done iterator = stackList.begin() while (iterator != stackList.end()) increment iterator while (!stack.empty()) print top element of stack pop element from stack 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: 31