现在的位置: 首页 > 综合 > 正文

图3–拓扑排序变体求重要路径

2013年12月02日 ⁄ 综合 ⁄ 共 8571字 ⁄ 字号 小 中 大 ⁄ 评论关闭

基本思路：

最早发生时间是越早越好，但由于前面路径的消耗不得不晚，早了前面就还没有完成

最晚发生时间是越晚越好，但由于后面路径的消耗不得不早，晚了后面的路径消耗来不及完成。

初始化最早发生时间数组为0，找到排序的下一顶点，用该顶点去更新最早发生时间并入栈，方法是用自身的最早发生时间+路径代价，如果大于连接的下一顶点的最早发生时间就更新一下下一顶点的最早发生时间。一直做到最后一个顶点，最后一个顶点不和任何顶点相连而什么都做，最后就可以得到最早发生时间数组和堆栈中的逆拓扑顺序的顶点序列。

初始化最晚发生时间数组为终点最早发生时间的值，逆拓扑顺序逐个出栈，用出栈的该顶点的最晚发生时间-路径代价更新相连的顶点，如果小于相连顶点的最晚发生时间，就更新下。这样一直做到最前面的顶点，最前面的顶点因为没有任何入度而不作任何操作。最后得到的就是最晚发生时间。

最后，一个顶点的最早发生时间等于最晚发生时间，就是关键顶点（不能有任何延迟），连起来就是关键路径。

邻接矩阵实现方法：

找到拓扑排序顶点，方法是循环列如果该列没有被访问过，则进入循环该列的行，如果全部为0则表明没有入度则记下下标并设置该行已经被访问过，跳出寻找的循环，否则就把全0计数器清0.然后用该下标找到该顶点入栈（为了形成逆拓扑序列），同时更新它相连的顶点的最早发生时间，如果该顶点的最早发生时间+路径消耗大于原本的值就更新下。循环做到最后。

得到的逆拓扑序列分别出栈得到顶点，更新它相连的前面一个顶点的最晚发生时间。一直到最后。

然后判断是否是关键顶点并形成critical path。

邻接表实现方法：

1 和矩阵类似，唯一的不同是，求最晚发生时间，顶点由堆栈pop出来，因此节点必须加一个属性number才能知道自己在顶点数组中的位置（不然就要遍历节点数组找到位置，空间换时间）。

2 用1知道的位置找到附表，用附表节点的最晚发生时间减去路径消耗去更新自己的最晚发生时间

3 判断关键顶点并形成critical path

代码：

