数据结构AOE关键路径，关于这个有些知识点需要涉及，一个是关于拓扑排序，一个是寻找关键路径。下面给出图例。
此次代码每一步相应给出了解释，因为部分算法书上是错误的。
关于拓扑排序就不用多说了，比较简单，下面给出一个AOE的关键路径求法。
当然答主关于图的很多算法有很多，这里就不再一一列出，但注意的是，可以点击此处查看最小生成树的求法与代码。
下面开始我们的数据结构题目
题目描述：按照图的“邻接表”存储结构表示AOE网，实现求其关键路径的算法，并验证如下图1所示AOE网的关键路径。
不过想说句题外话，西安电子科技大学出版的《数据结构》关于此处的算法有错误（要源于课本也要高于课本），我花了一些时间才看出猫腻来，我下面给出了完整的程序并且无错误。
操作提示：一个完整的系统应具有以下功能：
1）输入图的顶点数目.
2）按偏序顺序输入各边顶点及权值.
3）输入(0,0)结束（我这里采取了（0,0,0）的输入）
4）程序会自动计算出关键路径
下面附完整程序
/*
Jack Leo
All rights reversed
*/
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;
/*创建图的邻接表*/
typedef struct ArcNode{
int adv;//指向顶点的位置
struct ArcNode *nextArc;//指向下一条边
int w;//表示权值
}ArcNode;
typedef struct VNode{
ArcNode *first;//指向该顶点第一条弧的指针
string datam; //顶点数据，例如名字
}AdVlist;
typedef struct ALGraph{
AdVlist vts[500];//顶点向量
int v,e;
}ALGraph;
/*查找输入的x顶点位置*/
int Find(ALGraph &g,string x){
for(int i=0;i<g.v;i++){
if(x==g.vts[i].datam) return i;
}
return -1;
}
int ve[500];//全局变量，表示事件最早发生的时间
stack<int> t;//t为返回拓扑序列的栈
/*创建图*/
void Creat(ALGraph &g){
int mw,edge=0;
string v1,v2;
cout<<"输入图的顶点数"<<endl;
cin>>g.v;
cout<<"输入图中结点信息"<<endl;
//输入顶点的信息，并且使指边指向NULL
for(int i=0;i<g.v;i++){
cin>>g.vts[i].datam;
g.vts[i].first=NULL;
}
cout<<"输入图中两个顶点（起点和终点）与相应的权值，其中(0,0,0)结束"<<endl;
while(1){
cin>>v1>>v2>>mw;
if(v1=="0"&&v2=="0"&&mw==0) break;
edge++;
int j,k;
j=Find(g,v1);
k=Find(g,v2);
ArcNode *p1=new ArcNode;
//使边p的顶点指向第k个顶点，意思就是第k个顶点为指向量，例如边<i,j>，则j就是这里的k
p1->adv=k;
//使边p的权值赋值
p1->w=mw;
p1->nextArc=NULL;
p1->nextArc=g.vts[j].first;
g.vts[j].first=p1;
}
g.e=edge;
}
/*三金编写，版权所有，转载注明*/
/*求各顶点的入度，保存在indegree数组中*/
void FindID(ALGraph g,int indegree[500]){
int i;
ArcNode *p;
for(i=0;i<g.v;i++) indegree[i]=0;//初始化
for(i=0;i<g.v;i++){
p=g.vts[i].first;//p是第i个顶点指向的第一条边的指针
//遍历第i个顶点所有的边，直到指向NULL
while(p!=NULL){
indegree[p->adv]++;//边的顶点，就是此时的顶点入度+1
p=p->nextArc;//遍历
}
}
}
/*拓扑排序*/
bool TopOrder(ALGraph g){
stack<int> s;//s为存放入度为0的顶点的栈
int count,i,j,k;//count做检验工作，因为入度为0的时候可能会有顶点没有进入，这样做更加保险
ArcNode *p;
int indegree[500];//各顶点的入度
FindID(g,indegree);
for(i=0;i<g.v;i++){
if(indegree[i]==0) s.push(i);//使没有入度的点入栈，就是说在拓扑排序中，先寻找入度为0的顶点
}
count=0;
for(i=0;i<g.v;i++){
ve[i]=0;//初始化最早发生的时间
}
while(!s.empty()){
/*如果栈s非空，那么先出栈并赋值给j，然后使j进入栈t,这样栈t就是拓扑序列，因为s里面的肯定是入度为0的了*/
j=s.top();
s.pop();
t.push(j);
count++;
//边p指向顶点j的第一条边
p=g.vts[j].first;
while(p!=NULL){
k=p->adv;
/*顶点k(就是这条边的指向顶点)度数是否为0，如果不是那么减为0，然后使其入栈*/
if(!(--indegree[k])) s.push(k);
//j的最早发生事件+权值是否大于这个顶点的ve，注意一开始ve(0)=0
if(ve[j]+p->w>ve[k]) ve[k]=ve[j]+p->w;
p=p->nextArc;
}
}
if(count<g.v) return false;//有回路
else return true;
}
/*三金编写，版权所有，转载注明*/
/*关键路径算法
有了最早发生事件了，就是全局变量ve,然后现在要求最晚发生时间了，最后可求出活动的时间
关键路径就是活动，注意是活动（也就是边）最早和最晚时间发生的活动
*/
bool CriticalPath(ALGraph g){
ArcNode *p;
int i,j,k,dut,ei,li;
int vl[500];//vl为事件，注意不是活动，发生的最晚时间
//TopOrder(g);
if(!TopOrder(g)) return false;
for(i=0;i<g.v;i++) vl[i]=ve[g.v-1];//初始化
/*按逆拓扑顺序求各顶点的vl*/
while(!t.empty()){
j=t.top();
t.pop();
p=g.vts[j].first;
while(p!=NULL){
k=p->adv;
dut=p->w;
if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut;
p=p->nextArc;
}
}
cout<<"关键路径"<<endl;
cout<<"Initial "<<"End "<<"Weight "<<" el"<<" vl"<<endl;
for(j=0;j<g.v;j++){
p=g.vts[j].first;
while(p!=NULL){
k=p->adv;
dut=p->w;
ei=ve[j];
li=vl[k]-dut;
if(ei==li)
cout<<g.vts[j].datam<<" "<<g.vts[k].datam<<" "<<dut<<endl;
p=p->nextArc;
}
}
return true;
}
/*三金编写，版权所有，转载注明*/
int main(){
ALGraph g;
Creat(g);
CriticalPath(g);
return 0;
}
下面给出此次程序的运行结果，图例按照上述题目要求的。
