图的关键路径 C语言

一时失言乱红尘 2022-11-20 04:53 217阅读 0赞

还是按照书上给的例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
图的关键路径必须了解的（以下都是自己理解的）：  
**（1）AOE-网**：带权值的AOV-网。（AOV-网是不带权值且没有回路的有向图）

**（2）Ve(i)**：顶点V(i)的最早发生时间。这里开始只知道图的源点Ve(0)的值，初始点顶点Ve(0)为0，Ve(i)的值便是从V(0)开始沿着各种路径到达顶点V(i)的最长路径。例如：图中V(0)有两种路径到达V(4)选择最长的那条，故Ve(4) == 7。

**（3）Vl(i)**：顶点V(i)的最迟发生时间。只有求出所有Ve(i)才能开始求Vl(i)，这里是根据终点开始算的，开始只知道图的终点Vl(8)的值（如图），Vl(8) = Ve(8)，然后倒着推，Vl(i)的值便是终点Vl(8)的值减去从V(i)到终点V(8)的最长路径。例如：图中终点Vl(8) = 18，Vl(4)=Vl(8)-11。

**（4）e(i)**：活动开始的最早发生时间。这是正推求边的值，e(i)便是第i条边的e值，计算这之前需要计算Ve(i)的值，根据Ve(i)来求；若e(i)的弧头连的是顶点j，则e(i) = Ve(j)。例如：图中e(1),e(2),e(3)的弧头都是V(0)，故e(1) = e(2) = e(3) = Ve(0) = 0。

