【数据结构】树和图04——关键路径

输入：为顶点个数n，弧的个数m，各个顶点的序号，接下来是m个弧的起点、终点、权值
输出：关键路径包括的各个弧
样例输入：
9 11
1
2
3
4
5
6
7
8
9
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
7 9 2
8 9 4
样例输出：
v1->v2,t=0
v2->v5,t=6
v5->v8,t=7
v5->v7,t=7
v7->v9,t=16
v8->v9,t=14

#include   
#include   
#define max 20  
int visited[max];
typedef char vextype;  
typedef struct arcnode  
{  
    int adjvex;     //顶点位置  
    struct arcnode * nextarc;          //指向下一个表结点  
    int info;     //权值
}arcnode; //边结点
typedef struct VNode  
{  
    vextype data;  
    int indegree;  
    arcnode * firstarc;  
}VNode, Adjlist[max];
typedef struct  
{  
    Adjlist vertices; //邻接表  
    int vernum, arcnum;//顶点数和弧数  
}ALGraph;  
int LocateVer(ALGraph G, char u)  
{  
    int i;  
    for(i = 0; i < G.vernum; i++)  
    {  
        if(u == G.vertices[i].data)  
            return i;  
    }
}  
void CreateALGraph(ALGraph &G)  
{  
    int i, j, k, w;  
    char v1, v2;  
    arcnode * p;  
    scanf("%d %d", &G.vernum, &G.arcnum);   
    for(i = 0; i < G.vernum; i++)  
    {  
        fflush(stdin);  
        scanf("%c", &G.vertices[i].data);  
        G.vertices[i].firstarc = NULL;  
        G.vertices[i].indegree = 0;  
    } 
    for(k = 0; k < G.arcnum; k++)  
    {  
        fflush(stdin);  
        scanf("%c %c %d", &v1, &v2, &w);  
        i = LocateVer(G, v1);  
        j = LocateVer(G, v2);  
        p = (arcnode *)malloc(sizeof(arcnode));  
        p->adjvex = j;  
        p->info = w;  
        p->nextarc = G.vertices[i].firstarc;  
        G.vertices[i].firstarc = p;  
        G.vertices[j].indegree++;    
	} 
}  //图的创建函数 
void CriticalPath(ALGraph G)  
{  
    int i, k, e, l;  
    int Ve[max],Vl[max];  
    arcnode *p;
    for(i = 0; i < G.vernum; i++)
        Ve[i] = 0;  //先初始化为零，再进行求解 
	for(i = 0; i < G.vernum; i++)  
    {  
        arcnode * p = G.vertices[i].firstarc;  
        while(p != NULL)  
        {  
            k = p->adjvex;  
            if(Ve[i] + p->info > Ve[k])  
                Ve[k] = Ve[i]+p->info;  //则我们称从v0到vi的最长路径的长度为vi的最早发生时间 
            p = p->nextarc;  
        }  
    }  //求解最早发生时间 
    for(i = 0; i < G.vernum; i++)  
    	Vl[i] = Ve[G.vernum-1];  //最晚发生时间 
    for(i = G.vernum-2; i >= 0; i--) 
    {  
        p = G.vertices[i].firstarc;  
        while(p != NULL)  
        {  
            k = p->adjvex;  
            if(Vl[k]-p->info<Vl[i])  
                Vl[i] = Vl[k] - p->info;  
            p = p->nextarc;  
        }  
    }  //拓扑逆序求解 
    for(i = 0; i < G.vernum; i++)  
    {  
    	p=G.vertices[i].firstarc;  
        while(p!= NULL)  
        {  
            k=p->adjvex;  
            e=Ve[i];
            l=Vl[k]-p->info;             //最迟开始时间
           	if(e==l)
            	printf("v%c->v%c,t=%d\n", G.vertices[i].data, G.vertices[k].data,l); //如果最早发生时间等于最晚时间，则为关键路径 
            p = p->nextarc;  
        }  
    } 
} 
int main()  
{  
    ALGraph G;  
	CreateALGraph(G);  
    CriticalPath(G);  
}