拓扑排序和关键路径算法----关键路径算法 (C语言实现)

Myth丶恋晨 2023-03-01 05:42 2阅读 0赞

在学习了拓扑排序之后，我们可以开始学习关键路径了。拓扑排序可以有多个起点和多个终点，跟拓扑排序不同的是，关键路径只能有一个起点、一个终点。

我们使用带有权重的有向图表示，8 -> 0 -> 1 -> 4 -> 5 -> 7这条红色的路径就是关键路径。关键路径的特征是：从起点 (起点是唯一的，入度为0) 到终点 (终点是唯一的，出度为0) 的一个有向图中，该路径上的弧 (有向图的边称之为“弧”) 的权重的和最大。关键路径可能不是唯一的，但不同的关键路径上的权重之和是相同的。  
如果把从起点到终点的所有事件看作一个工程，减小非关键路径上的弧的权重不会降低整个工程的时间。减少关键路径上的弧的权重，可以减少整个工程的时间。如果这个工程中有多条关键路径，那么必须同时压缩所有的关键路径，才能减少整个工程的时间。压缩关键路径可能导致的一个问题：关键路径变成非关键路径，而原先的非关键路径变成新的关键路径。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]我们发现，这一条关键路径一定是一个拓扑排序的子序列。所以我们就可以用拓扑排序计算关键路径了。但问题是拓扑排序有多种结果，怎么才能拿到关键路径 (权重的和最大) 呢？

首先，我们需要计算每个节点的earlyTime (最早开始时间)。终点的earlyTime 就是从起点到终点的最大权重和。  
其次，如果我们从终点到起点，进行反向的计算lastTime (最晚开始时间)，如果某一条路径的每一个结点的earlyTime 与lastTime都相等，那么这条路径就是关键路径。

怎么计算每个节点的earlyTime呢？我们可以用递推。  
例如：从起点开始，有两条路径可以到达3号点。分别是：8 -> 0 -> 3和8 -> 2 -> 3。我们只需要取这两条路径的权重最大值，那就是8 -> 3的权重。递推关系式：  
earlyTime(0) = max\[earlyTime(0), earlyTime(8) + weight8\_0\]  
earlyTime(2) = max\[earlyTime(2), earlyTime(8) + weight8\_2\]

earlyTime(3) 需要计算两次：  
earlyTime(3) = max\[earlyTime(3), earlyTime(0) + weight0\_3\]  
earlyTime(3) = max\[earlyTime(3), earlyTime(2) + weight2\_3\]

用同样的方法就可以计算出终点7的earlyTime，也就是从起点到终点的最大权重和。

在得到从起点到终点的最大权重和之后，我们就可以反向计算了。显然，终点的lastTime 和earlyTime是同一个值。那么其它结点的lastTime的初始值是多少呢？可以简单的赋值为∞ (无穷大，inf)，或者也同样设置为终点的lastTime。

计算结点的lastTime与计算earlyTime类似，也可以用递推。例如一共有两条路径从终点出发，反向走到结点4，分别是7 -> 5 -> 4和7 -> 6 -> 4。递推关系式：  
lastTime(5) = min\[lastTime(5), lastTime(7) - weight5\_7\]  
lastTime(6) = min\[lastTime(6), lastTime(7) - weight6\_7\]

lastTime(4) 需要计算两次：  
lastTime(4) = min\[lastTime(4), lastTime(5) - weight4\_5\]  
lastTime(4) = min\[lastTime(4), lastTime(6) - weight4\_6\]  
用同样的方法就可以计算出所有结点的lastTime。接着对比一下每个结点的earlyTime和lastTime。如果这两个值相等，则这个结点一定是关键路径上的结点，输出这个结点的编号即可。

