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

图2—-拓扑排序

2013年03月10日 ⁄ 综合 ⁄ 共 6668字 ⁄ 字号 小 中 大 ⁄ 评论关闭

拓扑排序，也就是AOV（activity on vertex)，顶点的活动有先后执行顺序，用于有向无环图。

基本思路是

1 找到无入度的点，然后去掉这个点和这个点的出度边。

2 循环执行1直到再也找不到点

3 如果点的个数等于顶点数则生成一个拓扑序列，如果小的话就是有环。

邻接矩阵实现方法：

用列下标循环，如果列没有访问过，则进入行下标循环，如果该列都为0，则表示该列表示的节点没有入度，记下下标。如果该列不是全为0则计数器清0.

用刚存入的下标找到顶点存入拓扑序列，同时将该列下标表示的顶点的出度边都去掉（就是用下标表示的行全部置为0），计数器清0.

重复上面的动作直到再也找不到为止，跳出最外层循环。

邻接表实现方法：

首先定义入度数组，用下标找到位置然后循环邻接表设置入度值。

堆栈初始化，将入度为0的顶点入栈，计数器自增。

当堆栈不为空的时候循环，出栈的顶点（去掉顶点）找到连接的arc链表，链表的保存的序号对应着节点也对应着入度数组的位置（根据序号将入度数组的值自减），如果入度为0则将该顶点入栈（下标找到该顶点），计数器自增。

最后判断个数是否是顶点的个数。

代码：

