图的关键路径C/C++代码实现

青旅半醒 2023-02-20 02:34 102阅读 0赞

## AOE-网： ##

AOE-网 (Activity On Edge) , 即以边表示活动的网。 AOE-网是一个带权的有向无环图， 其中顶点表示事件， 弧表示活动， 权表示活动持续的时间。

## 关键路径： ##

要估算整项工程完成的最短时间， 就是要找一条从源点到 汇点的带权路径长度最长的路径， 称为关键路径 (Critical Path)。关键路径上的 活动叫做关键活动，这些活动是影响工程进度的关键， 它们的提前或拖延将使整个工程提前或拖延。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
其关键路径为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]  
关键路径有两条： (v0, v1,v4,v6, v8)或(v0, v1,v4,v7,v8), 长度均为18。关键活动为(a1, a4, a7, a10)或(a1, a4, a8, a11)。

## 4个描述量： ##

1，事件v的最早发生时间ve(i)：ve(i) = Max\{ve(k) + W(i,k)\}  
2，事件v的最迟发生时间vl(i)：vl(i) = Min\{vl(k) - W(k,i)\}  
根据前两个可求得后两个：  
3，活动a的最早开始时间e(i)：e(i) = ve(j)  
4，活动a的最晚开始时间l(i) ：l(i) = vl(k) - (ai的持续时间)

**找出 e(i)=i(i)的活动a, 即为关键活动。由关键活动形成的由源点到汇点的每一条路径 就是关键路径，关键路径有可能不止一条。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]

以上图为例：

## 代码如下： ##

