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

javalearner

当每个任务有前后置关系时，需要找到一种满足前后置关系的路线，将任务完成。    如果将每个任务看成一个节点，任务之间的前后置关系表示为有向图时，这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。  比如有很多任务T1,T2,....
这些任务又是相互关联的，比如Tj完成前必须要求Ti已完成，这样T1,T2....序列关于这样的先决条件构成一个图，其中如果Ti必须要先于Tj完成，那么<Ti,Tj>就是该图中的一条路径，路径长度为1的就是一条边。拓扑排序就是把这些任务按照完成的先后顺序排列出来。显然，这样的顺序可能不是唯一的，比如Tk，Tl如果没有在一条路径上，那么他们之间的顺序是任意的。
   
  
   
   

     
   

     
   
  
     当从某顶点v出发的DFS搜索完成时，v的所有后继必定均已被访问过(想像它们均已被删除)，此时的v相当于是无后继的顶点，因此在DFS算法返回之前输出顶点v即可得到 DAG的逆拓扑序列。
    其中第一个输出的顶点必是无后继(出度为0)的顶点，它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列，同样可增加T来保存输出的顶点。假设T是栈。
利用DFS求拓扑序列的抽象算法可描述为：

  void DFSTopSort(G，i，T){//i是搜索的出发点，T是栈
   int j；
   visited=TRUE； //访问i
   for(所有i的邻接点j)//即<i，j>∈E(G)
     if(!visited[j])
      DFSTopSort(G，j，T)；
    Push(&T，i)； //从i出发的搜索已完成，输出i
}  看看下图的一个拓扑序列：[c1, c4, c0, c2, c3, c5, c6, c7, c8]

1. 
   
2.                                   public enum VertexState {
   
3.         UNVISITED,VISITED,PASSED;//未访问，已访问，已经过
   
4. }
   
5. import java.util.Set;
   
6. import java.util.List;
   
7. import java.util.HashSet;
   
8. import java.util.ArrayList;
   
9. import java.util.Collections;
   
10. //顶点类
    
11. class Vertex
    
12.    {
    
13.     private String label;        
    
14.     private VertexState state;//顶点状态
    
15.    public Vertex(String lab)   
    
16.       {
    
17.       label = lab;
    
18.       state = VertexState.UNVISITED;
    
19.       }
    
20. 
    
21.    public VertexState getState(){
    
22.          return state;
    
23.    }
    
24.    public void setState(VertexState state){
    
25.          this.state=state;
    
26.    }
    
27.    public String toString(){
    
28.        return label;
    
29.    }
    
30.    
    
31.    }
    
32. //有向图的邻接矩阵实现
    
33. class Graph
    