[java]
view plaincopy
  1. package nuaa.ds;  
  2.   
  3.   
  4. //拓扑排序，排到了某个顶点就等于可以访问那个顶点  
  5. //计算该顶点的最早发生时间并入栈  
  6. //得到栈内的逆拓扑序列出栈分别计算顶点最晚发生时间  
  7. //顶点的最早发生时间等于最晚发生时间则该顶点为关键路径上的点  
  8. public class CPofGraph {  
  9.     private CreateGraph g;  
  10.       
  11.     private String[] vertexes;//邻接矩阵法所  
  12.     private int[][] vr;       //使用的成员变量  
  13.       
  14.     private VertexNode[] vertexNodes;//邻接表所使用的成员变量  
  15.       
  16.       
  17.     /** 
  18.      * 手动生成有向无环图测试算法 
  19.      * A->B->E-->F-->H 
  20.      *    ^  ^\     ^ 
  21.      *     \ | v  / 
  22.      * C---> D->G 
  23.      */  
  24.     public CPofGraph(CreateGraph g){  
  25.         this.g = g;  
  26.         switch(g){  
  27.         case AdjacencyMatrix://邻接矩阵  
  28.             this.vertexes = new String[]{"A","B","C","D","E","F","G","H"};  
  29.             vr = new int[8][8];  
  30.             //arcs都有权重  
  31.             vr[0] = new int[]{0,7,0,0,0,0,0,0};//好  
  32.             vr[1] = new int[]{0,0,0,0,3,0,0,0};  
  33.             vr[2] = new int[]{0,0,0,4,0,0,0,0};  
  34.             vr[3] = new int[]{0,2,0,0,1,0,0,0};//多  
  35.             vr[4] = new int[]{0,0,0,0,0,5,6,0};  
  36.             vr[5] = new int[]{0,0,0,0,0,0,0,2};//浪  
  37.             vr[6] = new int[]{0,0,0,0,0,0,0,4};  
  38.             vr[7] = new int[]{0,0,0,0,0,0,0,0};//费  
  39.             break;  
  40.         case AdjacencyTable:  
  41.             vertexNodes = new VertexNode[8];  
  42.             String[] temp = {"A","B","C","D","E","F","G","H"};  
  43.             for(int i=0;i<vertexNodes.length;i++){  
  44.                 vertexNodes[i] = new VertexNode(temp[i]);  
  45.                 vertexNodes[i].loc = i;  
  46.             }  
  47.             vertexNodes[0].arcNode = new ArcNode(1,7);  
  48.             vertexNodes[1].arcNode = new ArcNode(4,3);  
  49.             vertexNodes[2].arcNode = new ArcNode(3,4);  
  50.             vertexNodes[3].arcNode = new ArcNode(1,2);  
  51.             vertexNodes[3].arcNode.arcNode = new ArcNode(4,1);  
  52.             vertexNodes[4].arcNode = new ArcNode(5,5);  
  53.             vertexNodes[4].arcNode.arcNode = new ArcNode(6,6);  
  54.             vertexNodes[5].arcNode = new ArcNode(7,2);  
  55.             vertexNodes[6].arcNode = new ArcNode(7,4);  
  56.         }  
  57.           
  58.     }  
  59.       
  60.     /** 
  61.      * AOE(activity on edge)网，顶点表示事件，arc表示活动 
  62.      *  
  63.      */  
  64.     public void criticalPath(){//拓扑排序改改得到的关键路径  
  65.         this.criticalPath(this.g);         
  66.     };  
  67.       
  68.     private void criticalPath(CreateGraph g){  
  69.         switch(g){  
  70.         case AdjacencyMatrix:  
  71.             tCriticalPath();  
  72.             break;  
  73.         case AdjacencyTable:  
  74.             mCriticalPath();  
  75.         }  
  76.     }  
  77.     //该方法破坏了原来了邻接矩阵，应该拷贝一份再调用更合适  
  78.     private void tCriticalPath(){  
  79.         int[][] vrcopy = new int[vr.length][vr.length];  
  80.         for(int i=0;i<vrcopy.length;i++)  
  81.             for(int j=0;j<vrcopy.length;j++)  
  82.                 vrcopy[i][j] = vr[i][j];  
  83.         int[] ve = new int[vertexes.length];//顶点最早发生时间  
  84.         int[] vl = new int[vertexes.length];//顶点最晚发生时间  
  85.   
  86.         Stack<Integer> stack = new Stack<Integer>();  
  87.           
  88.         boolean[] visited = new boolean[vr.length];  
  89.         int zeroNumber = 0;//判断某列是否全为0  
  90.         int chosen = 0;//找到序列下一个节点就把下标记录下来  
  91.           
  92.         while(true){  
  93.               
  94.             //寻找拓扑序列下一节点  
  95.             for(int i=0;i<vr.length;i++){//i为列下标  
  96.                 if(!visited[i]){//如果该列代表元素没有被塞入拓扑序列  
  97.                     for(int j=0;j<vr.length;j++){//j为行下标，循环判断某列是否为全0  
  98.                         if(vr[j][i]!=0){//有非0元素表示有前序节点  
  99.                             break;//跳出来  
  100.                         }  
  101.                         zeroNumber++;//不然就++自增  
  102.                     }  
  103.                 }  
  104.                 if(zeroNumber==vr.length){//一列都为0  
  105.                     chosen = i;//记录下这个拓扑节点  
  106.                     visited[i] = true;//这个元素要被塞入拓扑序列  
  107.                     break;  
  108.                 }else{  
  109.                     zeroNumber = 0;  
  110.                 }  
  111.             }  
  112.             if(zeroNumber==vr.length){//如果找到了拓扑序列下一个节点  
  113.                 stack.push(chosen);  
  114.                 for(int i=0;i<vr.length;i++){//循环更新最早发生时间  
  115.                     if(vr[chosen][i]!=0&&ve[chosen]+vr[chosen][i]>ve[i]){  
  116.                         ve[i] = ve[chosen]+vr[chosen][i];  
  117.                     }  
  118.                     vr[chosen][i] = 0;//该行全部置为0  
  119.                 }  
  120.                       
  121.             }else{//找不到下一拓扑节点了  
  122.                 break;  
  123.             }  
  124.             zeroNumber = 0;//计数器归0  
  125.         }  
  126.       
  127.           
  128.         //计算最晚发生时间  
  129.         for(int i=0;i<vl.length;i++){//初始化，将最早发生时间当成最晚发生时间  
  130.             vl[i] = ve[ve.length-1];  
  131.         }  
  132.         while(!stack.isEmpty()){  
  133.             int iterator = stack.pop();  
  134.             for(int i=0;i<vrcopy.length;i++){  
  135.                 if(vrcopy[i][iterator]!=0&&vl[iterator]-vrcopy[i][iterator]<vl[i]){  
  136.                     vl[i] = vl[iterator]-vrcopy[i][iterator];  
  137.                 }  
  138.             }  
  139.         }  
  140.         //找到关键节点  
  141.         for(int i=0;i<ve.length;i++){  
  142.             if(ve[i]==vl[i])  
  143.                 System.out.print(vertexes[i]+" ");  
  144.         }  
  145.     }  
  146.       
  147.     private void mCriticalPath(){  
  148.         int[] ve = new int[vertexNodes.length];//顶点最早发生时间  
  149.         int[] vl = new int[vertexNodes.length];//顶点最晚发生时间  
  150.           
  151.         int[] indegree = this.getIndegree();  
  152.         Stack<VertexNode> stack = new Stack<VertexNode>();//要拓扑序列用Queue更合适,只是  
  153.         Stack<VertexNode> saveStack = new Stack<VertexNode>();//为了后面的关键路径算法  
  154.           
  155.         for(int i=0;i<indegree.length;i++){  
  156.             if(indegree[i]==0){  
  157.                 stack.push(vertexNodes[i]);  
  158.                   
  159.             }  
  160.         }  
  161.         while(!stack.isEmpty()){  
  162.             VertexNode vertexNode = stack.pop();  
  163.             saveStack.push(vertexNode);  
  164.             ArcNode p = vertexNode.arcNode;  
  165.             while(p!=null){  
  166.                 indegree[p.serialNumber]--;  
  167.                 if(indegree[p.serialNumber]==0){  
  168.                     stack.push(vertexNodes[p.serialNumber]);  
  169.                       
  170.                 }  
  171.                 if(ve[vertexNode.loc]+p.weight>ve[p.serialNumber]){//最早发生时间有更大的值  
  172.                     ve[p.serialNumber] = ve[vertexNode.loc]+p.weight;  
  173.                 }  
  174.                 p = p.arcNode;  
  175.             }  
  176.         }  
  177.         for(int i=0;i<vl.length;i++){  
  178.             vl[i] = ve[ve.length-1];//初始化最晚发生时间  
  179.         }  
  180.         while(!saveStack.isEmpty()){  
  181.             VertexNode v = saveStack.pop();  
  182.             ArcNode p = v.arcNode;  
  183.             while(p!=null){  
  184.                 if(vl[p.serialNumber]-p.weight<vl[v.loc]){  
  185.                     vl[v.loc] = vl[p.serialNumber]-p.weight;  
  186.                 }  
  187.                 p = p.arcNode;  
  188.             }  
  189.               
  190.         }  
  191.         //找到关键节点  
  192.         for(int i=0;i<ve.length;i++){  
  193.             if(ve[i]==vl[i])  
  194.                 visit(vertexNodes[i]);  
  195.         }  
  196.           
  197.           
  198.     }  
  199.     //邻接表求入度，入度in English 怎么说。。。。。。。。。  
  200.     private int[] getIndegree(){  
  201.         int[] indegree = new int[this.vertexNodes.length];  
  202.         for(int i=0;i<vertexNodes.length;i++){  
  203.             ArcNode p = vertexNodes[i].arcNode;  
  204.             while(p!=null){  
  205.                 indegree[p.serialNumber]++;//序号表示节点在入度数组的位置  
  206.                 p = p.arcNode;  
  207.             }  
  208.         }  
  209.         return indegree;  
  210.     }  
  211.       
  212.       
  213.     private void visit(VertexNode node){  
  214.         System.out.print(node.vertex+" ");  
  215.     }  
  216.       
  217.     class VertexNode{  
  218.         String vertex;  
  219.         ArcNode arcNode;  
  220.         int loc;//又加的一个字段，堆栈里找到vertexNode必须要知道下标  
  221.                 //才能用下标定位到自己的最早发生时间+弧长度更新节点的最早发生时间  
  222.         public VertexNode(String vertex){  
  223.             this.vertex = vertex;  
  224.         }  
  225.     }  
  226.     class ArcNode{  
  227.         int serialNumber;//存放边连着的节点在vertexNode数组里面的位置  
  228.         int weight;//权重在求最小生成树时用到，拓扑排序没有  
  229.         ArcNode arcNode;  
  230.         public ArcNode(int serialNumber,int weight){  
  231.             this.serialNumber = serialNumber;  
  232.             this.weight = weight;  
  233.         }  
  234.     }  
  235. } 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