[java]
view plaincopy
  1. package nuaa.ds;  
  2.   
  3. public class Digraph {  
  4.     private CreateGraph g;  
  5.       
  6.     private String[] vertexes;//邻接矩阵法所  
  7.     private int[][] vr;       //使用的成员变量  
  8.       
  9.     private VertexNode[] vertexNodes;//邻接表所使用的成员变量  
  10.       
  11.       
  12.     /** 
  13.      * 手动生成有向无环图测试算法 
  14.      * A->B->E-->F-->H 
  15.      *    ^  ^\     ^ 
  16.      *     \ | v  / 
  17.      * C---> D->G 
  18.      */  
  19.     public Digraph(CreateGraph g){  
  20.         this.g = g;  
  21.         switch(g){  
  22.         case AdjacencyMatrix://邻接矩阵  
  23.             this.vertexes = new String[]{"A","B","C","D","E","F","G","H"};  
  24.             vr = new int[8][8];  
  25.             //arcs都有权重  
  26.             vr[0] = new int[]{0,7,0,0,0,0,0,0};//好  
  27.             vr[1] = new int[]{0,0,0,0,3,0,0,0};  
  28.             vr[2] = new int[]{0,0,0,4,0,0,0,0};  
  29.             vr[3] = new int[]{0,2,0,0,1,0,0,0};//多  
  30.             vr[4] = new int[]{0,0,0,0,0,5,6,0};  
  31.             vr[5] = new int[]{0,0,0,0,0,0,0,2};//浪  
  32.             vr[6] = new int[]{0,0,0,0,0,0,0,4};  
  33.             vr[7] = new int[]{0,0,0,0,0,0,0,0};//费  
  34.             break;  
  35.         case AdjacencyTable:  
  36.             vertexNodes = new VertexNode[8];  
  37.             String[] temp = {"A","B","C","D","E","F","G","H"};  
  38.             for(int i=0;i<vertexNodes.length;i++){  
  39.                 vertexNodes[i] = new VertexNode(temp[i]);  
  40.             }  
  41.             vertexNodes[0].arcNode = new ArcNode(1,7);  
  42.             vertexNodes[1].arcNode = new ArcNode(4,3);  
  43.             vertexNodes[2].arcNode = new ArcNode(3,4);  
  44.             vertexNodes[3].arcNode = new ArcNode(1,2);  
  45.             vertexNodes[3].arcNode.arcNode = new ArcNode(4,1);  
  46.             vertexNodes[4].arcNode = new ArcNode(5,5);  
  47.             vertexNodes[4].arcNode.arcNode = new ArcNode(6,6);  
  48.             vertexNodes[5].arcNode = new ArcNode(7,2);  
  49.             vertexNodes[6].arcNode = new ArcNode(7,4);  
  50.         }  
  51.           
  52.     }  
  53.       
  54.     /** 
  55.      * AOV(activity on vertex)网，顶点表示活动的网 
  56.      * 工程上有用，图必须为无回路的图 
  57.      */  
  58.     public void topologicalSort(){//拓扑排序，排序结果不唯一  
  59.         this.topologicalSort(this.g);         
  60.     };  
  61.       
  62.     private void topologicalSort(CreateGraph g){  
  63.         switch(g){  
  64.         case AdjacencyMatrix:  
  65.             mTopologicalSort();  
  66.             break;  
  67.         case AdjacencyTable:  
  68.             tTopologicalSort();  
  69.         }  
  70.     }  
  71.     //该方法破坏了原来了邻接矩阵，应该拷贝一份再调用更合适  
  72.     private void mTopologicalSort(){  
  73.         boolean[] visited = new boolean[vr.length];  
  74.           
  75.         int zeroNumber = 0;//判断某列是否全为0  
  76.         int chosen = 0;//找到序列下一个节点就把下标记录下来  
  77.         int count = 0;//判断序列个数，得到的图是否是有向无环图  
  78.         while(true){  
  79.               
  80.             //寻找拓扑序列下一节点  
  81.             for(int i=0;i<vr.length;i++){//i为列下标  
  82.                 if(!visited[i]){//如果该列代表元素没有被塞入拓扑序列  
  83.                     for(int j=0;j<vr.length;j++){//j为行下标，循环判断某列是否为全0  
  84.                         if(vr[j][i]!=0){//有非0元素表示有前序节点  
  85.                             break;//跳出来  
  86.                         }  
  87.                         zeroNumber++;//不然就++自增  
  88.                     }  
  89.                 }  
  90.                 if(zeroNumber==vr.length){//一列都为0  
  91.                     chosen = i;//记录下这个拓扑节点  
  92.                     visited[i] = true;//这个元素要被塞入拓扑序列  
  93.                     break;  
  94.                 }else{  
  95.                     zeroNumber = 0;  
  96.                 }  
  97.             }  
  98.             if(zeroNumber==vr.length){//如果找到了拓扑序列下一个节点  
  99.                 visit(vertexes[chosen]);//这里直接打印下。不是很合适  
  100.                 for(int i=0;i<vr.length;i++){  
  101.                     vr[chosen][i] = 0;//该行全部置为0  
  102.                 }  
  103.                 count++;          
  104.             }else{//找不到下一拓扑节点了  
  105.                 break;  
  106.             }  
  107.             zeroNumber = 0;//计数器归0  
  108.         }  
  109.         if(count!=vr.length)  
  110.             System.out.println("--------------有环图---------------");  
  111.           
  112.     }  
  113.       
  114.     private void tTopologicalSort(){  
  115.         int[] indegree = this.getIndegree();  
  116.         Stack<VertexNode> stack = new Stack<VertexNode>();//要拓扑序列用Queue更合适,只是  
  117.         Stack<VertexNode> saveStack = new Stack<VertexNode>();//为了后面的关键路径算法  
  118.         int count = 0;//计数器，判断是否有环  
  119.         for(int i=0;i<indegree.length;i++){  
  120.             if(indegree[i]==0){  
  121.                 stack.push(vertexNodes[i]);  
  122.                 count++;  
  123.             }  
  124.               
  125.               
  126.         }  
  127.         while(!stack.isEmpty()){  
  128.             VertexNode vertexNode = stack.pop();  
  129.             saveStack.push(vertexNode);  
  130.             ArcNode p = vertexNode.arcNode;  
  131.             while(p!=null){  
  132.                 indegree[p.serialNumber]--;  
  133.                 if(indegree[p.serialNumber]==0){  
  134.                     stack.push(vertexNodes[p.serialNumber]);  
  135.                     count++;  
  136.                 }  
  137.                   
  138.                 p = p.arcNode;  
  139.             }  
  140.         }  
  141.         if(count==vertexNodes.length){  
  142.             printSeries(saveStack);  
  143.         } else{  
  144.             System.out.println("有环图");  
  145.         }  
  146.           
  147.     }  
  148.     //邻接表求入度，入度in English 怎么说。。。。。。。。。  
  149.     private int[] getIndegree(){  
  150.         int[] indegree = new int[this.vertexNodes.length];  
  151.         for(int i=0;i<vertexNodes.length;i++){  
  152.             ArcNode p = vertexNodes[i].arcNode;  
  153.             while(p!=null){  
  154.                 indegree[p.serialNumber]++;//序号表示节点在入度数组的位置  
  155.                 p = p.arcNode;  
  156.             }  
  157.         }  
  158.         return indegree;  
  159.     }  
  160.     //递归打印正确的拓扑序列  
  161.     private void printSeries(Stack<VertexNode> s){  
  162.         if(s.isEmpty()){  
  163.             return;  
  164.         }  
  165.         VertexNode vertexNode = s.pop();  
  166.         printSeries(s);  
  167.         visit(vertexNode);  
  168.     }  
  169.     private void visit(String vertex){  
  170.         System.out.print(vertex+" ");  
  171.     }  
  172.       
  173.     private void visit(VertexNode node){  
  174.         System.out.print(node.vertex+" ");  
  175.     }  
  176.       
  177.     class VertexNode{  
  178.         String vertex;  
  179.         ArcNode arcNode;  
  180.         public VertexNode(String vertex){  
  181.             this.vertex = vertex;  
  182.         }  
  183.     }  
  184.     class ArcNode{  
  185.         int serialNumber;//存放边连着的节点在vertexNode数组里面的位置  
  186.         int weight;//权重在求最小生成树时用到，拓扑排序没有  
  187.         ArcNode arcNode;  
  188.         public ArcNode(int serialNumber,int weight){  
  189.             this.serialNumber = serialNumber;  
  190.             this.weight = weight;  
  191.         }  
  192.     }  
  193. } 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

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