邻接表非递归带时间戳版BFS

 2009-03-24 16:24 

#include<iostream>
using namespace std;

#define init(x) memset(x,0,sizeof(x) )
#define GRAY -1
#define BLACK 1
#define WHITE 0

const int MAX = 100;

struct{
       int n;
       int adjvex[MAX];
       int edgetype[MAX];
}Edge[MAX];

class Stack{
      public:
         Stack(int);
        
         bool IsEmpty(){
              return top==-1;
         }
         void Push(int key);
         void Pop(int& key);
         void GetTop(int& key);
        
      private:
         int* data;
         int top;
         int max_size;
};

Stack::Stack(int n = 100){
       data = new int[n];
       top = -1;
       max_size = n;
}

void Stack::Push(int key){
     if(top==max_size-1) return;
    
     data[++top] = key;
}

void Stack::Pop(int& key){
     if(IsEmpty() ) return;
    
     key = data[top--];
}

void Stack::GetTop(int& key){
     if(IsEmpty() ) return;
    
     key = data[top];
}

void DFS(int source,int p[],int s[],int f[]){
     Stack st;
     int color[MAX],u,v,t,i,j;
    
     init(color);
     st.Push(source);
     t = 0;
    
     while(!st.IsEmpty() ){
           st.GetTop(v);
           t++;
           if(color[v]==WHITE){
              color[v] = GRAY;
              s[v] = t;
              for(i=0;i<Edge[v].n;i++){
                  u = Edge[v].adjvex[i];
                  if(color[u]==WHITE){
                     st.Push(u);
                     p[u] = v;
                     Edge[v].edgetype[i] = WHITE;
                  }
                  else if(color[u]==BLACK)
                       Edge[v].edgetype[i] = BLACK;
                  else Edge[v].edgetype[i] = GRAY;
              }
           }
           else{
               color[v] = BLACK;
               st.Pop(v);
               f[v] = t;
           }
     }
}
    
    
int main(void){
    int n,e,a,b;
    int source,p[MAX],s[MAX],f[MAX];
    int i,j;
   
    cout<<"Input vexnum&&edgenum:";
    cin>>n>>e;
    for(i=1;i<=n;i++)
        Edge[i].n = 0;
   
    cout<<"Input the edges:";
    for(i=0;i<e;i++){
        cin>>a>>b;
        Edge[a].adjvex[ Edge[a].n++ ] = b;
    }
   
    cout<<"Input source vex:";
    cin>>source;
   
    init(p);
    init(s);
    init(f);
    DFS(source,p,s,f);
   
    for(i=1;i<=n;i++)
       cout<<"p["<<i<<"]:"<<p[i]<<"\t"<<
             "s["<<i<<"]:"<<s[i]<<"\t"<<
             "f["<<i<<"]:"<<f[i]<<endl;
   
    for(i=1;i<=n;i++)
        for(j=0;j<Edge[i].n;j++){
            a = i;
            b = Edge[i].adjvex[j];
            cout<<"("<<a<<","<<b<<"):"<<Edge[i].edgetype[j]<<"\t";
        }
    cout<<endl;
   
    system("pause");
    return 0;
}