总体的代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    int arr[9][9]; //存放weight的二维数组
    int size = 9; //图上的结点数
    int inf = 999; //无穷大
    
    //声明结构体:结点 
    struct Node{
        
    	int index; //编号 
    	int inDegree; //入度 
    	int earlyTime = 0; //最早的发生时间，默认为0 
    	int lastTime = inf; //最晚的发生时间，默认为无穷大 
    	struct Node * next; //下一个结点的指针 
    };
    
    int stack [100]; //用栈辅助实现拓扑排序，用数组实现栈
    int top = 0; //栈的头元素的index 
    
    int queue[100]; //一个用数组实现的队列 
    int head = 0; //队列的头 
    int tail = 0; //队列的尾 
    
    //用一个数组存放首元素。每个首元素后面用指针连接各个结点 
    struct Node arrNode[8];
     
    //头插法，得到的结果的次序是反的是得到的结果的次序是反的 
    void addNode(int parentIndex, int nodeIndex)
    {
        
    	struct Node * parentNode;
    	parentNode = &arrNode[parentIndex];
    	
    	//向操作系统申请空间 
    	struct Node *temp = (struct Node *)(malloc(sizeof(struct Node)));
    	temp->index = nodeIndex;
    	temp->next = parentNode->next;
    	
    	parentNode->next = temp; 
    	arrNode[nodeIndex].inDegree++; //入度 + 1
    	temp->inDegree = arrNode[nodeIndex].inDegree;
    }
    
    //遍历一个结点，和它的所有相连的结点 
    void traverse(int parentIndex)
    {
        
    	struct Node * node = &arrNode[parentIndex];
    	while(node != NULL)
    	{
        
    		printf("%d (%d) --> ", node->index, node->inDegree);
    		node = node->next;
    	}
    	printf("\r\n");
    }
    
    int max(int a, int b) //求两个数中的最大值 
    {
        
    	return a > b ? a : b; //三元运算符
    }
    
    int min(int a, int b) //求两个数中的最小值
    {
        
    	return a < b ? a : b; //三元运算符
    }
    
    //用二维数组储存图，其实要的仅仅是weight 
    void initMap()
    {
        
    	for(int i = 0; i < size; i++)
    	{
        
    		for(int j = 0; j < size; j++)
    		{
        
    			arr[i][j] = 0;
    		}
    	}
    	
    	//对有向图中的边进行赋值
    	arr[0][1] = 10; arr[0][3] = 2; arr[1][4] = 3; arr[2][3] = 3; arr[3][4] = 4; arr[4][5] = 6;
    	arr[4][6] = 3; arr[5][7] = 2; arr[6][7] = 3; arr[8][0] = 3; arr[8][2] = 3;
    }
    
    int TopologicalOrderByStack() //栈辅助实现的拓扑排序 
    {
        
    	int count = 0; //用来计数
    	int index = 0; //输出的结点的编号 
    	int i = 0; //循环变量 
    	
    	//1、遍历所有结点，寻找入度为0的结点，并把编号存放在stack中 
    	for(i = 0; i < size; i++) 
    	{
        
    		struct Node node = arrNode[i];
    		if(node.inDegree == 0)
    		{
        
    			stack[top] = i; //把结点的编号存放到stack中 
    			top++; //top + 1 
    		}
    	}
    	
    	//2、弹出栈中的结点，输出结点编号。同时让该结点的下一级结点的入度-1 
    	//3、循环，直到栈中的结点为0，即top == 0 
    	while(top > 0)
    	{
        
    		top--; //top的位置没有内容，所以要先 - 1 
    		index = stack[top]; //得到存放在stack中的编号 
    		queue[tail] = index; //把编号存放到queue中 
    		tail++; //存放数据后，队列的tail + 1 
    		
    		printf("%d(%d) -> ", index, arrNode[index].earlyTime); //输出编号和earlyTime
    		count++; //计数 + 1 
    		
    		//从arrNode中获得结点的指针 
    		struct Node * parentNode = &arrNode[index]; //得到数组arrNode中的指定节点 
    		struct Node * node = parentNode->next; //得到arrNode中的指定节点的子节点
    		
    		//遍历
    		while(node != NULL) //如果子节点不是NULL就循环 
    		{
        
    			int sonIndex = node->index; //子节点的index 
    
    			//计算子节点的earlyTime
    			arrNode[sonIndex].earlyTime = max(arrNode[sonIndex].earlyTime, arrNode[index].earlyTime + arr[index][sonIndex]);
    			
    			//从arrNode中获得结点、结点信息 
    			if(arrNode[sonIndex].inDegree > 0) //子节点的入度 > 0 
    			{
        
    				//结点的inDegree - 1 
    				arrNode[sonIndex].inDegree--;
    				
    				//如果结点的inDegree == 0
    				if(arrNode[sonIndex].inDegree == 0)
    				{
        
    					//把结点的index (也就是sonIndex) 加入到stack中 
    					stack[top] = sonIndex;
    					top++;
    				}
    			}
    			node = node->next; //指针指向下一个子节点 
    		}
    	}
    	
    	if(count < size) //如果输出的结点数 < 总结点数 
    	{
        
    		return 0; //不存在拓扑排序
    	}
    	return 1; //存在拓扑排序 
    }
    
    void releaseResource() //释放资源
    {
        
    	//同前
    }
    
    void showQueue()
    {
        
    	printf("\r\n显示队列：\r\n");
    	int myHead = head;
    	
    	while(myHead < tail)
    	{
        
    		printf("%d, ", queue[myHead]);
    		myHead++;
    	}
    	printf("\r\n\r\n");
    }
    
    void getKeyRoute() //关键路径 
    {
        
    	//最终结点的最晚发生时间就是它的最早发生时间
    	arrNode[queue[tail - 1]].lastTime = arrNode[queue[tail - 1]].earlyTime;  
    	
    	//从终点往起点开始，反着计算。这种计算方式的时间复杂度为O(N^2)  
    	for(int i = tail - 1; i >= head; i--)
    	{
        
    		for(int j = i; j >= head; j--)
    		{
        
    			if(arr[queue[j]][queue[i]] > 0)
    			{
        
    				//注意，这是一个有向图。所以不能用arr[queue[i]][queue[j]]，
    				//arr[queue[i]][queue[j]]的值一定是0，用arr[queue[j]][queue[i]] 
    				arrNode[queue[j]].lastTime = min(arrNode[queue[j]].lastTime, arrNode[queue[i]].lastTime - arr[queue[j]][queue[i]]);
    				
    				//显示每个节点的lastTime 
    				//printf("arrNode[%d].lastTime = %d, arr[queue[j]][queue[i]] = %d\r\n", queue[j], arrNode[queue[j]].lastTime, arr[queue[j]][queue[i]]);
    			}
    		}
    	}
    	printf("\r\n\r\n显示每个节点和它的lastTime：\r\n");
    	for(int i = 0; i < size; i++)
    	{
        
    		printf("%d (%d), ", queue[i], arrNode[queue[i]].lastTime);
    	}
    	
    	printf("\r\n\r\n关键路径：\r\n");
    	for(int i = 0; i < size; i++)
    	{
        
    		//如果结点的earlyTime与反向计算得到的lastTime相等，说明是关键路径上的点
    		//但是，如果有多条关键路径，这里只会傻傻的一起输出，而不是分开输出。 
    		if(arrNode[queue[i]].earlyTime == arrNode[queue[i]].lastTime)
    		{
        
    			printf("%d(%d), ", queue[i], arrNode[queue[i]].lastTime);
    		}
    	}
    }
    
    int main() 
    {
        
    	initMap(); //初始化地图 (weight)
    	 
    	//初始化 
    	for(int  i = 0; i < size; i++)
    	{
        
    		arrNode[i].index = i;	
    		arrNode[i].inDegree = 0;
    		arrNode[i].next = NULL;
    	}
    	
    	//插入数据
    	addNode(0, 1); addNode(0, 3); addNode(1, 4); addNode(2, 3); addNode(3, 4);addNode(4, 5);
        addNode(4, 6); addNode(5, 7); addNode(6, 7); addNode(8, 0);addNode(8, 2);
    	//addNode(5, 1); //加上这一行，就会形成环，也就没有拓扑排序了 
    	
    	for(int i = 0; i < size; i++) //对每个节点遍历它的相邻节点
    	{
        
    		traverse(i);
    	}
    	
    	if(TopologicalOrderByStack())
    	{
        
    		printf("存在拓扑排序\r\n");
    	}
    	else
    	{
        
    		printf("不存在拓扑排序\r\n");
    	}
    	///完成拓扑排序和计算earlyTime 
    	
    	showQueue(); //显示队列中的内容，这里把队列当初数组看 
    	
    	printf("拓扑排序的首元素：%d\r\n", queue[head]);
    	printf("拓扑排序的尾元素：%d\r\n", queue[tail - 1]);
    
    	getKeyRoute(); //计算关键路径 
    	
    	releaseResource(); //释放资源 
    	printf("\r\nHello\r\n");
    	return 0;
    }

运行结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]很明显，关键路径上的结点的earlyTime与lastTime都相等。如果一个有向图中有多条关键路径，这个代码不会分别显示。只会把所有结点按照拓扑排序中的次序依次显示。  
这个算法的思路不难，但是过程却比较复杂，代码也相对比较长。代码中大部分是拓扑排序的内容，真正计算关键路径的代码其实不多。另外，这里使用邻接矩阵的方式储存图的边长 (weight)，需要两层for循环才能最终确定每一个结点的lastTime，所以关键路径算法的时间复杂度为O(N^2)。

关键路径算法是“图”的最后一个扩展算法。它是运筹学的一部分。根据关键路径，可以明确加快哪些步骤可以加速整个工程的进度。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/2c4608a4fdab4878a3441b5508ba2904.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: /images/20230209/5042ec7c92e043f2a0b949e30c1338ff.png