图的关键路径

求关键路径的算法：

1）输入e条弧<i,j>，建立AOE网的存储结构。

2）从源点v0出发，令ve[0]＝0按拓扑有序求其余各顶点的最早发生时ve[i]（1≤i≤ n-1）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）。

3）从汇点vn出发，令vl[n-1]= ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i] (n-2 ≥i≥ 0)；

4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。

                   

#include<iostream>
using namespace std;
#define MAX_VEXTEX_NUM 20
#define M 20
#define MaxLen 1000    //最大长度
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int SElemType;
typedef int VertexType;
typedef int VRType;
typedef int InfoType;
typedef struct ArcNode
{
int adjvex; // 该弧所指向的顶点的位置
    struct ArcNode *nextarc;// 指向下一条弧的指针
InfoType   info;   // 该弧相关信息的指针
}ArcNode;
typedef struct VNode
{
VertexType data;// 顶点信息
    ArcNode *firstarc;// 指向第一条依附该顶点的弧
}VNode,AdjList[MAX_VEXTEX_NUM];
typedef struct
{
AdjList vertices;
    int vexnum, arcnum;
}ALGraph;
typedef struct SqStack
{
SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

 

void InitStack(SqStack &S)//初始化栈
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
   exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
int Pop(SqStack &S,SElemType &e)//出栈操作
{
if(S.top==S.base)return ERROR;
e=*--S.top;
return OK;
}
int Push(SqStack &S,SElemType e)//人栈操作
{
if(S.top-S.base>=S.stacksize)
{
   S.base = (SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
   if(!S.base)
    exit(OVERFLOW);
   S.top = S.base+S.stacksize;
   S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
int StackEmpty(SqStack S)//判栈是否为空
{
if(S.top==S.base)
   return OK;
else
   return ERROR;
}
int CreatALGraph(ALGraph &G)//构建图
{
ArcNode *p;
int i, j, k,info1;
cout<<"请输入有向图的顶点数和弧数:"<<endl;
cout<<"vexnum:";
cin>>G.vexnum;
cout<<endl<<"arcnum:";
cin>>G.arcnum;
for (i=1;i<=G.vexnum;i++)
{
   G.vertices[i].data=i;
   G.vertices[i].firstarc=NULL;
}
for(k=1;k<=G.arcnum;k++)       //输入存在边的点集合
{
   cout<<"建立弧，请输入第"<<k<<"条弧对应的顶点序号及权值:";
   cin>>i>>j>>info1;
        if(i==j||i<0||j<0)
   {
    cout<<"i,j,不合法输入"<<endl;
    cout<<"请重新输入"<<k<<"条弧对应的顶点:";
    cin>>i>>j;
   }
   if(i>G.vexnum||j>G.vexnum)
   {
    cout<<"图中没有这样的点，重新输入:"<<endl;
    cout<<"请重新输入"<<k+1<<"条弧对应的顶点:";
    cin>>i>>j;
   }
   p=(ArcNode*)malloc(sizeof(ArcNode));
   p->adjvex=j;
   p->info=info1;
   p->nextarc=G.vertices[i].firstarc;
   G.vertices[i].firstarc=p;
}
return OK;
}
void FindInDegree(ALGraph G,int indegree[])//求入度操作
{
int i;
for(i=1;i<=G.vexnum;i++)
{
   indegree[i]=0;
}
for(i=1;i<=G.vexnum;i++)
{
   while(G.vertices[i].firstarc)
   {
    indegree[G.vertices[i].firstarc->adjvex]++;
    G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;
   }
}
}
int ve[100];
int TopologicalSort(ALGraph G,SqStack &T)       //进行拓扑排序
{
int indegree[M];
FindInDegree(G, indegree);//求各顶点的入度
    SqStack S;
int i,x,k;

InitStack(S);
ArcNode *p;
InitStack(S);
for (i=1;i<=G.vexnum;i++)
{
   if (!indegree[i])Push(S,i);//入度为0者入栈
}
InitStack(T);
int count=0;
for(x=1;x<=G.vexnum;x++)// ve[0..G.vexnum-1]=0;
{
   ve[x]=0;  
}
while(!StackEmpty(S))
{
   Pop(S,i);
   Push(T,i);
   ++count;//输出i号顶点并计数
   for (p=G.vertices[i].firstarc;p;p=p->nextarc)
   {
    k=p->adjvex;
    if (--indegree[k]==0)//若入度减为0，则入栈
    {
     Push(S,k);
    }
    if((ve[i]+p->info)>ve[k])
    {
     ve[k]= ve[i]+p->info;
    }

   }

}
cout<<endl;
if (count<G.vexnum)//该图有回路
{
   cout<<"出现错误"<<endl;
}
else
{
   cout<<"排序成功"<<endl;
}
return OK;
}
int CriticalPath(ALGraph G)//输出G的关键活动
{
int dut;
int j=G.vexnum;
int i,k;
int ee,el;
char tag;
int vl[100];
ArcNode *p;
SqStack T;
if(!TopologicalSort(G,T))
{
   printf("该图存在环，无法找到关键路径！");
   return ERROR;
}
for(i=1;i<=G.vexnum;i++)// vl[0.. G.vexnum-1] =ve[0..G.vexnum-1];//用ve初始化vl
{
   vl[i]=ve[G.vexnum];
}
printf("带*的为关键活动！\n");
printf("起点\t终点\tdut\tee\tel\ttag\n");
    while(!StackEmpty(T))  
   for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc)
   {
    k=p->adjvex;
    dut=p->info;
    if((vl[k]-dut)<vl[j])
    {
     vl[j]=vl[k]-dut;
    }
   }//end of for
   for(i=1;i<=G.vexnum;++i)
    for (p=G.vertices[i].firstarc;p;p=p->nextarc){
     k=p->adjvex;
     dut=p->info;
     ee=ve[i];
     el=vl[k]-dut;
     tag=(ee==el)?'*':' ';
     printf("%d\t%d\t%d\t%d\t%d\t%c\n",i,k,dut,ee,el,tag);
    }//end of for(p)
    return 1;
}//end of CriticalPath
int main()
{
ALGraph G;
CreatALGraph(G);
CriticalPath(G);
    return 0;
}