图论--关键路径
最近忙着做作业。主要是《代数与图论》的一些算法的实现，五一估计不用过了，数据压缩要看论文，信息检索要做实验，实验室还要实现模糊匹配的改进。。。我怎么选了这么些难搞的课啊。。编程珠玑看来要被无限地搁置了
?
说一下关键路径的实现吧。
其实主要也是从网上看来的。
?
关键路径的相关概念：
?
1. AOE图：在工程上，很多任务之间常常有先后顺序的要求，例如，建房子前要先打桩等。任务与任务之前有前后顺序要求时，在图上表现为一个有向边，从任务（1）指向任务（2），并且这中间需要一定的时间间隔，往往把时间间隔做为两个任务间的边的权重。这样的图叫AOE图（Activity on Edge）。下图即为一个AOE图（呵呵，我也是从某个PPT上拷下来的）：
?
2. 最早发生时间：最早发生时间是指从源点v1到任意vi的最长路径，叫事件中vi的最早发生时间。（因为必须等前面需要完成的任务都完成后，才能做vi）
???? 设ve(i)为vi的最早发生时间，有ve(1)=0, ve(i) = max{ve(i)+dut<j,k>}, <i,j>is in T
???? T是所有以j为弧头的弧集合，dut<i,j>表示从i到j需要的时间。
?????（如上图结点7， ve(7)=max{ve(4)+a8, ve(5)+a2}）
3. 最迟发生时间：最迟发生时间是指从在不推迟整个工程完成的前提下，ai的最迟必须开始进行的时间。
??? 设vl(i)为vi的最迟发生时间，有vl(n)=ve(n), vl(i) = min{vl(j)-dut<i,j>}, <i j>is in S
??? S是所有以i为弧尾的弧的集合.
??? (如上图，vl(5)=min{vl(7)-a5, vl(8)-a10})
4. 当ve(i)+dut<i,j>=vl(j)时，弧<i, j>为关键路径上的弧。
?
这样的话，我们可以先通过拓扑排序一路计算出每个结点的最早发生时间，最后将ve(n)赋予vl(n)然后再一路返回来求每个结点的最迟发生时间，即可求出关键路径上的弧了。
?
算法流程主要是做拓扑排序，这个过程可以顺便求出各个结点的最早发生时间。求结点的最迟发生时间是一个逆排序过程。具体实现的时候，我把队列做成两头通的，用front和rear来表示队列的头部跟尾部。拓扑排序的时候从队尾加进去，逆排序的时候从队尾取出来。
首先是数据结构的表示。我用一个邻接表表示一个图。因为做拓扑排序的时候，我是通过将入度为0的点压入栈中，所以在邻接表的头部我记录了相关顶点的入度。
?
具体代码如下：
#include<stdio.h>//邻接结点的ID及边上的权重。typedef struct Node{int nodeID;int dut;struct Node* next;}adjNode;//表头，结点nodeID的入度，邻接结点typedef struct{int indgr;int nodeID;adjNode* adj;adjNode* tail; //为方便加入新结点而设计的。}vexNode;void criticalPath( vexNode* g, int numP ){//data structure for calculationint* stack = (int*)malloc( sizeof(int)*numP );int front = 0, rear = -1;int* ve = (int*)malloc( sizeof(int)*numP );int* vl = (int*)malloc( sizeof(int)*numP );int i;for( i=0; i<numP; i++ )if( g[i].indgr == 0 )stack[++rear] = i;for( i=0; i<numP; i++ ) ve[i] = 0;while( rear>=front ){int j=stack[front++];adjNode* tmp;for( tmp=g[j].adj; tmp!=NULL; tmp=tmp->next ){(g[tmp->nodeID].indgr)--;if( g[tmp->nodeID].indgr == 0 )stack[++rear]=tmp->nodeID;//calculate the earliest start timeif( ve[tmp->nodeID] < ve[j]+tmp->dut )ve[tmp->nodeID] = ve[j]+tmp->dut;}}if( rear < numP-1 ){printf( "circle in the graph\n" );return ;}//lastest start timefor( i =0; i<numP; i++ )vl[i] = ve[numP-1];while( rear>=0 ){int j=stack[rear--];adjNode* tmp;for( tmp=g[j].adj; tmp!=NULL; tmp=tmp->next ){if( vl[j] > vl[tmp->nodeID] - tmp->dut )vl[j] = vl[tmp->nodeID] - tmp->dut;}}front = 0;rear = numP-1;//collect the critical taskswhile( rear>=front ){int j=stack[front++];adjNode* tmp;for( tmp=g[j].adj; tmp!=NULL; tmp=tmp->next ){if( ve[j] == vl[tmp->nodeID]-tmp->dut )printf( "<%d, %d>\n", j, tmp->nodeID );}}free( stack );?free( ve );?free( vl );}main(){int verNum, actNum;int i;printf( "enter the number of vertices: " );scanf( "%d", &verNum );vexNode* g = (vexNode*)malloc( sizeof(vexNode)*verNum );//initializationfor( i=0; i<verNum; i++ ){g[i].indgr = 0;g[i].nodeID = i;g[i].adj = NULL;g[i].tail = NULL;}printf( "\nhow many activities are there? " );scanf( "%d", &actNum );printf( "\nenter them in the form of | startNode endNode duration | one by one\n" );int tmpS, tmpE, tmpD;//construct the map for the projectfor( i=0; i<actNum; i++ ){scanf( "%d %d %d", &tmpS, &tmpE, &tmpD );(g[tmpE].indgr)++;adjNode* tmpN = (adjNode*) malloc( sizeof(adjNode) );tmpN->nodeID = tmpE;tmpN->dut = tmpD;tmpN->next = NULL;if( g[tmpS].tail == NULL ){g[tmpS].adj = tmpN;g[tmpS].tail = tmpN;}else{g[tmpS].tail->next = tmpN;g[tmpS].tail = tmpN;}}//search the critical pathcriticalPath( g, verNum );}?
?
?