34.    {
    
35.    private final int MAX_VERTS = 30;
    
36.    private Vertex vertexList[]; // 存放顶点的数组
    
37.    private int adjMat[][];      // 邻接矩阵
    
38.    private int nVerts;          // 当前的顶点数
    
39. 
    
40.    public Graph()            
    
41.       {
    
42.       vertexList = new Vertex[MAX_VERTS];
    
43.                                          
    
44.       adjMat = new int[MAX_VERTS][MAX_VERTS];
    
45.       nVerts = 0;
    
46.       for(int y=0; y< MAX_VERTS; y++)      
    
47.          for(int x=0; x< MAX_VERTS; x++)   
    
48.             adjMat[x][y] = 0;
    
49.       
    
50.       }  
    
51.     public  void addVertex(Vertex v)//在图中添加一个顶点
    
52.       {
    
53.       vertexList[nVerts++] = v;
    
54.       }
    
55.   //在图中增加一条边,从start到end
    
56.    public void addEdge(int start, int end)
    
57.       {
    
58.       adjMat[start][end] = 1;
    
59.    
    
60.       }
    
61.        /**
    
62.          * 返回v顶点所关联的邻结点
    
63.          * @param v
    
64.          * @return
    
65.          */
    
66.    private Set< Vertex> getNeighbors(Vertex v){
    
67.                Set< Vertex> vSet = new HashSet< Vertex>();
    
68.                int index=getIndex(v);
    
69.                if(index==-1) return null;
    
70.                for(int i=0;i< nVerts;i++)
    
71.                   if(adjMat[index][i]==1)
    
72.                       vSet.add(vertexList[i]);
    
73.             
    
74.                 return vSet;
    
75.         }
    
76.       
    
77.        //返回顶点在vertexList数组中的索引
    
78.      private int getIndex(Vertex v){
    
79.           for(int i=0;i< nVerts;i++)
    
80.             if(vertexList[i]==v)
    
81.                 return i;
    
82.            return -1;
    
83.         }
    
84.       /**
    
85.          * 全部节点设为未访问
    
86.          */
    
87.     private void allUnVisted(){
    
88.                 Vertex v=null;
    
89.                 int len = nVerts;
    
90.                 for(int i = 0; i < len ; i++){
    
91.                         v = vertexList[i];
    
92.                         if(v.getState() != VertexState.UNVISITED){
    
93.                                 v.setState(VertexState.UNVISITED);
    
94.                         }
    
95.                 }
    
96.         }
    
97.     private boolean containsVertex(Vertex v){
    
98.          int index=getIndex(v);
    
99.          if(index!=-1) return true;
    
100.          else return false;
     
101.                
     
102.                
     
103.         }
     
104.     private VertexState getState(Vertex v){
     
105.                
     
106.                 return v.getState();
     
107.         }
     
108.     private VertexState setState(Vertex v, VertexState state) {
     
109.                
     
110.                 VertexState preState = v.getState();
     
111.                 v.setState(state);
     
112.                 return preState;
     
113.         }
     
114.    /**
     
115.          * 深度优先遍历一个顶点
     
116.          * @param
     
117.          * @param graph
     
118.          * @param v
     
119.          * @param checkCycle
     
120.          * @return
     
121.          */
     
122.     public List< Vertex> dfs(Vertex v,boolean checkCycle){
     
123.                 allUnVisted();
     
124.                 List< Vertex> vList = new ArrayList< Vertex>();
     
125.                 dfsHandler(v,checkCycle,vList);
     
126.                 return vList;
     
127.         }
     
128.   
     
129.       private void dfsHandler(Vertex v,boolean checkCycle,List< Vertex> vList){
     
130.                   Set< Vertex> neighbors = null;
     
131.                 if(!containsVertex(v)){
     
132.                         throw new IllegalStateException("不存在该顶点");
     
133.                 }
     
134.                 setState(v, VertexState.PASSED);
     
135.                
     
136.                 neighbors = getNeighbors(v);
     
137.                 VertexState state = null;
     
138.                 for(Vertex neighbor : neighbors){
     
139.                         state = getState(neighbor);
     
140.                         if(state == VertexState.UNVISITED){//未遍历，
     
141.                                //  System.out.println(neighbor+",");
     
142.                                 dfsHandler(neighbor, checkCycle, vList);
     
143.                         }else if(state == VertexState.PASSED && checkCycle){//
     
144.                              
     
145.                                 throw new IllegalStateException("存在一个环");
     
146.                         }
     
147.                 }
     
148.                 setState(v, VertexState.VISITED);//访问结束设为已访问
     
149.                 vList.add(v);
     
150.                // System.out.println("++"+v);
     
151.                
     
152.         }
     
153.     /**
     
154.          * 图的拓扑排序
     
155.          * @param
     
156.          * @param graph
     
157.          * @return
     
158.          */
     
159.         public List< Vertex> topo(){
     
160.                 List< Vertex> vList = new ArrayList< Vertex>();
     
161.                 allUnVisted();
     
162.                 for(int i=0;i< nVerts;i++){
     
163.                         if(getState(vertexList[i]) == VertexState.UNVISITED){
     
164.                                 try{
     
165.                                         dfsHandler(vertexList[i], true, vList);
     
166.                                 }catch (IllegalStateException e) {
     
167.                                         throw new IllegalStateException("图有一个环");
     
168.                                 }
     
169.                         }
     
170.                 }
     
171.                 Collections.reverse(vList);
     
172.                 return vList;
     
173.     }
     
174. }
     
175. public class DFSApp
     
176.    {
     
177.    public static void main(String[] args)
     
178.       {
     
179.       Graph theGraph = new Graph();
     
180.       Vertex v1=new Vertex("c0");
     
181.       Vertex v2=new Vertex("c1");
     
182.       Vertex v3=new Vertex("c2");
     
183.       Vertex v4=new Vertex("c3");
     
184.       Vertex v5=new Vertex("c4");
     
185.       Vertex v6=new Vertex("c5");
     
186.       Vertex v7=new Vertex("c6");
     
187.       Vertex v8=new Vertex("c7");
     
188.       Vertex v9=new Vertex("c8");
     
189.   
     
190.    
     
191.       theGraph.addVertex(v1);    // 0  
     
192.       theGraph.addVertex(v2);    // 1
     
193.       theGraph.addVertex(v3);    // 2
     
194.       theGraph.addVertex(v4);    // 3
     
195.       theGraph.addVertex(v5);    // 4
     
196.       theGraph.addVertex(v6);    // 5  
     
197.       theGraph.addVertex(v7);    // 6
     
198.       theGraph.addVertex(v8);    // 7
     
199.       theGraph.addVertex(v9);    // 8
     
200.       theGraph.addEdge(0, 6);     // c0->c6
     
201.       theGraph.addEdge(0, 2);     // c0->c2
     
202.       theGraph.addEdge(3, 5);     // c3->c5
     
203.       theGraph.addEdge(3, 8);     // c3->c8
     
204.       theGraph.addEdge(1, 2);     // c1->c2
     
205.       theGraph.addEdge(1, 4);     // c1->c4
     
206.       theGraph.addEdge(2, 3);     // c2->c3
     
207.       theGraph.addEdge(6, 7);     // c6->c7
     
208.       theGraph.addEdge(7, 8);     // c7->c8
     
209.       theGraph.addEdge(4, 3);     // c4->c3
     
210.       theGraph.addEdge(4, 5);     // c4->c5
     
211.       //theGraph.addEdge(3, 1);     // c4->c5
     
212.       System.out.print("Visits: ");
     
213.       List< Vertex> vl=theGraph.topo();   
     
214.        // List< Vertex> vl=theGraph.dfs(v1,false);            
     
215.       System.out.println(vl);
     
216.       }  
     
217.    }
     
218.                                   

复制代码

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/6/000719875.rar

青天下

顶顶顶顶顶顶顶顶顶顶