有向图（拓扑排序算法）

对一个 有向无环图(Directed Acyclic Graph简称 DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。     　通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称 拓扑序列。   注意：     　①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。     　②若图中存在有向环，则不可能使顶点满足拓扑次序。     　③一个DAG的拓扑序列通常表示某种方案切实可行。

下面是Java实现：

  1  package  zieckey.datastructure.study.graph;   2    3  /**   4   * 有方向图   5   *   6   *  @author  zieckey   7    */   8  public   class  DirectedGraph   9  {  10       private   final   int     MAX_VERTS     =   20 ;  11       private  Vertex[]    vertexList;         //  array of vertices  12   13       private   int [][]        adjMat;             //  adjacency matrix  14   15       private   int             nVerts;             //  current number of vertices  16   17       private   char []        sortedArray;         //  sorted vert labels  18   19   20       /**  21       * 默认构造函数 初始化邻接矩阵  22        */  23       public  DirectedGraph( )  24      {  25          vertexList  =   new  Vertex[MAX_VERTS];  26          sortedArray  =   new   char [MAX_VERTS];  27           //  图的邻接矩阵adjacency matrix  28   29          adjMat  =   new   int [MAX_VERTS][MAX_VERTS];  30          nVerts  =   0 ;  31           for  (  int  j  =   0 ; j  <  MAX_VERTS; j ++  )  32          {  33               //  set adjacency  34   35               for  (  int  k  =   0 ; k  <  MAX_VERTS; k ++  )  36              {  37                  adjMat[j][k]  =   0 ;  38              }  39          }  40      }  41        42       /**  43       * 对有向图进行拓扑排序  44       *  45       * 无后继的顶点优先拓扑排序方法  46       * 1、思想方法  47       * 该方法的每一步均是输出当前无后继(即出度为0)的顶点。  48       * 对于一个DAG，按此方法输出的序列是逆拓扑次序。  49       * 因此设置一个栈(或向量)T来保存输出的顶点序列，即可得到拓扑序列。  50       * 若T是栈，则每当输出顶点时，只需做人栈操作，排序完成时将栈中顶点依次出栈即可得拓扑序列。  51       * 若T是向量，则将输出的顶点从T[n-1]开始依次从后往前存放，即可保证T中存储的顶点是拓扑序列。  52        */  53       public   void  nonSuccFirstToplogicalSort()  54      {  55           int  orig_nVerts  =  nVerts;  56           while (nVerts > 0 )  57          {  58               int  delVertex  =  getNoSuccessorVertex();  59               if  (  - 1   ==  delVertex )  60              {  61                  System.out.println( " Error: This graph has cycles! It cannot be toplogical sorted. " );  62                   return ;  63              }  64                65              sortedArray[nVerts - 1 ]  =  vertexList[delVertex].label;  66              deleteVertex( delVertex );  67          }  68            69          System.out.print( " Topologically sorted order:  " );  70           for ( int  j = 0 ; j < orig_nVerts; j ++ )  71          {  72              System.out.print( sortedArray[j] );  73          }  74          System.out.println( "" );  75      }  76        77       /**  78       * 找到没有后继节点的节点  79       *  @return  80        */  81       public   int  getNoSuccessorVertex()  82      {  83           boolean  isEdge;  84           for  (  int  row  =   0 ; row  <  nVerts; row ++  )  85          {  86              isEdge  =   false ;  87               for  (  int  column  =   0 ; column  <  nVerts; column ++  )  88              {  89                   if  ( adjMat[row][column] > 0  ) // 大于0，表明有边指向其他点，说明有后继节点  90   91                  {      92                      isEdge  =   true ;  93                       break ;                     // OK，继续下一个节点  94   95                  }  96              }  97                98               if  (  false   ==  isEdge ) // 没有边，表明没有后继节点  99  100              { 101                   return  row; 102              } 103          } 104           return   - 1 ; 105      } 106       107       /** 108       * 删除一个节点 109       *  @param  delVertex 110        */ 111       public   void  deleteVertex(  int  delVertex ) 112      { 113           if  ( delVertex  !=  nVerts - 1  ) // 如果不是最后一个节点 114  115          { 116               // 在节点列表中删除这个节点，所有后面的节点前移一格 117  118               for  (  int  i  =  delVertex; i  <  nVerts - 1 ; i ++  ) 119              { 120                  vertexList[i]  =  vertexList[i + 1 ]; 121              } 122               123               //  删除邻接矩阵的delVertex行和列，即所有后面的行和列都向前移动一格 124  125               //  所有delVertex行后的行，向上一个格 126  127               for  (  int  row  =  delVertex; row  <  nVerts  -   1 ; row ++  ) 128              { 129                   for  (  int  column  =   0 ; column  <  nVerts; column ++  ) 130                  { 131                      adjMat[row][column]  =  adjMat[row  +   1 ][column]; 132                  } 133              } 134               135               //  所有delVertex列后的列，向左一个格 136  137               for  (  int  column  =  delVertex; column  <  nVerts; column ++  ) 138              { 139                   for  (  int  row  =   0 ; row  <  nVerts  -   1 ; row ++  )                 140                  { 141                      adjMat[row][column]  =  adjMat[row][column + 1 ]; 142                  } 143              } 144          } 145           146          nVerts -- ; // 减少一个节点 147  148      } 149       150       /** 151       * 添加一个节点 152       * 153       *  @param  lab 154        */ 155       public   void  addVertex(  char  lab )  //  argument is label 156  157      { 158          vertexList[nVerts ++  ]  =   new  Vertex( lab ); 159      } 160  161       /** 162       * 添加一条边 163       * 164       *  @param  start 165       * 起始点 166       *  @param  end 167       * 终点 168        */ 169       public   void  addEdge(  int  start,  int  end ) 170      { 171          adjMat[start][end]  =   1 ; 172      } 173  174       /** 175       * 添加一条边 176       * 177       *  @param  start 178       * 起始点 179       *  @param  end 180       * 终点 181        */ 182       public   void  addEdge(  char  startVertex,  char  endVertex ) 183      { 184           int  start  =  getIndexByLabel( startVertex ); 185           int  end  =  getIndexByLabel( endVertex ); 186           if  (  - 1   !=  start  &&   - 1   !=  end ) 187          { 188              adjMat[start][end]  =   1 ; 189          } 190      } 191       192       /** 193       * 显示一个节点 194       * 195       *  @param  v 196        */ 197       public   void  displayVertex(  int  v ) 198      { 199          System.out.print( vertexList[v].label ); 200      } 201  202       public   int  getIndexByLabel(  char  lable ) 203      { 204           for  (  int  i  =   0 ; i  <  vertexList.length; i ++  ) 205          { 206               if  ( lable  ==  vertexList[i].label ) 207              { 208                   return  i; 209              } 210          } 211  212           //  没有这个节点 213  214           return   - 1 ; 215      } 216  }

转载于:https://www.cnblogs.com/zack/archive/2009/04/21/1440167.html

相关资源：操作系统 拓扑排序算法