深度优先搜索与有向无环图的拓扑排序(java实现）
当每个任务有前后置关系时，需要找到一种满足前后置关系的路线，将任务完成。
如果将每个任务看成一个节点，任务之间的前后置关系表示为有向图时，这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。
比如有很多任务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[i]=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]
public enum VertexState {UNVISITED,VISITED,PASSED;//未访问，已访问，已经过}import java.util.Set;import java.util.List;import java.util.HashSet;import java.util.ArrayList;import java.util.Collections;//顶点类class Vertex { private String label; private VertexState state;//顶点状态 public Vertex(String lab) { label = lab; state = VertexState.UNVISITED; } public VertexState getState(){ return state; } public void setState(VertexState state){ this.state=state; } public String toString(){ return label; } } //有向图的邻接矩阵实现class Graph { private final int MAX_VERTS = 30; private Vertex vertexList[]; // 存放顶点的数组 private int adjMat[][]; // 邻接矩阵 private int nVerts; // 当前的顶点数 public Graph() { vertexList = new Vertex[MAX_VERTS]; adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for(int y=0; y<MAX_VERTS; y++) for(int x=0; x<MAX_VERTS; x++) adjMat[x][y] = 0; } public void addVertex(Vertex v)//在图中添加一个顶点 { vertexList[nVerts++] = v; } //在图中增加一条边,从start到end public void addEdge(int start, int end) { adjMat[start][end] = 1; } /** * 返回v顶点所关联的邻结点 * @param v * @return */ private Set<Vertex> getNeighbors(Vertex v){ Set<Vertex> vSet = new HashSet<Vertex>(); int index=getIndex(v); if(index==-1) return null; for(int i=0;i<nVerts;i++) if(adjMat[index][i]==1) vSet.add(vertexList[i]); return vSet;} //返回顶点在vertexList数组中的索引 private int getIndex(Vertex v){ for(int i=0;i<nVerts;i++) if(vertexList[i]==v) return i; return -1; } /** * 全部节点设为未访问 */ private void allUnVisted(){Vertex v=null;int len = nVerts; for(int i = 0; i < len ; i++){v = vertexList[i];if(v.getState() != VertexState.UNVISITED){v.setState(VertexState.UNVISITED);} } } private boolean containsVertex(Vertex v){ int index=getIndex(v); if(index!=-1) return true; else return false; } private VertexState getState(Vertex v){return v.getState();} private VertexState setState(Vertex v, VertexState state) {VertexState preState = v.getState();v.setState(state);return preState;} /** * 深度优先遍历一个顶点 * @param * @param graph * @param v * @param checkCycle * @return */ public List<Vertex> dfs(Vertex v,boolean checkCycle){allUnVisted();List<Vertex> vList = new ArrayList<Vertex>();dfsHandler(v,checkCycle,vList);return vList;} private void dfsHandler(Vertex v,boolean checkCycle,List<Vertex> vList){ Set<Vertex> neighbors = null;if(!containsVertex(v)){ throw new IllegalStateException("不存在该顶点");}setState(v, VertexState.PASSED);neighbors = getNeighbors(v);VertexState state = null;for(Vertex neighbor : neighbors){ state = getState(neighbor); if(state == VertexState.UNVISITED){//未遍历， // System.out.println(neighbor+","); dfsHandler(neighbor, checkCycle, vList);}else if(state == VertexState.PASSED && checkCycle){// throw new IllegalStateException("存在一个环");}}setState(v, VertexState.VISITED);//访问结束设为已访问vList.add(v); // System.out.println("++"+v); } /** * 图的拓扑排序 */public List<Vertex> topo(){ List<Vertex> vList = new ArrayList<Vertex>(); allUnVisted(); for(int i=0;i<nVerts;i++){ if(getState(vertexList[i]) == VertexState.UNVISITED){try{ dfsHandler(vertexList[i], true, vList);}catch (IllegalStateException e) { throw new IllegalStateException("图有一个环");} } }Collections.reverse(vList);return vList; }}public class DFSApp { public static void main(String[] args) { Graph theGraph = new Graph(); Vertex v1=new Vertex("c0"); Vertex v2=new Vertex("c1"); Vertex v3=new Vertex("c2"); Vertex v4=new Vertex("c3"); Vertex v5=new Vertex("c4"); Vertex v6=new Vertex("c5"); Vertex v7=new Vertex("c6"); Vertex v8=new Vertex("c7"); Vertex v9=new Vertex("c8"); theGraph.addVertex(v1); // 0 theGraph.addVertex(v2); // 1 theGraph.addVertex(v3); // 2 theGraph.addVertex(v4); // 3 theGraph.addVertex(v5); // 4 theGraph.addVertex(v6); // 5 theGraph.addVertex(v7); // 6 theGraph.addVertex(v8); // 7 theGraph.addVertex(v9); // 8 theGraph.addEdge(0, 6); // c0->c6 theGraph.addEdge(0, 2); // c0->c2 theGraph.addEdge(3, 5); // c3->c5 theGraph.addEdge(3, 8); // c3->c8 theGraph.addEdge(1, 2); // c1->c2 theGraph.addEdge(1, 4); // c1->c4 theGraph.addEdge(2, 3); // c2->c3 theGraph.addEdge(6, 7); // c6->c7 theGraph.addEdge(7, 8); // c7->c8 theGraph.addEdge(4, 3); // c4->c3 theGraph.addEdge(4, 5); // c4->c5 //theGraph.addEdge(3, 1); // c3->c1 System.out.print("Visits: "); List<Vertex> vl=theGraph.topo(); // List<Vertex> vl=theGraph.dfs(v1,false); System.out.println(vl); } }