C ++程序实现图结构化堆栈
在此C++程序中，我们实现了图结构堆栈。
算法
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