DFS版拓扑排序

2009-03-24 17:00

#include<iostream>
using namespace std;
const int MAX = 100;
#define BLACK 1
#define WHITE 0
#define GRAY -1
struct{
       int n;
       int adjvex[MAX];
}Edge[MAX];
int List[MAX],k;
int color[MAX];
void DFS(int cur);
void TopologicalSort(int n);
int main(void){
    int n,e,a,b;
    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;
    }
   
    TopologicalSort(n);
   
    for(i=0;i<n;i++)
        cout<<List[i]<<" ";
   
    system("pause");
    return 0;
}
void TopologicalSort(int n){
     int i,j;
    
     k = n;
     memset(color,0,sizeof(color) );
     DFS(1);
}
void DFS(int cur){
     int i,next;
    
     color[cur] = GRAY;
     for(i=0;i<Edge[cur].n;i++){
         next = Edge[cur].adjvex[i];
        
         if(color[next]==WHITE) DFS(next);
         else if(color[next]==GRAY){//有回边出现意味着有回路

              cout<<"Circuit exists!"<<endl;
              system("pause");
              exit(0);
         }
     }
    
     color[cur] = BLACK;
     List[--k] = cur;//按节点完成的顺序入列

}