做加盟代理的网站,网站建设维护网页设计,网页功能设计,温州旅游 网站建设Content: 一、问题描述二、算法思想三、代码实现四、小结 一、问题描述 设计实现 AOE 网的关键活动与关键路径问题#xff1b;
二、算法思想
获取拓扑序列#xff1b;计算节点的最早开始时间 v e [ i ] ve[i] ve[i]#xff1b;计算节点的最晚开始时间 v l [ j ] vl[j] v… Content: 一、问题描述二、算法思想三、代码实现四、小结 一、问题描述 设计实现 AOE 网的关键活动与关键路径问题
二、算法思想
获取拓扑序列计算节点的最早开始时间 v e [ i ] ve[i] ve[i]计算节点的最晚开始时间 v l [ j ] vl[j] vl[j]查找关键路径
三、代码实现
#includestdio.h
#includestdlib.h
#includestring.h
#define maxx 999999
#pragma warning(disable:4996)typedef struct arc//弧
{ int index;//指向节点编号int weight;//边的权值struct arc *next;
}AR;typedef struct MyGraph
{int type;//0表示无向图1表示有向图int arcnum,vexnum;//边的个数、顶点个数char **vexname;//存放顶点名称的二维数组 AR *N;//表头数组int **A;//邻接矩阵
}GH;int findvex(char *s,GH *G);//找到图G中名称为s的节点编号并将其返回
void createGraph(GH *G);//创建图G
void showGraph(GH *G);//以邻接表的形式显示图Gint Topological_sort(GH *G,int *q);//对G进行拓扑排序q用于存放拓扑序列如果G中有回路返回1否则返回0
void CriticalPath(GH *G);//寻找G中的关键路径
void findCP(int *t,int top,int end,int *visit,GH *G,int *ve,int *vl,int *count);//递归函数用于在图G中寻找关键路径
//t为栈存储关键路径上节点编号end表示汇点编号visit表示访问标记数组ve,vl表示节点的最早开始时间和最晚开始时间count表示关键路径条数int main(void)
{GH *G;G(GH *)malloc(sizeof(GH));createGraph(G);printf(图的邻接表形式:\n);showGraph(G);CriticalPath(G);free(G);return 0;
}int findvex(char *s,GH *G)//找到图G中名称为s的节点编号并将其返回
{int i;for(i0;iG-vexnum;i){if(strcmp(s,G-vexname[i])0)return i;}printf(读取文件错误.\n);exit(-1);
}void createGraph(GH *G)//创建图G
{int i,j,n,edge;char filename[]graph.txt;//存放图的数据文件char str[10],str1[10];FILE *fp;AR *p;fpfopen(filename,r);if(!fp){printf(打开文件失败!\n);exit(-1);}fscanf(fp,%d,G-type);//读取图的类型G-arcnum0;fscanf(fp,%d,n);//读取结点数量G-vexnumn;//为动态数组分配空间G-vexname(char **)malloc(n*sizeof(char *));G-N(AR *)malloc(n*sizeof(AR));G-A(int **)malloc(n*sizeof(int *));//对头结点数组和邻接矩阵初始化for (i 0; i n; i){G-N[i].next NULL;G-A[i] (int *)malloc(n*sizeof(int));for (j 0; j n; j)G-A[i][j]maxx;}//读取顶点名称for(i0;in;i){fscanf(fp,%s,str);G-vexname[i](char *)malloc(strlen(str)*sizeof(char));strcpy(G-vexname[i],str);}//读取边while(!feof(fp)){fscanf(fp,%s,str);fscanf(fp,%s,str1);fscanf(fp,%d,edge);ifindvex(str,G);jfindvex(str1,G);//邻接表p(AR *)malloc(sizeof(AR));p-indexj;p-weightedge;p-nextG-N[i].next;G-N[i].nextp;//邻接矩阵G-A[i][j]edge;G-arcnum;//边的个数增加if(G-type0)//如果是无向图{//邻接表p(AR *)malloc(sizeof(AR));p-indexi;p-weightedge;p-nextG-N[j].next;G-N[j].nextp;//邻接矩阵G-A[j][i]edge;}}fclose(fp);
}void showGraph(GH *G)//以邻接表的形式显示图G
{int i;AR *p;//用于遍历for (i 0; i G-vexnum; i){printf(%s,G-vexname[i]);pG-N[i].next;while (p){if (G-type 1)printf(--);else//无向图没有箭头printf(--);printf(%s(%d),G-vexname[p-index],p-weight);pp-next;}printf(\n);}printf(\n);
}int Topological_sort(GH *G,int *q)//对G进行拓扑排序q用于存放拓扑序列如果G中有回路返回1否则返回0
{int i,n;int *d;int *t,top;int index,count;AR *p;nG-vexnum;d(int *)malloc(n*sizeof(int));//统计各个节点的入度t(int *)malloc(n*sizeof(int));//建立栈用于存储节点编号top-1;//初始化将各个节点的入度设为0for (i 0; i n; i)d[i] 0;//遍历表头数组统计各个节点的入度for (i 0; i n; i){pG-N[i].next;while (p){d[p-index];pp-next;}}//挑选入度为0的点进栈for (i 0; i n; i){if (d[i] 0){top;t[top]i;}}count0;//统计弹出的节点个数while (top 0)//若栈非空弹栈{indext[top];//栈顶元素编号//栈顶元素不输出//printf(%s ,G-vexname[index]);top--;//记录弹出序列即拓扑序列q[count]index;count;//遍历弹出节点的邻接表其相邻点的入度减一pG-N[index].next;while (p){d[p-index]--;if (d[p-index] 0)//若入度变为0进栈{top;t[top]p-index;}pp-next;}}//printf(\n);//输出free(t);free(d);if (count n)//拓扑序列中含有G中全部点表示没有回路return 0;elsereturn 1;
}void CriticalPath(GH *G)//寻找G中的关键路径
{int i,n;int x,y;//计数器int length;//关键路径长度int num,count;//关键节点个数和关键路径条数AR *p;int *q,*ve,*vl;int *t;//用于在递归寻找关键路径时存储路径int *visit;//访问标记数组nG-vexnum;q(int *)malloc(n*sizeof(int));//拓扑序列存储节点编号ve(int *)malloc(n*sizeof(int));//最早开始时间vl(int *)malloc(n*sizeof(int));//最晚开始时间if (Topological_sort(G,q))//获取拓扑序列{printf(该有向图中存在回路故不存在关键路径.\n);return;}//1.计算最早开始时间//初始化全设为0for (i 0; i n; i)ve[i] 0;for (i 0; i n; i)//利用正向拓扑序列计算最早开始时间{x q[i];p G-N[x].next;//利用邻接表寻找x的直接后继while (p)//更新x的直接后继的最早开始时间{if (ve[p-index] ve[x] (p-weight))ve[p-index] ve[x] (p-weight);p p-next;}}//2.计算最晚开始时间length ve[q[n - 1]];//关键路径长度//初始化for (i 0; i n; i)vl[i] length;for (i n - 1; i 0; i--)//利用逆向拓扑序列计算最晚开始时间{y q[i];//利用邻接矩阵寻找y的直接前驱for (x 0; x n; x)//更新y的直接前驱的最晚开始时间{if (G-A[x][y] maxx)//找到之后{if (vl[x] vl[y] - G-A[x][y])vl[x] vl[y] - G-A[x][y];}}}//3.输出最早开始时间和最晚开始时间num0;visit(int *)malloc(n*sizeof(int));printf(节点名称 最早开始时间 最晚开始时间\n);for (i 0; i n; i){x q[i];//节点编号printf(%4s %10d %12d\n,G-vexname[x],ve[x],vl[x]);if (ve[x] vl[x]){visit[x] 0;//关键节点设置为未访问num;}elsevisit[x]1;//事先标记非关键节点避免后续访问}//4.利用递归在关键节点中探寻关键路径//初始化t (int *)malloc(num*sizeof(int));//存储关键路径中节点编号visit[q[0]]1;t[0] q[0];count 0;//关键路径条数//调用递归函数findCP(t,0,q[n-1],visit,G,ve,vl,count);printf(\n);free(ve);free(vl);free(q); free(t);free(visit);
}//t为栈存储关键路径上节点编号end表示汇点编号visit表示访问标记数组ve,vl表示节点的最早开始时间和最晚开始时间count表示关键路径条数
void findCP(int *t,int top,int end,int *visit,GH *G,int *ve,int *vl,int *count)//递归函数用于在图G中寻找关键路径
{int i;int cur;AR *p;curt[top];if (cur end)//基准情况到达汇点输出路径{(*count); printf(\n第%d条关键路径:\n,(*count));for (i 0; i top; i)printf(%s--,G-vexname[t[i]]); printf(%s\n,G-vexname[cur]);}else//非基准情况{pG-N[cur].next;while (p)//遍历当前节点的直接后继{if (visit[p-index]0 ve[cur] (p-weight) vl[p-index])//关键工序(边)的判别条件非关键节点的visit[i]1{visit[p-index]1;t[top1]p-index;//入栈findCP(t,top1,end,visit,G,ve,vl,count);//调用递归函数visit[p-index]0;//撤销标记}pp-next;}}
}四、小结
1、 为了利用拓扑序列计算最早和最迟开始时间在进行拓扑排序时对排序序列进行记录 2、 对于关键路径不唯一的情况采用 DFS 寻找关键路径查找路径之前标记非关键节点避免后续访问从而简化了节点添入路径的条件提高算法的执行效率 3、 t 用于存储关键路径中的节点编号由于关键路径中的节点均是关键节点所以在给 t 分配空间时分配的空间单位数与关键节点个数相同即可 4、 在实际计算最早开始时间时做法并不与算法思想完全一致具体做法为先设初值 v e [ i ] ve[i] ve[i] 全部为0然后遍历正向拓扑序列 q q q对于编号为 q [ i ] q[i] q[i] 的节点更新其直接后继 y y y 号节点的最早开始时间即若 v e [ y ] v e [ q [ i ] ] A [ q [ i ] ] [ y ] ve[y]ve[q[i]]A[q[i]][y] ve[y]ve[q[i]]A[q[i]][y]则令 v e [ y ] v e [ q [ i ] ] A [ q [ i ] ] [ y ] ve[y] ve[q[i]] A[q[i]][y] ve[y]ve[q[i]]A[q[i]][y]对于最迟开始时间进行类似操作
