邻接表版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[100];
}Edge[MAX];
struct Node{
       int key;
       Node *next;
       Node(){
           next = 0;
       }
};
class LinkQueue{
      public:
         LinkQueue();
        
         bool IsEmpty();
         void EnQueue(int key);
         void DeQueue(int& key);
     
      private:
         Node *head,*tail;
};
LinkQueue::LinkQueue(){
         head = new Node;
         tail = head;
}
bool LinkQueue::IsEmpty(){
     return head==tail;
}
void LinkQueue::EnQueue(int key){
     Node* t = new Node;
    
     t->key = key;
     tail->next = t;
     tail = t;
}
void LinkQueue::DeQueue(int& key){
     if(IsEmpty() ) return;
    
     Node* p = head->next;
     head->next = p->next;
     key = p->key;
    
     if(p==tail) tail = head;
     delete p;
}
void BFS(int s,int f[],int d[]){
     LinkQueue q;
     int u,v,i,j;
     int color[MAX];
    
     init(f);
     init(d);
     init(color);
     f[s] = 0;
     d[s] = 0;
     color[s] = BLACK;
     q.EnQueue(s);
    
     while(!q.IsEmpty() ){
           q.DeQueue(v);
           color[v] = GRAY;
           for(i=0;i<Edge[v].n;i++){
               u = Edge[v].adjvex[i];
               if(color[u]==WHITE){
                  q.EnQueue(u);
                  color[u] = GRAY;
                  d[u] = d[v]+1;
                  f[u] = v;
               }
           }
           color[v] = BLACK;
     }
}