无前趋的顶点优先的拓扑排序方法(JAVA)(转载http://128kj.iteye.com/blog/1706968)

无前趋的顶点优先的拓扑排序方法 

    该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为： 
    NonPreFirstTopSort(G){//优先输出无前趋的顶点 
      while(G中有人度为0的顶点)do{ 
       从G中选择一个人度为0的顶点v且输出之； 
       从G中删去v及其所有出边； 
       } 
      if(输出的顶点数目<|V(G)|) 
        //若此条件不成立，则表示所有顶点均已输出，排序成功。 
        Error("G中存在有向环，排序失败！")； 
     } 


Java代码  收藏代码
  1. import java.util.Arrays;     
  2. import java.util.List;     
  3. import java.util.ArrayList;     
  4. import java.util.Stack;  
  5.   
  6. public class Graph {     
  7.     
  8.     int vertexNum;   //图的顶点数  
  9.     ArrayList<ArrayList<Integer>>  table; //图的邻接表，table.get(i)存放与i邻接的顶点  
  10.     Stack<Integer> stack;  //存放入度为0的顶点   
  11.     int[] result;   //拓朴排序的结果  
  12.     int[] in;// 入度,in[i]表示顶点i的入度     
  13.     
  14.     /**   
  15.      *    
  16.      * 构造一个图   
  17.      *    
  18.      * @param num   
  19.      * 图的顶点数   
  20.      *    
  21.      */    
  22.     public Graph(int num) {     
  23.     
  24.         vertexNum = num;     
  25.         table = new ArrayList<ArrayList<Integer>> (vertexNum);     
  26.          for(int i=0;i<vertexNum;i++)  
  27.               table.add(new ArrayList<Integer>());  
  28.         stack = new Stack<Integer>();     
  29.         result = new int[vertexNum];     
  30.         in = new int[vertexNum];     
  31.     
  32.     }     
  33.     
  34.     /**   
  35.      * 向图中添加无向边   
  36.      *    
  37.      * @param I   
  38.      *         边的一个顶点   
  39.      * @param J   
  40.      *         边的另一个顶点   
  41.      * @return 是否添加成功   
  42.      */    
  43.     public boolean addEdge(int I, int J) {     
  44.     
  45.         /**   
  46.          * 判断用户输入的是否是一个顶点，如果是，则返回flase,添加不成功   
  47.          */    
  48.         if (J == I) {     
  49.             return false;     
  50.         }     
  51.     
  52.         /**   
  53.          * 判断所输入的顶点值是否在图所顶点范围值内，如果不在，则提示顶点不存在   
  54.          *    
  55.          */    
  56.         if (I < vertexNum && J < vertexNum && I >= 0 && J >= 0) {      
  57.             /**   
  58.              *    
  59.              * 判断边是否存在   
  60.              */    
  61.     
  62.             if (isEdgeExists(I, J)) {      
  63.                 return false;     
  64.             }     
  65.     
  66.             /**   
  67.              * 添加边，将孤头的入度加1   
  68.              */    
  69.     
  70.             table.get(I).add(J);     
  71.             in[J]++;     
  72.             return true;     
  73.         }     
  74.         return false;     
  75.     }     
  76.     
  77.     /**   
  78.      * 判断有向边是否存在   
  79.      *    
  80.      * @param i   
  81.      *            要查询的有向边的一个孤尾   
  82.      * @param j   
  83.      *            要查询的有向边的另一个孤头   
  84.      * @return 边是否存在，false:不存在，true:存在   
  85.      */    
  86.     
  87.     public boolean isEdgeExists(int i, int j) {     
  88.     
  89.         /**   
  90.          * 判断所输入的顶点值是否在图所顶点范围值内，如果不在，则提示顶点不存在   
  91.          *    
  92.          */    
  93.         if (i < vertexNum && j < vertexNum && i >= 0 && j >= 0) {     
  94.     
  95.             if (i == j) {     
  96.                 return false;     
  97.             }     
  98.     
  99.             /**   
  100.              * 判断i的邻接结点集是否为空   
  101.              */    
  102.     
  103.             if (table.get(i) == null) {     
  104.                return false;  
  105.             }     
  106.     
  107.             /**   
  108.              * 判断这条边是否存在，如果存在，则提示边已经存在   
  109.              */    
  110.             for (int q = 0; q < table.get(i).size(); q++) {     
  111.     
  112.                 if (((Integer) table.get(i).get(q)).intValue() == j) {     
  113.                  System.out.println("顶点" +i+"和"+"顶点"+j+ "这两点之间存在边");     
  114.                     return true;       
  115.                 }     
  116.             }     
  117.         }     
  118.         return false;     
  119.     }     
  120.     
  121.     public void TopSort() {   //无前趋的顶点优先的拓扑排序方法  
  122.     
  123.         for (int i = 0; i < vertexNum; i++)   //无前趋的顶点入栈  
  124.             if (in[i] == 0)     
  125.                 stack.push(i);     
  126.         int k = 0;     
  127.         while (!stack.isEmpty()) {  
  128.     
  129.             result[k] = (Integer) stack.pop();   //弹出一个无前趋的顶点,并放入拓扑排序的结果集  
  130.     
  131.             if (table.get(result[k]) != null) {  //这个顶点的邻接表非空   
  132.                 for (int j = 0; j < table.get(result[k]).size(); j++) {     
  133.     
  134.                     int temp = (Integer) table.get(result[k]).get(j);  
  135.                       //对result[k]每一个邻接点进行入度减1操作  
  136.                     if (--in[temp] == 0) { //如果temp的入度为0，进栈.  
  137.                         stack.push(temp);     
  138.                     }       
  139.                 }      
  140.             }     
  141.             k++;       
  142.         }     
  143.     
  144.         if (k < vertexNum) {     
  145.             System.out.println("有回路");     
  146.             System.exit(0);      
  147.         }       
  148.     }     
  149.     
  150.     public int[] getResult() {     
  151.         return result;       
  152.     }     
  153.     
  154. }    

测试： 
 

Java代码  收藏代码
  1. import java.util.List;     
  2.     
  3. public class GraphTest {     
  4.     
  5.     public static  void main(String args[]){     
  6.         Graph graph = new Graph(6);     
  7.         graph.addEdge(1, 0);     
  8.         graph.addEdge(2, 0);     
  9.         graph.addEdge(3, 0);     
  10.         graph.addEdge(1, 3);     
  11.         graph.addEdge(2, 3);     
  12.         graph.addEdge(3, 5);     
  13.         graph.addEdge(4, 2);     
  14.         graph.addEdge(4, 3);     
  15.         graph.addEdge(4, 5);     
  16.              
  17.         graph.TopSort();     
  18.         int[] list = graph.getResult();     
  19.         System.out.println("拓扑排序的结果为：");     
  20.         for(int i : list){                  
  21.             System.out.print(i+"        ");     
  22.         }     
  23.     }     
  24.          
  25. }    


运行: 
C:>java   GraphTest 
拓扑排序的结果为： 
4        2        1        3        5        0 

下载源码 
 
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/bobzhangfw/p/3296251.html