图练习

下列代码的功能是对一个给定的图G执行拓扑排序，其中TopNum[]从1开始记录拓扑序。

void Topsort( Graph G )
{
   Queue Q;
   Vertex V, W;
   NodePtr ptr;
   int counter = 0;

   Q = CreateEmptyQueue(NumVertex);
   for ( V=0; V<G->NumV; V++ )
      if ( Indegree[V] == 0 )
         Enqueue(V, Q);
   while ( !IsEmpty(Q) ){
      V = Dequeue( Q );
      TopNum[V] =++counter 3分;
      for ( ptr=G->List[V]; ptr; ptr=ptr->Next) {
         W = ptr->Vertex;
         if (  --Indegree[W] 3分 == 0 )
            Enqueue(W, Q);
      }
   }
   if ( counter != NumVertex )
      printf("ERROR: Graph has a cycle.\n");
   DisposeQueue(Q);
}

#include <iostream>
using namespace std;

#define MVNum 100    
#define BDNum MVNum * (MVNum - 1)
#define OK 1    
#define ERROR 0 

typedef char VerTexType;

typedef struct ArcNode{
    int adjvex;
    int weight;
    struct ArcNode *nextarc;
}ArcNode; 

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

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

int indegree[MVNum];//顶点入度
int ve[BDNum];//事件vi的最早发生时间
int vl[BDNum];//事件vi的最迟发生时间
int topo[MVNum];//记录拓扑序列的顶点序号

int LocateVex(ALGraph G , VerTexType v);//确定点v在G中的位置
int CreateUDG(ALGraph &G);//创建邻接表和逆邻接表
void FindInDegree(ALGraph G,int indegree[]);//求出各顶点的入度存入数组indegree中
int TopologicalOrder(ALGraph G , int topo[]);//生成G的一个拓扑序列topo[]

int CriticalPath(ALGraph G){ 
    int n , i , k , j , e , l,flag=1;
    if (!TopologicalOrder(G, topo))  return ERROR; 
    n = G.vexnum;                                  
    for(i = 0; i < n; i++) 
       ve[i] = 0; 

    for(i = 0;i < n; i++){                 
        k = topo[i];                
        ArcNode *p = G.vertices[k].firstarc; 
        while(p != NULL){  
            j = p->adjvex;                 
            if(ve[j] < ve[k] + p->weight2分)
                ve[j] = ve[k] + p->weight2分;     
            p = p->nextarc; 
        }  
    } 

    for(i=0;i<n;i++)
    vl[i]=ve[n-1];

    for(i = n - 1;i >= 0; i--){               
        k = topo[i];             
        ArcNode *p = G.vertices[k].firstarc; 
        while(p != NULL){  
            j = p->adjvex;                   
            if(vl[k] > vl[j] - p->weight2分)
                vl[k] = vl[j] - p->weight2分;       
            p = p->nextarc; 
        } 
    } 

    for(i = 0;i < n; i++){ 
        ArcNode *p = G.vertices[i].firstarc;  
        while(p != NULL) {    
            j = p->adjvex;    
            e =ve[i]; 2分;
            l =vl[j] - p->weight; 2分;
            if(e == l) {
                if(flag){
                 cout << G.vertices[i].data << "->" << G.vertices[j].data;flag=0;    
                }
                else
                 cout <<  "," << G.vertices[i].data << "->" << G.vertices[j].data;
            }
            p = p->nextarc; 
        }  
    }   
    return OK;
}

int main(){
    ALGraph G;
    CreateUDG(G);
    int *topo = new int [G.vexnum];
    CriticalPath(G);
    return 0;
}