Java数据结构之关键路径

深碍√TFBOYSˉ_ 2022-02-01 10:49 290阅读 0赞

# 基本概念 #

1.  AOE网：在[AOV网][AOV]中，当弧上带有权值时，称这种有向网为边活动网，简称AOE网。在AOE网中，弧指向事件表示该弧代表的活动已经完成，弧从事件出发表示弧代表的活动开始进行，故AOE网中同样不能有回环存在。
2.  源点：AOE网常用来表示工程的进行，表示工程开始事件的顶点的入度为0，称为源点。
3.  汇点：表示工程结束事件的顶点的出度为0，称为汇点。

> 一个AOE网是只有一个源点和一个汇点的有向无环图。

1.  关键路径：在AOE网中可能存在并行的互动，故存在从源点到汇点的最短路径，即完成工程的最短时间，称这条路径为关键路径，构成关键路径的弧称为关键活动。

> 1.事件的最早发生时间ve\[k\]  
> ve\[k\]是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。如图1所示，vk事件开始的条件是入度为0，故只有所有指向vk的活动全部执行完，vk事件才能开始。  
> ![在这里插入图片描述][20190514100441750.PNG]  
> 2. 事件的最迟发生时间vl\[k\]  
> vl\[k\]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。在逆拓扑序列中，通常汇点的发生时间已定，为了保证汇点准点发生，需要确定事件vk的最晚发生时间。如图2所示，vk所指向的三个顶点的发生时间已定，故vk的发生时间只能是min(vl\[k\])，否则会使vk的后继顶点存在推迟发生，从而是汇点的发生时间推迟。  
> ![在这里插入图片描述][20190514102122122.PNG]  
> 3. 活动的最早开始时间e\[i\]  
> 若活动ai是由弧<vk , vj>表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有：e\[i\]=ve\[k\]  
> 4. 活动的最晚开始时间l\[i\]  
> 活动ai的最晚开始时间是指，在不推迟整个工期的前提下， ai必须开始的最晚时间。若ai由弧<vk，vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，有：l\[i\]=vl\[j\]-len<vk, vj>

# 核心思想 #

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

1.  根据正、逆拓扑序列求出图3中每个事件（顶点）的ve和vl；  
    ![在这里插入图片描述][20190514103818758.PNG]
2.  根据正、逆拓扑序列求出图3中每个活动（弧）的e和l；  
    ![在这里插入图片描述][20190514103959156.PNG]
3.  找出e\[i\]=l\[i\]的活动，即为关键路径  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 1]

# 代码实现 #

package Topologic;
    
    import java.util.ArrayList;
    //其中的导入包请参见页底
    import ch03.LinkStack;
    import cho6.ALGraph;
    import cho6.VNode;
    import cho6.ArcNode;
    
    public class CriticalPathMethod {
    	private int[] ve; // 顶点（事件）的最早发生时间,默认全为0
    	private int[] vl; // 顶点（事件）的最晚发生时间,默认全为0
    	private LinkStack t; // 用于保存逆拓扑序列的栈
    	private ALGraph al; // 用于保存AOE网的邻接表
    
    	public CriticalPathMethod(ALGraph al) {
    		this.al = al;
    	}
    
    	/**
    	 * 顺序拓扑序列
    	 * @return 是否能构成拓扑序列
    	 * @throws Exception
    	 */
    	private boolean topoOrder() throws Exception {
    		int count = 0;
    		LinkStack s = new LinkStack();// 用于保存零入度的顶点的栈
    		int[] inDegree = al.getInDegree();
    		for (int i = 0; i < inDegree.length; i++) {
    			if (inDegree[i] == 0)
    				s.push(i);
    		}
    		while (!s.isEmpty()) {
    			int j = (Integer) s.pop();// 零入度栈出栈
    			t.push(j);
    			count++;
    			for (ArcNode node = ((VNode) al.getVex(j)).firstArc; node != null; node = node.nextArc) {
    				int k = node.adjVex;// j,k即表示顶点j到顶点k
    				int value = node.value;// value表示<j,k>的距离，即权值
    				if (--inDegree[k] == 0) {
    					s.push(k);
    				}
    				if (ve[j] + value > ve[k]) {
    					ve[k] = ve[j] + value;
    				}
    			}
    		}
    
    		if (count == al.getVNum())
    			return true;
    		else
    			return false;
    	}
    
    	/**
    	 * 逆序拓扑序列
    	 * @return 是否能构成拓扑序列
    	 * @throws Exception
    	 */
    	private boolean reTopoOrder() throws Exception {
    		if (!topoOrder())
    			return false;
    		for (int i = 0; i < al.getVNum(); i++) {
    			vl[i] = ve[al.getVNum() - 1];// 令所有顶点（事件）的最晚发生时间和汇点的最早发生时间相等
    		}
    		while (!t.isEmpty()) {
    			int j = (Integer) t.pop();// 逆序拓扑栈出栈
    			for (ArcNode node = ((VNode) al.getVex(j)).firstArc; node != null; node = node.nextArc) {
    				int k = node.adjVex;// j,k即表示顶点j到顶点k
    				int value = node.value;// value表示<j,k>的距离，即权值
    				if (vl[k] - value < vl[j]) {
    					vl[j] = vl[k] - value;
    				}
    			}
    		}
    		
    		return true;
    	}
    	
    	public void getCriticalPah() throws Exception {
    		if(!reTopoOrder())
    			throw new Exception("所构建的AOE网不存在拓扑序列，故不存在关键路径！");
    		ArrayList a = new ArrayList();
    		for(int j=0;j<al.getVNum();j++) {
    			for(ArcNode node = ((VNode) al.getVex(j)).firstArc; node != null; node = node.nextArc) {
    				int k = node.adjVex;
    				int value = node.value;
    				int e = ve[j];//边（活动）的最早开始时间
    				int l = ve[k] - value;//边（活动）的最晚开始时间
    				if(e == l) {
    					System.out.println(al.getVex(j) + "-->" + al.getVex(k));
    				}
    			}
    		}
    	}
    }

### 参考类 ###

> [ch03.LinkStack][]  
> [cho6.ALGraph][]  
> [VNode][cho6.ALGraph]  
> [ArcNode][cho6.ALGraph]

[AOV]: https://blog.csdn.net/weixin_44270248/article/details/89926312
[20190514100441750.PNG]: /images/20220201/0ee868bd28d2494fb55ade1338329405.png
[20190514102122122.PNG]: /images/20220201/e8fc0c556626471e882f355c8d479fdc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20220201/b2e1b198c82d4ea1b1680fef85a44424.png
[20190514103818758.PNG]: /images/20220201/9822bf2fa455466f8d9074762cc88cba.png
[20190514103959156.PNG]: /images/20220201/ae7cb8b9bb244ad8b28ea8b3cdda757a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220201/2763ec5279b44d0fae289d84ea513d08.png
[ch03.LinkStack]: https://blog.csdn.net/weixin_44270248/article/details/89482106
[cho6.ALGraph]: https://blog.csdn.net/weixin_44270248/article/details/90210652