//图的关键路径
#include "stdafx.h"
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#define gr_lin 10
#define M 30
#define pInt int *
/*
求图的关键路径的步骤如下:
1> 从源点v1开始,计算各事件的最早发生时间.令ve[1]=0,按拓扑顺序求其余各项点
的最早发生时间ve[j](2<= j <=n).如果得到的拓扑有序序列中的顶点个数小于
网中的顶点个数n,则说明网中存在有向回路,不能求关键路径,算法终止,否则继续
执行以下步骤;
2> 从汇点vn出发,计算各事件的最迟发生时间.令vl[n]=ve[n],按拓扑逆序求其余各顶点
的最迟发生时间vl[j](n-1>=j>=1);
3> 根据各事件的ve值和vl值,求每个活动的最早开始时间ee和迟开始时间el,满足条件
ee=el的活动均为关键活动.
*/
typedef struct enode{int vertex,dur; struct enode *link;}*PENODE,ENODE;
typedef struct hnode{int data,count; PENODE first;}*PHNODE,HNODE;
void ShowData(int *e,int n=0)
{
for(int i=0;i<n;i++)
printf("%d \n",e[i]);
}
void DebugShowData(char *ms,int i)
{
printf("%s==%d ==\n",ms,i);
}
bool fucSetNode(PHNODE node,int count,int data,int first[])
{
PENODE phInsertNode;
node->count=count;node->data=data;
for(int i=0;i<gr_lin;i++)
{
if(first[i]>0)
{
phInsertNode=(PENODE)malloc(sizeof(ENODE));
phInsertNode->dur=first[i];
phInsertNode->vertex=i;
phInsertNode->link=node->first;
node->first=phInsertNode;
}
}
return true;
}
void fucCreateGraph(PHNODE graph)//建立树数据
{
int Node[][gr_lin]=
{
0,3,4,0,0,0,0,0,0,0, //0
0,0,0,5,6,0,0,0,0,0, //1
0,0,0,8,0,7,0,0,0,0, //2
0,0,0,0,3,0,0,0,0,0, //3
0,0,0,0,0,0,9,4,0,0, //4
0,0,0,0,0,0,0,6,0,0, //5
0,0,0,0,0,0,0,0,0,2, //6
0,0,0,0,0,0,0,0,5,0, //7
0,0,0,0,0,0,0,0,0,3, //8
0,0,0,0,0,0,0,0,0,0 //9
};
int TempCount[gr_lin]={0,1,1,2,2,1,1,2,3,2};
for(int i=0;i<gr_lin;i++)
{
graph[i].first=NULL;
fucSetNode(&graph[i],TempCount[i],i,Node[i]);
}
}
void fucShowData(HNODE pn[])
{
int i=0;
PENODE pen;
for(i=0;i<gr_lin;i++)
{
printf("结点=%d,入度=%d ",pn[i].data,pn[i].count);
for(pen=pn[i].first;pen/* !=NULL */;pen=pen->link)
printf("活动为(%d,%d) 的权值是 %d ",i,pen->vertex,pen->dur);
printf("\n");
}
}
int fucSetStack(PHNODE adjlist,int n=gr_lin)
{
int i=0,iTop=0;
for(i=0;i<n;i++)
{
if(adjlist[i].count==0)
{
adjlist[i].count=iTop;
iTop=i;
}
}
return iTop;
}
bool fucGraphShort(HNODE adjlist[],pInt ve,pInt iStack,pInt iTopStack=0)
//对图进行排序返回排序结点Stack数组，
//和事件的最早发生时间ve[图的结点数],如果返回false 表示图有回路
{
int iTemp=0,iPoint=0,iPointCount=0,iTopGraph=0;
PENODE pen;
iTopGraph=fucSetStack(adjlist,gr_lin);
do
{
iPointCount++;
iTemp=iTopGraph;
iTopGraph=adjlist[iTemp].count;
iStack[(*iTopStack)++]=iTemp;//先加加和后加加是有区别的
for(pen=adjlist[iTemp].first;pen;pen=pen->link)
{
iPoint=pen->vertex;
adjlist[iPoint].count--;
if(adjlist[iPoint].count==0)
{adjlist[iPoint].count=iTopGraph; iTopGraph=iPoint;}
if(ve[iTemp]+pen->dur>ve[iPoint])
{
ve[iPoint]=ve[iTemp]+pen->dur ;
//printf("调试VE=%d\n",ve[iPoint]);
}
}
} while(iTopGraph>0);
if(iPointCount<gr_lin)
{
//printf("iPointCount=%d\n",iPointCount);
return false;
}
else
return true;
}
bool fucKeyPath(HNODE adjlist[],int n=gr_lin)
{
int iPoint=0,iGraphTop=0,iStackTop=0,iTemp=0,ee=0,el=0;
int iStack[M]={0},ve[gr_lin]={0},vl[gr_lin]={0};
PENODE p;
iGraphTop=fucSetStack(adjlist,n);
if(!fucGraphShort(adjlist,ve,iStack,&iStackTop))
{
memcpy(vl,ve,sizeof(ve));
while(iStackTop>0)
{
iPoint=iStack[iStackTop--];
for(p=adjlist[iPoint].first;p;p=p->link)
{
iTemp=p->vertex;
if(vl[iTemp]-p->dur<vl[iPoint])
vl[iPoint]=vl[iTemp]-p->dur;
}
}
for(iTemp=0;iTemp<gr_lin;iTemp++)
{
for(p=adjlist[iTemp].first;p;p=p->link)
{
iPoint=p->vertex;
ee=ve[iTemp];el=vl[iPoint]-p->dur;
if(el==ee)
printf("<%d,%d>,ee=%d ,el=%d \n",iTemp,iPoint,ee,el);
}
}
}
else
{
printf("图有回路不能找到关键路径\n");
return false;
}
return true;
}
int main(int argc, char* argv[])
{
int ve[gr_lin]={0},iStack[M]={0};
PHNODE graph=(PHNODE)malloc(sizeof(HNODE)*gr_lin);
printf("图的关键路径\n");
fucCreateGraph(graph);
fucShowData(graph);
/*
if(!fucGraphShort(graph,ve,iStack))
{
printf("顺序显示ve 的内容\n");
ShowData(ve);
printf("顺序显示栈内的内容\n");
ShowData(iStack);
}else
{
printf("图的排序执行失败请检查\n");
}
*/
fucKeyPath(graph);
return 0;
}
C++技术网会员解答：
这个问题，我不能帮你解决哦。而且这种问题很深入算法，我不能提供算法本身的解答。如果编程方面有问题，可以问。算法写错了，写不出效果，你要一步步确认算法的思路，要让每一步达到算法的要求。
然后分析结果，看看与预期结果有什么不一样，分析关系。你要对算法熟悉，要达到的效果就是，其中一步如果有偏差，会导致什么效果。而不只是一步到位。所以，现在出的问题，刚好就是让你熟悉出错后形成的各种问题。
希望提供一个解决问题的思路，可以帮助你解决问题。
