当前位置： 首页 > article >正文

数据结构应用实例(五)——关键路径

article 2024/9/20 23:39:12

Content:

      • 一、问题描述
      • 二、算法思想
      • 三、代码实现
      • 四、小结

一、问题描述

  设计实现 AOE 网的关键活动与关键路径问题；

二、算法思想

  1. 获取拓扑序列；
  2. 计算节点的最早开始时间 v e [ i ] ve[i] ve[i]；
  3. 计算节点的最晚开始时间 v l [ j ] vl[j] vl[j]；
  4. 查找关键路径

三、代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.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);//以邻接表的形式显示图G

int 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(i=0;i<G->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;

	fp=fopen(filename,"r");
	if(!fp)
	{
		printf("打开文件失败!\n");
		exit(-1);
	}

	fscanf(fp,"%d",&G->type);//读取图的类型
	G->arcnum=0;
	fscanf(fp,"%d",&n);//读取结点数量
	G->vexnum=n;

	//为动态数组分配空间
	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(i=0;i<n;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);

		i=findvex(str,G);
		j=findvex(str1,G);
		//邻接表
		p=(AR *)malloc(sizeof(AR));
		p->index=j;
		p->weight=edge;
		p->next=G->N[i].next;
		G->N[i].next=p;
		//邻接矩阵
		G->A[i][j]=edge;
		G->arcnum++;//边的个数增加
		if(G->type==0)//如果是无向图
		{
			//邻接表
			p=(AR *)malloc(sizeof(AR));
			p->index=i;
			p->weight=edge;
			p->next=G->N[j].next;
			G->N[j].next=p;
			//邻接矩阵
			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]);
		p=G->N[i].next;
		while (p)
		{
			if (G->type == 1)
				printf("-->");
			else//无向图没有箭头
				printf("--");
			printf("%s(%d)",G->vexname[p->index],p->weight);
			p=p->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;

	n=G->vexnum;
	d=(int *)malloc(n*sizeof(int));//统计各个节点的入度
	t=(int *)malloc(n*sizeof(int));//建立栈，用于存储节点编号
	top=-1;
	
	//初始化，将各个节点的入度设为0
	for (i = 0; i < n; i++)
		d[i] = 0;

	//遍历表头数组，统计各个节点的入度
	for (i = 0; i < n; i++)
	{
		p=G->N[i].next;
		while (p)
		{
			d[p->index]++;
			p=p->next;
		}
	}

	//挑选入度为0的点进栈
	for (i = 0; i < n; i++)
	{
		if (d[i] == 0)
		{
			top++;
			t[top]=i;
		}
	}

	count=0;//统计弹出的节点个数
	while (top >= 0)//若栈非空，弹栈
	{
		index=t[top];//栈顶元素编号
		//栈顶元素不输出
		//printf("%s ",G->vexname[index]);
		top--;
		//记录弹出序列，即拓扑序列
		q[count]=index;
		count++;
		//遍历弹出节点的邻接表，其相邻点的入度减一
		p=G->N[index].next;
		while (p)
		{
			d[p->index]--;
			if (d[p->index] == 0)//若入度变为0，进栈
			{
				top++;
				t[top]=p->index;
			}
			p=p->next;
		}
	}
	//printf("\n");//输出

	free(t);
	free(d);
	if (count == n)//拓扑序列中含有G中全部点，表示没有回路
		return 0;
	else
		return 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;//访问标记数组

	n=G->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.计算最早开始时间
	//初始化，全设为0
	for (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.输出最早开始时间和最晚开始时间
	num=0;
	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++;
		}
		else
			visit[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;

	cur=t[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//非基准情况
	{
		p=G->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[top+1]=p->index;//入栈
				findCP(t,top+1,end,visit,G,ve,vl,count);//调用递归函数
				visit[p->index]=0;//撤销标记
			}
			p=p->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]；对于最迟开始时间，进行类似操作；


http://www.kler.cn/news/304242.html

相关文章：

  • 学python要下什么包吗，有推荐的教程或者视频吗?
  • SprinBoot+Vue山西文旅网的设计与实现
  • 软件测试学习笔记丨Postman实战练习
  • 黑链、黑帽、明链分别是什么意思
  • JavaScript --函数作用域变量的使用规则（局部和访问）
  • 研究生深度学习入门的十天学习计划------第十天
  • LLM 工程师入门：生成式AI的简易指南
  • 【Vue】移动端访问Vue项目页面无数据，但是PC访问有数据
  • Linux定时启动jar应用shell脚本分享
  • 基于springboot的二手物品管理系统的设计与实现 （含源码+sql+视频导入教程）
  • C语言实现一个简单的点歌系统
  • XSS和sql注入部分场景测试用例样例
  • 将复杂类型列展开成多行，附带json解析
  • pandas 将多条记录整合成一条记录，每条记录的year和month字段组成新的字段名
  • MySQL从C盘迁移到D盘
  • Git的学习笔记
  • 服务器与个人计算机之间的区别
  • Java项目: 基于SpringBoot+mybatis+maven课程答疑系统(含源码+数据库+毕业论文)
  • 【Ubuntu】Ubuntu双网卡配置 实现内外网互不影响同时可用
  • KubeCon China 回顾｜快手的 100% 资源利用率提升：从裸机迁移大规模 Redis 到 Kubernetes
  • 深度学习--对抗生成网络（GAN, Generative Adversarial Network）
  • Pr 入门系列之三：挑选与添加媒体到序列（上）
  • UQpy | 不确定性量化Python工具箱推荐
  • Spring和MyBatis常见面试题总结
  • 房屋租赁|基于springboot的房屋租赁管理系统设计与实现(附项目源码+论文+数据库）
  • python-游戏自动化（一）（实战-自动刷视频点赞）
  • activiti第五步流程图定义会审并设置串行用户任务
  • 在RabbitMQ中四种常见的消息路由模式
  • 电能质量监测装置和防孤岛装置在特斯拉工厂分布式光伏项目的应用
  • Node.js Express 框架