引入
事件是点,活动是边.
1.事件V1的最早发生时间ve[i]
2.事件的最迟发生时间vl[i]
第一句话是说,最迟事件执行完后,后继的事件要么直接开始,要么可以等会开始,但不能最迟事件正在执行着,后继时间就得开始了,这样是不行的.
所以我们可以从已知的汇点从后往前递推,每一次求解弧头的最小值(因为值越小,说明你可以执行时间的时间越长).
举例:
3.活动ai = <Vj,Vk >的最早发生时间e[i]
活动的最早发生时间,只要这个事件可以开始做的时间已到,我们就开始做了,就像平常老师已布置作业你就可以写了.
活动的最晚发生时间,就是你得在下一个事件开始之前必须完成这个活动,也就是在老师截止之前你得完成作业.直接用截止时间-你写作业花费的时间便是你最晚写作业的时间.
为啥求活动最早发生是用事件的最早－的呢?
因为事件是从最早发生时间之后,你就可以搞活动了,在事件最晚发生之前开始都行,所以我最早开始做就是当事件可以开始搞的时候开始做就行了.
4.活动ai = <Vj,Vk >的最迟发生时间l[i]
当活动最早开始时间和最晚开始时间一样,那么这个路径就是关键路径.它表示在执行这些事件的时候,一刻都不能停.
总结:
算法设计:
算法时间复杂度分析:
参考代码:
#include <iostream> #include<cstring> #include<stack> using namespace std; const int MaxVnum=100;//顶点数最大值 int indegree[MaxVnum];//入度数组 int ve[MaxVnum]; //事件vi的最早发生时间 int vl[MaxVnum]; //事件vi的最迟发生时间 e和l数组不需要创建,因为我们在判断时如果满足就直接输出了,没必要再存着. typedef string VexType;//顶点的数据类型为字符型 typedef struct AdjNode{ //定义邻接点类型 int v; //邻接点下标 int weight; //权值 struct AdjNode *next; //指向下一个邻接点指针 }AdjNode; typedef struct VexNode{ //定义顶点类型 VexType data; //VexType为顶点的数据类型，根据需要定义 AdjNode *first; //指向第一个邻接点指针 }VexNode; typedef struct{ //包含邻接表和逆邻接表 VexNode Vex[MaxVnum]; //定义邻接表 VexNode converse_Vex[MaxVnum]; //定义逆邻接表 int vexnum,edgenum; //顶点数，边数 }ALGragh; int locatevex(ALGragh G,VexType x) { for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标 if(x==G.Vex[i].data) return i; return -1;//没找到 } void insertedge(ALGragh &G,int i,int j,int w)//插入一条边 { AdjNode *s1,*s2; //创建邻接表结点 s1=new AdjNode; s1->v=j; s1->weight=w; s1->next=G.Vex[i].first; G.Vex[i].first=s1; //创建逆邻接表结点 s2=new AdjNode; s2->v=i; s2->weight=w; s2->next=G.converse_Vex[j].first; G.converse_Vex[j].first=s2; } void printg(ALGragh G)//输出邻接表 { cout<<"----------邻接表如下：----------"<<endl; for(int i=0;i<G.vexnum;i++) { AdjNode *t=G.Vex[i].first; cout<<G.Vex[i].data<<"： "; while(t!=NULL) { cout<<"["<<G.Vex[t->v].data<<" "<<t->weight<<"] "; t=t->next; } cout<<endl; } cout<<"----------逆邻接表如下：----------"<<endl; for(int i=0;i<G.vexnum;i++) { AdjNode *t=G.converse_Vex[i].first; cout<<G.converse_Vex[i].data<<"： "; while(t!=NULL) { cout<<"["<<G.Vex[t->v].data<<" "<<t->weight<<"] "; t=t->next; } cout<<endl; } } void CreateALGraph(ALGragh &G)//创建有向图的邻接表和逆邻接表 { int i,j,w; VexType u,v; cout<<"请输入顶点数和边数:"<<endl; cin>>G.vexnum>>G.edgenum; cout << "请输入顶点信息:"<<endl; for(i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组 { cin>>G.Vex[i].data; G.converse_Vex[i].data=G.Vex[i].data; G.Vex[i].first=NULL; G.converse_Vex[i].first=NULL; } cout<<"请依次输入每条边的两个顶点及权值u,v,w"<<endl; while(G.edgenum--) { cin>>u>>v>>w; i=locatevex(G,u);//查找顶点u的存储下标 j=locatevex(G,v);//查找顶点v的存储下标 if(i!=-1&&j!=-1) insertedge(G,i,j,w); else { cout << "输入顶点信息错！请重新输入！"<<endl; G.edgenum++;//本次输入不算 } } } void FindInDegree(ALGragh G)//求出各顶点的入度存入数组indegree中 { int i,count; for(i=0;i<G.vexnum; i++) { count=0; AdjNode *p=G.converse_Vex[i].first; if(p) { while(p) { p=p->next; count++; } } indegree[i]=count; } cout<<"入度数组为："<<endl; for(int i=0;i<G.vexnum;i++)//输出入度数组 cout<<indegree[i]<<"\t"; cout<<endl; } bool TopologicalSort(ALGragh G,int topo[]){ int index; stack<int> S; FindInDegree(G);//入度数组进行 初始化 for(int i = 0; i <G.vexnum; i++){ if(!indegree[i]){ S.push(i);//入度为0的入栈 } } index = 0; while(!S.empty()){ int x = S.top(); S.pop(); topo[index] = x; index++; AdjNode *p = G.Vex[x].first;//p指向i的第一个邻接点 while(p){//x的邻接点进行入度-1 int k = p->v; --indegree[k]; if(indegree[k]==0){ S.push(k); } p = p->next; } } if(index < G.vexnum){ return false; }else{ return true;//该有向图无回路. } } bool CriticalPath(ALGragh G,int topo[]){ int n,k; n = G.vexnum; if(TopologicalSort(G,topo)){ cout<<"拓扑序列为:"<<endl; for(int i = 0; i < G.vexnum;i++){ cout<<topo[i]<<"\t"; } cout<<endl; }else{ cout<<"该图有环,无拓扑序列!"<<endl; } for(int i = 0;i < n; i++){ ve[i] = 0;//进行初始化 } for(int i = 0; i < n; i++){//按照拓扑序列求ve数组 k = topo[i]; AdjNode *p = G.Vex[k].first; while(p!=NULL){ int j = p->v; if(ve[j] < ve[k]+p->weight){ ve[j] = ve[k]+p->weight; } p = p->next;//p后移 } } for(int i = 0;i<n; i++){ vl[i] = ve[n-1];//给每个事件的最迟发生时间置初值ve[n-1] 相当于给每个初始化为最大值. } for(int i = n-1; i>=0; i--){//按逆拓扑序求 每个事件的最迟发生时间 k = topo[i]; AdjNode *p = G.Vex[k].first; while(p!=NULL) { int j = p->v; if(vl[k] > vl[j]-p->weight){ vl[k] = vl[j]-p->weight; } p = p->next;//指针后移 } } cout<<"事件的最早发生时间和最迟发生时间:"<<endl; for(int i = 0;i < n; i++){ cout<<ve[i]<<"\t"<<vl[i]<<endl; } //判断每一活动是否为关键活动 cout<<endl; cout<<"关键活动路径为:"; for(int i = 0; i < n;i++){ AdjNode *p = G.Vex[i].first; while(p!=NULL){ int j = p->v; int e = ve[i]; int l = vl[j] - p->weight; if(e==l){ cout<<"<"<<G.Vex[i].data<<","<<G.Vex[j].data<<"> "; } p = p->next; } } return true; } int main() { ALGragh G; int *topo=new int[G.vexnum]; CreateALGraph(G);//创建有向图的邻接表和逆邻接表 printg(G);//输出邻接表和逆邻接表 CriticalPath(G,topo); return 0; } //请输入顶点数和边数: //9 11 //请输入顶点信息: //V1 V2 V3 V4 V5 V6 V7 V8 V9 //请依次输入每条边的两个顶点及权值u,v,w //V1 V2 6 //V1 V3 4 //V1 V4 5 //V2 V5 1 //V3 V5 1 //V4 V6 2 //V5 V7 9 //V5 V8 7 //V6 V8 4 //V7 V9 2 //V8 V9 4
运行结果:
注:
算法在执行求v数组时:假如图中A->B,D->B,C->B,那么我们采用按照拓扑序的顺序对每个点的临界点的V进行初始化,如果该临界点的V小于新的V则用大的那个进行覆盖.
由于A,D,C都是在B之前的,所以当执行到B时,其V已经达到最大值了.这样的好处是遍历一遍邻接表V已经找到了.
如果采用按照拓扑序,来直接求解当前的V,那么需要找到该点入度的所有点.即需要建立逆邻接表.然后每次进行查找然后更新,较为麻烦.
