Go语言视频零基础入门到精通

javalearner

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

【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。
④一个DAG可能有多个拓扑序列。
【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C6，C7，C1，C4，C2，C3，C8，C5。
   
  
   
   
     
   

     
   
  


⑤当有向图中存在有向环时，拓扑序列不存在

无后继的顶点优先拓扑排序方法

1、思想方法
该方法的每一步均是输出当前无后继(即出度为0)的顶点。对于一个DAG，按此方法输出的序列是逆拓扑次序。因此设置一个栈(或向量)T来保存输出的顶点序列，即可得到拓扑序列。若T是栈，则每当输出顶点时，只需做人栈操作，排序完成时将栈中顶点依次出栈即可得拓扑序列。若T是向量，则将输出的顶点从T[n-1]开始依次从后往前存放，即可保证T中存储的顶点是拓扑序列。

2、抽象算法描述
算法的抽象描述为：
NonSuccFirstTopSort(G){//优先输出无后继的顶点
   while(G中有出度为0的顶点)do {
     从G中选一出度为0的顶点v且输出v；
    从G中删去v及v的所有人边
  }
   if(输出的顶点数目<|V(G)|)
   Error("G中存在有向环，排序失败!")；
}

代码：

1. //有向无环图的拓扑排序：
   
2. //第一步：在图中找到一个没有后继的顶点；
   
3. //第二步：从图中删除这个顶点，在列表的前面插入顶点的标记
   
4. //第三步：重复第一和第二步，直到所有顶点都从图中删除。这时列表显示的顶点顺序就是拓扑排序的结果。
   
5. class Vertex {
   
6.    public char label;      
   
7.    public Vertex(char lab)  
   
8.       { label = lab; }
   
9.    }  
   
10. class Graph{
    
11.    private final int MAX_VERTS = 20;
    
12.    private Vertex vertexList[]; //顶点列表
    
13.    private int adjMat[][];     //邻接矩阵
    
14.    private int nVerts;          // 当前的顶点数
    
15.    private char sortedArray[];// 已经排序的顶点
    
16. Graph() {
    
17.       vertexList = new Vertex[MAX_VERTS];
    
18.                                        
    
19.       adjMat = new int[MAX_VERTS][MAX_VERTS];
    
20.       nVerts = 0;
    
21.       for(int j=0; j< MAX_VERTS; j++)     
    
22.          for(int k=0; k< MAX_VERTS; k++)
    
23.             adjMat[j][k] = 0;
    
24.       sortedArray = new char[MAX_VERTS];  
    
25.       }  
    
26.    public void addVertex(char lab)//在图中增加一个顶点
    
27.       {
    
28.       vertexList[nVerts++] = new Vertex(lab);
    
29.       }
    
30.    public void addEdge(int start, int end)//在图中增加一条边
    
31.       {
    
32.       adjMat[start][end] = 1;
    
33.       }
    
34.    public void displayVertex(int v)
    
35.       {
    
36.       System.out.print(vertexList[v].label);
    
37.       }
    
38.    public void topo(){
    
39.       int orig_nVerts = nVerts;  
    
40.       while(nVerts > 0){
    
41.         
    
42.          int currentVertex = noSuccessors();//找一个没有后继的顶点（出度为0）
    
43.          
    
44.          if(currentVertex == -1){      // 没有找到，一定是一个环
    
45.             System.out.println("ERROR: Graph has cycles");
    
46.             return;
    
47.          }
    
48.          // 找到了，插入
    
49.          sortedArray[nVerts-1] = vertexList[currentVertex].label;
    
50.          deleteVertex(currentVertex);  // 删除顶点
    
51.       }  
    
52.       // 显示拓扑排序的结果
    
53.       System.out.print("Topologically sorted order: ");
    
54.       for(int j=0; j< orig_nVerts; j++)
    
55.          System.out.print( sortedArray[j] );
    
56.       System.out.println("");
    
57.       }  
    
58.    public int noSuccessors(){ // 从邻接矩阵中找一个没有后继的顶点（出度为0的)                  
    
59.       boolean isEdge;  
    
60.       for(int row=0; row< nVerts; row++){
    
61.          isEdge = false;                 
    
62.          for(int col=0; col< nVerts; col++){
    
63.             if( adjMat[row][col] > 0 ){                        
    
64.                isEdge = true;
    
65.                break;                  
    
66.                }                     
    
67.          }                        
    
68.          if( !isEdge )   
    
69.             return row;   
    
70.       }
    
71.       return -1;      
    
72.    }  
    
73.    //删除一个顶点。顶点从vertexList[]数组删除，后面的顶点向前移动填补空位，同样的，顶点所在的行列
    
74.   //从邻接矩阵中删除，下面的行的右面的列移动来填补空位。
    
75.    public void deleteVertex(int delVert){
    
76.       if(delVert != nVerts-1) {// 如果不是最后一个顶点
    
77.          for(int j=delVert; j< nVerts-1; j++)
    
78.             vertexList[j] = vertexList[j+1];
    
79.          // 在邻接矩阵中删除一行
    
80.          for(int row=delVert; row< nVerts-1; row++)
    
81.             moveRowUp(row, nVerts);
    
82.          // 在邻接矩阵中删除一列
    
83.         for(int col=delVert; col< nVerts-1; col++)
    
84.             moveColLeft(col, nVerts-1);
    
85.       }
    
86.       nVerts--;                  
    
87.    }
    
88.    private void moveRowUp(int row, int length){
    
89.       for(int col=0; col< length; col++)
    
90.          adjMat[row][col] = adjMat[row+1][col];
    
91.       }
    
92.    private void moveColLeft(int col, int length){
    
93.       for(int row=0; row< length; row++)
    
94.          adjMat[row][col] = adjMat[row][col+1];
    
95.       }
    
96.    }  
    
97. public class TopoApp {
    
98.    public static void main(String[] args){
    
99.       Graph theGraph = new Graph();
    
100.       theGraph.addVertex("0");   
     
101.       theGraph.addVertex("1");   
     
102.       theGraph.addVertex("2");   
     
103.       theGraph.addVertex("3");   
     
104.       theGraph.addVertex("4");   
     
105.       theGraph.addVertex("5");   
     
106.       theGraph.addVertex("6");   
     
107.       theGraph.addVertex("7");   
     
108.       theGraph.addVertex("8");   
     
109.       theGraph.addEdge(0, 6);   
     
110.       theGraph.addEdge(0, 2);   
     
111.       theGraph.addEdge(6, 7);     
     
112.       theGraph.addEdge(7, 8);     
     
113.       theGraph.addEdge(2, 3);     
     
114.       theGraph.addEdge(1, 2);     
     
115.       theGraph.addEdge(1, 4);   
     
116.       theGraph.addEdge(4, 5);  
     
117.       theGraph.addEdge(4, 3);   
     
118.       theGraph.addEdge(3, 5);
     
119.       theGraph.addEdge(3, 8);               
     
120.    
     
121.       theGraph.topo();            // do the sort
     
122.       }  
     
123.    }  
     

复制代码

运行结果：
C:        est>java TopoApp
Topologically sorted order: 067142385


  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/7/000708140.zip