#include<stdio.h>
    
    #define MVNum 100
    typedef char OtherInfo;
    typedef char VerTexType;
    
    //图的邻接表存储结构
    typedef struct ArcNode			//边结点
    {
        
    	int adjvex;//邻接点域 
    	struct ArcNode *nextarc;//链域
    	OtherInfo info;//数据域
    	int weight;	//权值
    }ArcNode;
    typedef struct VNode			//顶点信息
    {
        
    	VerTexType data;//数据域
    	ArcNode *firstarc;//链域
    }VNode, AdjList[MVNum];
    typedef struct                  //邻接表
    {
        
    	AdjList vertices;
    	int vexnum, arcnum;
    }ALGraph;
    
    //函数声明
    int LocateVex(ALGraph G, char v);
    void LinkAL(ALGraph &G, int i, int j, int weight);
    void FindInDegree(ALGraph G, int indegree[]);
    void printTopo(int topo[], int m);
    
    
    //邻接表创建有向图
    void CreateUDG(ALGraph &G)
    {
        
    	G.vexnum = 9;						//输入总顶点数和边数
    	G.arcnum = 11;
    	G.vertices[0].data = 'v0';			//输入顶点信息
    	G.vertices[0].firstarc = NULL;
    	G.vertices[1].data = 'v1';
    	G.vertices[1].firstarc = NULL;
    	G.vertices[2].data = 'v2';
    	G.vertices[2].firstarc = NULL;
    	G.vertices[3].data = 'v3';
    	G.vertices[3].firstarc = NULL;
    	G.vertices[4].data = 'v4';
    	G.vertices[4].firstarc = NULL;
    	G.vertices[5].data = 'v5';
    	G.vertices[5].firstarc = NULL;
    	G.vertices[6].data = 'v6';
    	G.vertices[6].firstarc = NULL;
    	G.vertices[7].data = 'v7';
    	G.vertices[7].firstarc = NULL;
    	G.vertices[8].data = 'v8';
    	G.vertices[8].firstarc = NULL;
    
    	int i, j;							//输入边信息
    	i = LocateVex(G, 'v0');
    	j = LocateVex(G, 'v1');
    	LinkAL(G, i, j, 6);
    	i = LocateVex(G, 'v0');
    	j = LocateVex(G, 'v2');
    	LinkAL(G, i, j, 4);
    	i = LocateVex(G, 'v0');
    	j = LocateVex(G, 'v3');
    	LinkAL(G, i, j, 5);
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v4');
    	LinkAL(G, i, j, 1);
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v4');
    	LinkAL(G, i, j, 1);
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v5');
    	LinkAL(G, i, j, 2);
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v6');
    	LinkAL(G, i, j, 9);
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v7');
    	LinkAL(G, i, j, 7);
    	i = LocateVex(G, 'v5');
    	j = LocateVex(G, 'v7');
    	LinkAL(G, i, j, 4);
    	i = LocateVex(G, 'v6');
    	j = LocateVex(G, 'v8');
    	LinkAL(G, i, j, 2);
    	i = LocateVex(G, 'v7');
    	j = LocateVex(G, 'v8');
    	LinkAL(G, i, j, 4);
    }
    
    //建立边
    void LinkAL(ALGraph &G, int i, int j, int weight)
    {
        
    
    	ArcNode *p1;
    	p1 = new ArcNode;
    	p1->adjvex = j;
    	p1->nextarc = G.vertices[i].firstarc;						  //头插法
    	G.vertices[i].firstarc = p1;
    
    	p1->weight = weight;
    }
    
    //返回顶点位置下标
    int LocateVex(ALGraph G, char v)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		if (G.vertices[i].data == v)
    		{
        
    			return i;
    		}
    	}
    }
    
    //打印输出图
    void printGraph(ALGraph G)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		printf("%d :", i);
    		printf("v%d ->", i);
    
    		ArcNode *p;
    		p = G.vertices[i].firstarc;
    		while (p != NULL)
    		{
        
    			printf("%d->", p->adjvex);
    			p = p->nextarc;
    		}
    		printf("\n");
    	}
    }
    
    //邻接表深度优先遍历
    bool visited[MVNum];
    void DFS_AL(ALGraph G, int v)
    {
        
    	printf("v%c->", G.vertices[v].data);
    	visited[v] = true;
    	ArcNode *p;
    	p = G.vertices[v].firstarc;
    	while (p != NULL)
    	{
        
    		int w = p->adjvex;
    		if (!visited[w])
    		{
        
    			DFS_AL(G, w);
    		}
    		p = p->nextarc;
    	}
    }
    
    
    
    //定义栈
    #define MAXSIZE 100
    typedef struct
    {
        
    	int base[MAXSIZE];
    	int *top;
    	int stacksize;
    }SqStack;
    //初始化
    int InitStack(SqStack &S)
    {
        
    	S.top = S.base;
    	S.stacksize = MAXSIZE;
    	return 1;
    }
    //入栈
    int Push(SqStack &S, int e)
    {
        
    	if (S.top - S.base == S.stacksize) return 0;
    	*S.top++ = e;
    	return 1;
    }
    //出栈
    int Pop(SqStack &S, int &e)
    {
        
    	if (S.top == S.base) return 0;
    	e = *--S.top;
    	return 1;
    }
    
    
    //拓扑排序
    int indegree[MVNum];		//存放各顶点入度
    int topo[MVNum];			//存放拓扑序列的顶点序号
    SqStack S;					//暂存入度为0的顶点
    int TopologicalSort(ALGraph G, int topo[])
    {
        
    	ArcNode *p;
    	int i, m = 0;				//m用来计数
    	FindInDegree(G, indegree);	//求各顶点的入度存入indegree数组
    	InitStack(S);
    	for (i = 0; i < G.vexnum; i++)
    	{
        
    		if (!indegree[i])
    		{
        
    			Push(S, i);			//入度为0的入栈
    		}
    	}
    
    	while (S.base != S.top)
    	{
        
    		Pop(S, i);
    		topo[m] = i;		//入度为0的出栈并存入topo数组中
    		m++;				//计数加一
    		p = G.vertices[i].firstarc;		//p指向后继边结点
    		while (p != NULL)
    		{
        
    			int k = p->adjvex;			//k为顶点下标值
    			--indegree[k];				//顶点的入度减1来代替删除边的操作
    			if (indegree[k] == 0)		//如果减1后为0 则入栈
    			{
        
    				Push(S, k);
    			}
    			p = p->nextarc;				//继续下一个后继边结点
    		}
    	}
    
    	if (m < G.vexnum)  return 0;		//输出的顶点数小千有向图中的顶点数，则说明有向图中存在环
    	else return m;						//否则投拓扑排序成功，无环
    }
    
    //求各顶点的入度
    void FindInDegree(ALGraph G, int indegree[])
    {
        
    	//初始化
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		indegree[i] = 0;
    	}
    
    	ArcNode *p;
    	//遍历整个邻接表求出入度
    	for (int j = 0; j < G.vexnum; j++)
    	{
        
    		p = G.vertices[j].firstarc;
    		while (p != NULL)
    		{
        
    			indegree[p->adjvex]++;
    			p = p->nextarc;
    		}
    	}
    }
    
    //打印拓扑序列
    void printTopo(int topo[], int m)
    {
        
    	printf("\n该图的一个拓扑序列为：");
    	for (int i = 0; i < m; i++)
    	{
        
    		printf("v%d->", topo[i]);
    	}
    }
    
    
    //关键路径算法
    int ve[MVNum];				//事件最早发生时间
    int vl[MVNum];				//事件最晚发生时间
    int CriticalPath(ALGraph G)
    {
        
    	//初始化最早发生时间为最小
    	int n, i;
    	if (!TopologicalSort(G, topo))   return 0;		//拓扑排序失败，有环！
    	n = G.vexnum;
    	for (i = 0; i < n; i++)
    	{
        
    		ve[i] = 0;
    	}
    
    	//求每个事件最早发生时间
    	ArcNode *p;
    	int k, j;
    	for (i = 0; i < n; i++)
    	{
        
    		k = topo[i];
    		p = G.vertices[k].firstarc;
    		while (p != NULL)
    		{
        
    			j = p->adjvex;
    			if (ve[j]<ve[k] + p->weight)		//更新顶点的最早方式时间即最大的weight活动
    			{
        
    				ve[j] = ve[k] + p->weight;		//第一个顶点的最早发生时间ve[0]==0；
    			}
    			p = p->nextarc;
    		}
    	}
    
    	//初始化最晚发生时间为最大
    	for (i = 0; i < n; i++)
    	{
        
    		vl[i] = ve[n - 1];
    	}
    
    	//逆拓扑排序求最迟发生时间
    	for (i = n - 1; i >= 0; i--)				//从倒数第二个顶点开始
    	{
        
    		k = topo[i];
    		p = G.vertices[k].firstarc;
    		while (p != NULL)
    		{
        
    			j = p->adjvex;
    			if (vl[k]>vl[j] - p->weight)
    			{
        
    				vl[k] = vl[j] - p->weight;
    			}
    			p = p->nextarc;
    		}
    	}
    
    
    	//判断是否为关键路径
    	printf("\n关键路径为：");
    	int e, l;
    	for (i = 0; i < n; i++)
    	{
        
    		p = G.vertices[i].firstarc;
    		while (p != NULL)
    		{
        
    			j = p->adjvex;
    			e = ve[i];
    			l = vl[j] - p->weight;
    			if (e == l)		//相等则为关键活动，输出对应的关键路径
    			{
        
    				printf("\nv%c->v%c ", G.vertices[i].data, G.vertices[j].data);
    			}
    			p = p->nextarc;
    		}
    	}
    }
    
    
    int main()
    {
        
    	ALGraph G;
    	CreateUDG(G);
    
    	printGraph(G);
    
    	int v = 0;
    	printf("深度优先遍历：");
    	DFS_AL(G, v);
    
    	//拓扑排序
    	printf("\n==========================\n");
    	int loop = TopologicalSort(G, topo);
    	if (loop == 0)
    	{
        
    		printf("\n拓扑排序失败，该图有环！\n");
    	}
    	else
    	{
        
    		printf("\n拓扑排序成功,该图无环！");
    		printTopo(topo, loop);		//输出拓扑序列
    	}
    
    	//关键路径
    	CriticalPath(G);
    	//输出ve[]和vl[]数组
    	printf("\nve[]:");
    	for (int i = 0; i <G.vexnum; i++)
    	{
        
    		printf("%d,", ve[i]);
    	}
    	printf("\nvl[]:");
    	for (int i = 0; i <G.vexnum; i++)
    	{
        
    		printf("%d,", vl[i]);
    	}
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020062211204172.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200622112241386.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200622112618135.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200622112930412.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70