グラフ構造化スタックを実装する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