有向图（拓扑排序算法）

    　对一个 有向无环图(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 

  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      

 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      

 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      

 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      

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      

155       public   void  addVertex(  char  lab )  //  argument is label

156 

157      {

158          vertexList[nVerts ++  ]  =   new  Vertex( lab );

159      }

160 

161      

169       public   void  addEdge(  int  start,  int  end )

170      {

171          adjMat[start][end]  =   1 ;

172      }

173 

174      

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      

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