拓扑排序

2008-10-31 20:19

#include<iostream>
using namespace std;
const int INC = 20;
class Stack{
      public:
      Stack(){ st = new int[INC]; top = -1; }
      Stack(int i);
      void Push(int i);
      void Pop(int& i);
      bool IsEmpty(){ return top==-1; }
      private:
      int* st;
      int top;
      int max_size;
};
bool adjmat[10][10] = {0};
int vexnum = 6,vexinfo[10];
bool TopologicalSort();
int main(void){
    adjmat[0][1] = 1;
    adjmat[0][2] = 1;
    adjmat[0][3] = 1;
    adjmat[2][1] = 1;
    adjmat[3][4] = 1;
    adjmat[2][4] = 1;
    adjmat[5][3] = 1;
    adjmat[5][4] = 1;
   
    cout<<"Input vexinfo:";
    for(int i=0;i<vexnum;i++)
        cin>>vexinfo[i];
       
    if(TopologicalSort())
       cout<<"No cycle";
    else cout<<"Cycle exists!";
    cout<<endl;
   
    system("pause");
    return 0;
}
Stack::Stack(int i){
     st = new int[i+INC];
     top = -1;
     max_size = i+INC;
}
void Stack::Push(int i){
     if(top+1>=max_size){
        cout<<"Stack full!"<<endl;
        system("pause");
        exit(0);
     }
     st[++top] = i;
}
       
void Stack::Pop(int& i){
     if(IsEmpty()){
        cout<<"Stack empty!"<<endl;
        system("pause");
        exit(0);
     }
     i = st[top];
     top--;
}
bool TopologicalSort(){
     int indeg[10];
     int i,j,count=0;
     Stack stc(vexnum);
     memset(indeg,0,sizeof(indeg));
    
     for(i=0;i<vexnum;i++)
         for(j=0;j<vexnum;j++)
             if(adjmat[j][i]) indeg[i]++;
    
     for(i=0;i<vexnum;i++)
         if(!indeg[i]) stc.Push(i);
    
     while(!stc.IsEmpty()){
           stc.Pop(i);
           cout<<i+1<<" "<<vexinfo[i]<<endl;
           count++;
           for(j=0;j<vexnum;j++)
               if(adjmat[i][j])
                  if(--indeg[j]==0) stc.Push(j);
     }
     cout<<endl;
    
     if(count==vexnum) return true;
     else return false;
}