トポロジーソート(頂点を求める入度アルゴリズム)

トポロジのソート
隣接チェーンテーブルと逆隣接チェーンテーブルの2種類の頂点入度を求めるアルゴリズムを実現し,トポロジーソートアルゴリズムに応用する
ある:逆隣接テーブルで各頂点の入度を求める配列indegreeにもある:正隣接テーブルで頂点の入度を求める

//  6.12　    

#include 
using namespace std;

#define MVNum 100                           //     
#define OK 1
#define ERROR 0

typedef char VerTexType;

//- - - - -         - - - - -
typedef struct ArcNode{                     //   
    int adjvex;                             //           
    struct ArcNode *nextarc;                //         
}ArcNode;

typedef struct VNode{
    VerTexType data;                        //    
    ArcNode *firstarc;                      //               
}VNode, AdjList[MVNum];                     //AdjList       

typedef struct{
    AdjList vertices;                       //   
    AdjList converse_vertices;              //    
    int vexnum, arcnum;                     //          
}ALGraph;
//- - - - - - - - - - - - - - - -

//- - - - -      - - - - -
typedef struct{
    int *base;
    int *top;
    int stacksize;
}spStack;
//- - - - - - - - - - - - - - - -

int indegree[MVNum];                        //  indegree        
spStack S;

//------------      ----------------------
void InitStack(spStack &S){
    //    
    S.base = new int[MVNum];
    if(!S.base)
        exit(1);
    S.top = S.base;
    S.stacksize = MVNum;
}//InitStack

void Push(spStack &S , int i){
    //  
    if(S.top - S.base == S.stacksize)
        return;
    *S.top++ = i;
}//Push

void Pop(spStack &S , int &i){
    //  
    if(S.top == S.base)
        return;
    i = *--S.top;
}//Pop

bool StackEmpty(spStack S){
    //       
    if(S.top == S.base)
        return true;
    return false;
}//StackEmpty
//-------------------------------------------------

int LocateVex(ALGraph G , VerTexType v){
    //   v G    
    for(int i = 0; i < G.vexnum; ++i)
        if(G.vertices[i].data == v)
            return i;
        return -1;
}//LocateVex

int CreateUDG(ALGraph &G){
    //     G    、    
    int i , k;

    cout <> G.vexnum >> G.arcnum;                //      ，   
    cout << endl;

    cout << "      ， a" << endl;

    for(i = 0; i < G.vexnum; ++i){              //    ，       
        cout << "    " << (i+1) << "     :";
        cin >> G.vertices[i].data;              //     
        G.converse_vertices[i].data = G.vertices[i].data;
        //            NULL
        G.vertices[i].firstarc=NULL;
        G.converse_vertices[i].firstarc=NULL;
    }//for
    cout << endl;
    cout << "        ， a b" << endl;
    for(k = 0; k < G.arcnum;++k){               //    ，     
        VerTexType v1 , v2;
        int i , j;
        cout << "    " << (k + 1) << "       :";
        cin >> v1 >> v2;                        //            
        i = LocateVex(G, v1);  j = LocateVex(G, v2);
        //  v1 v2 G   ，    G.vertices    

        ArcNode *p1=new ArcNode;                //         *p1
        p1->adjvex=j;                           //      j
        p1->nextarc = G.vertices[i].firstarc;  G.vertices[i].firstarc=p1;
        //    *p1    vi     

        ArcNode *p2=new ArcNode;                //         *p1
        p2->adjvex=i;                           //       i
        p2->nextarc = G.converse_vertices[j].firstarc;  G.converse_vertices[j].firstarc=p2;
        //    *p1    vi     
    }//for
    return OK;
}//CreateUDG

// void FindInDegree(ALGraph G){
//  //                  indegree 
//  int i , count;
//
//  for(i = 0 ; i < G.vexnum ; i++){
//      count = 0;
//      ArcNode *p = G.converse_vertices[i].firstarc;
//      if(p){
//          while(p){
//              p = p->nextarc;
//              count++;
//          }
//      }
//      indegree[i] = count;
//  }
// }//FindInDegree
 void FindInDegree(ALGraph G)
 { //           
   int i;
   ArcNode *p;
   for(i=0;iadjvex]++;
       p = p->nextarc;
     }
   }
 }

int TopologicalSort(ALGraph G , int topo[]){
    //   G         
    // G   ，   G       topo[]   OK，  ERROR
    int i , m;
    FindInDegree(G);                            //            indegree 
    InitStack(S);                               // S     
    for(i = 0; i < G.vexnum; ++i)
        if(!indegree[i]) Push(S, i);            //   0   
    m = 0;                                      //       ，   0
    while(!StackEmpty(S)){                      // S  
        Pop(S, i);                              //     vi  
        topo[m]=i;                              // vi         topo 
        ++m;                                    //       
        ArcNode *p = G.vertices[i].firstarc;    //p  vi       
        while(p){
            int k = p->adjvex;                  //vk vi    
            --indegree[k];                      //vi          1
            if(indegree[k] ==0)  Push(S, k);    //     0，   
            p = p->nextarc;                     //p    vi       
        }//while
    }//while

    if(m < G.vexnum)  return ERROR;             //       
    else return OK;
}//TopologicalSort

int main(){
    cout << "************  6.12　    **************" << endl << endl;
    ALGraph G;
    CreateUDG(G);
    int *topo = new int [G.vexnum];

    cout << endl;
    cout << "       、        !" << endl << endl;

    if(TopologicalSort(G , topo)){
        cout << "            ：";
        for(int j = 0 ; j < G.vexnum; j++){
            if(j != G.vexnum - 1)
                cout << G.vertices[topo[j]].data << " , ";
            else
                cout << G.vertices[topo[j]].data << endl << endl;
        }//for
    }
    else
        cout << "     ，        ！" <