**（5）l(i)**：活动开始的最迟发生时间。这里是求边的l值；相比于求e(i)，求l(i)是根据Vl(i)的值从弧尾开始的；若l(i)的弧尾是k，则l(i) = Vl(k)-第i条边的权值。例如：l(10)和l(11)的弧尾都是V(8)，则l(10) = Vl(8)-2 = 16，l(11) = Vl(8)-4 = 14。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]  
完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MVNum 100 //最大顶点数 
    #define MAXSIZE 100 //最大栈容量 
    
    void Interrupt(void)//创建一个中断函数 
    { 
    	while(1)//用于检测换行符，使函数脱离scanf的连续输出 
    		if(getchar()=='\n')
    			break;
    } 
    
    //导入栈定义 
    typedef struct 
    { 
    	int data[MAXSIZE];//静态顺序栈可用的最大容量 
    	int top;//栈顶 
    }SqStack;
    
    void InitStack(SqStack &S)//栈的初始化 
    { 
    	S.top = -1;//静态顺序栈中，使S.top=-1便是对栈的初始化 
    }
    
    int Push(SqStack &S,int e)//进栈 
    { 
    	if(S.top==MAXSIZE-1)//判断栈是否为满 
    	{ 
    		printf("栈满！\n");
    		return 0;
    	}
    	S.data[++S.top]=e;//S.top自加一，使S.top=0,使输入的e值导入栈中 
    	return 0; 
    }
    
    bool StackEmpty(SqStack S)//栈的判空操作 
    { 
    	if(S.top == -1)//若栈为空返回true，否则为false 
    		return true;
    	else
    		return false;
    }
    
    int Pop(SqStack &S)//使栈顶元素出栈，并返回栈顶元素，且栈长减一 
    { 
    	if(StackEmpty(S))//首先先判断栈是否为空 
    	{ 
    		printf("栈空!\n");
    		return -1;
    	}
    	else 
    		return S.data[S.top--];
    }
    
    //导入邻接矩阵定义 
    typedef struct ArcNode
    { 
    	int adjvex;//该边所指向的顶点的位置 
    	struct ArcNode *nextarc;//该向下一条边的指针 
    	int weight;
    }ArcNode;
    typedef struct VNode//顶点信息 
    { 
    	char data;//顶点名称 
    	ArcNode *firstarc;//指向第一条依附该顶点的边的指针 
    }VNode,AdjList[MVNum];//AdjList表示邻接表类型 
    typedef struct//邻接表 
    { 
    	AdjList vertices;
    	int vexnum,arcnum;//图的当前顶点数和边数 
    }ALGraph;
    
    void InitGraph(ALGraph &G)//图的初始化 
    { 
    	int i;
    	for(i=0;i<MVNum;i++)
    		G.vertices[i].firstarc = NULL;//使所有的第一个结点都置空，也就是后面设定的尾指针的判空操作 
    }
    
    void CreateGraph(ALGraph &G)//图的创建 
    { 
    	int i;//记录次数 
    	char a;//顶点变量 
    	printf("请输入顶点数和边数:");
    	scanf("%d %d",&G.vexnum,&G.arcnum);//顶点数和边数的赋值 
    	Interrupt();//该函数用于检测并吸收换行符 
    	printf("请输入顶点名称（连续输入）：");
    	for(i=0;i<G.vexnum;i++)//利用循环输入图中顶点名称 
    	{ 
    		scanf("%c",&a);
    		G.vertices[i].data = a;//第i个顶点的命名 
    	}
    	Interrupt();//该函数用于检测并吸收换行符
    	char b,c;//顶点变量 
    	int w,j,k;//w为权值变量，j和k是用来记录次数的 
    	for(i=0;i<G.arcnum;i++)//利用循环输入所有边的两个顶点和权值 
    	{ 
    		printf("请输入边的两个顶点和权值:");
    		scanf("%c %c %d",&b,&c,&w);//输入 
    		Interrupt();//该函数用于检测并吸收换行符
    		for(j=0;j<G.arcnum;j++)//该操作为书上的函数LocateVex操作 
    		{ 
    			if(G.vertices[j].data == b)//找到输入的顶点b的位置 
    			break;
    		}
    		for(k=0;k<G.arcnum;k++)
    		{ 
    			if(G.vertices[k].data == c)//找到输入的顶点c的位置 
    			break;
    		}
    		ArcNode *p1;//创建两个野结点 
    		p1 = (ArcNode*)malloc(sizeof(ArcNode));
    		p1->adjvex = k;
    		p1->weight = w;
    		p1->nextarc = G.vertices[j].firstarc;//类似于头插法 
    		G.vertices[j].firstarc = p1;//并使头结点永远放在第一位 
    	}
    }
    
    void InputGraph(ALGraph G)//邻接表的输出 
    { 
    	int i,j;//记录次数 
    	ArcNode *p;//用于遍历链表 
    	printf("邻接表为：\n");
    	for(i=0;i<G.vexnum;i++)//利用循环输出 
    	{ 
    		printf("%c",G.vertices[i].data);
    		p = G.vertices[i].firstarc;
    		while(p)//当p为空时，结束循环 
    		{ 
    			printf(" --> %d",p->adjvex);
    			p = p->nextarc;//p指向p的下一个结点 
    		}	
    		printf("\n");
    	}
    	printf("\n");
    }
    
    void FindInDegree(ALGraph G,int indegree[])//拓扑排序中所用到的各顶点入度函数 
    { 
    	int i,j;
    	ArcNode *p;//创建一个指针 
    	for(i=0;i<G.vexnum;i++)//数组初始化 
    		indegree[i] = 0;
    	for(i=0;i<G.vexnum;i++)//遍历整个邻接表 
    	{ 
    		p = G.vertices[i].firstarc;//指针指向第i个结点的firstarc 
    		while(p != NULL)//判断p是否为空 ，这里和拓扑排序函数中的刚好相反 
    		{ 
    			j = p->adjvex;
    			indegree[j]++;
    			p = p->nextarc;
    		}
    	}	
    }
    
    bool TopologicalSort(ALGraph G,int topo[])//拓扑排序 
    { 
    	int i,m,k;
    	int indegree[G.vexnum];
    	FindInDegree(G,indegree);//求各顶点入度函数 
    	SqStack S;
    	InitStack(S);//引入栈 
    	for(i=0;i<G.vexnum;i++)//遍历各顶点 
    	{ 
    		if(indegree[i] == 0)//入度为0的顶点进栈 
    			Push(S,i);
    	}
    	m = 0;//对输出顶点计数，初始化为0 
    	ArcNode *p;
    	while(StackEmpty(S) != true)//栈S非空 
    	{ 
    		i = Pop(S);//出栈，并赋值给i 
    		topo[m] = i;//将Vi保存在拓扑排序数组topo中 
    		m++;//对输出顶点计数 
    		p = G.vertices[i].firstarc;//p指向Vi的第一个邻接点 
    		while(p != NULL)
    		{ 
    			k = p->adjvex;//Vk为Vi的邻接点 
    			indegree[k]--;//Vi的每个邻接点的入度减1 
    			if(indegree[k] == 0)//若入度减为0，则入栈 
    				Push(S,k);
    			p = p->nextarc;//p指向Vi下一个邻接结点 
    		}
    	}
    	if(m<G.vexnum)//该有向图有回路 
    		return false;
    	else
    		return true;
    }
    
    bool CriticalPath(ALGraph G)//G为带权值的邻接表存储的有向图，输出G的各项关键路径 
    { 
    	int i,//次数记录 
    		j,k,//各顶点序号记录变量 
    		Ve[G.vexnum],Vl[G.vexnum],//各顶点的发生时间 数组 
    		e,l,//各顶点活动开始时间 
    		topo[G.vexnum];//拓扑排序数组 
    	if(!TopologicalSort(G,topo))//检查该有向图是否符合拓扑排序，并使拓扑排序结果导入topo[]数组中 
    		return false;
    	for(i=0;i<G.vexnum;i++)//数组Ve[]的初始化，全置为0 
    		Ve[i] = 0;
    	ArcNode *p;//创建一个野指针,便于遍历邻接表 
    	for(i=0;i<G.vexnum;i++)
    	{ 
    		k = topo[i];//取得拓扑序列中的顶点序号k 
    		p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点 
    		while(p != NULL)//依次更新k的所有邻接顶点的最早发生时间。若p为空结束循环 
    		{ 
    			j = p->adjvex;//j为邻接点的序号 
    			if(Ve[j] < Ve[k]+p->weight)//更新顶点j的最早发生时间Ve[j] 
    				Ve[j] = Ve[k]+p->weight;
    			p = p->nextarc;//p指向k的下一个邻接顶点 
    		}
    	}
    	for(i=0;i<G.vexnum;i++)//数组Vl[]的初始化，全置为数组Ve[]最后一个值 
    		Vl[i] = Ve[G.vexnum-1];
    	for(i=G.vexnum-1;i>=0;i--)//和上面那个循环类似，只是这里是倒着来的 
    	{ 
    		k = topo[i];//取得拓扑序列中的顶点序号k 
    		p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点 
    		while(p != NULL)
    		{ 
    			j = p->adjvex;//j为邻接点的序号
    			if(Vl[k] > Vl[j]-p->weight)//更新顶点k的最迟发生时间Vl[j]
    				Vl[k] = Vl[j]-p->weight;
    			p = p->nextarc;//p指向k的下一个邻接顶点 
    		}
    	}
    	for(i=0;i<G.vexnum;i++)//每次循环针对Vi为活动开始点的所有活动 
    	{ 
    		p = G.vertices[i].firstarc;//p指向i的第一个邻接顶点
    		while(p != NULL)
    		{ 
    			j = p->adjvex;//j为i的邻接顶点的序号 
    			e = Ve[i];//计算活动<Vi,Vj>的最早开始时间 
    			l = Vl[j]-p->weight;//计算活动<Vi,Vj>的最迟开始时间 
    			if(e == l)//若为关键活动，则输出<Vi,Vj>
    				printf("%c->%c ",G.vertices[i].data,G.vertices[j].data);
    			p = p->nextarc;//p指向k的下一个邻接顶点 
    		}
    	}
    }
    
    int main()
    { 
    	ALGraph G;
    	InitGraph(G);//初始化 
    	CreateGraph(G);//邻接表的创建 
    	InputGraph(G);//邻接表的输出 
    	int i,a[G.vexnum];
    	if(TopologicalSort(G,a)) //调用拓扑排序，若没有回路函数为true，否则false 
    		for(i=0;i<G.vexnum;i++)//利用循环打印拓扑后的值 
    			printf("%c ",G.vertices[a[i]].data);
    	else
    		printf("有回路！");
    	printf("\n");
    	CriticalPath(G);//关键路径函数 
    	return 0;
    }

结果演示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 2]  
（完）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/32a36daec7ed43fd96de7914ace56241.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/4f47a9d49cb147ce803fddcce2244bc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/6225a08de5624ad79785c9fa2c41c28c.png