拓扑排序(Topologicalsort)之Java实现 - JAVA

tedList.toArray(new Vertex[0]); } /** * 深度优先搜索(Depth First Search) */ public static void visitVertex(Graph graph, Vertex vertex, TimeRecorder recorder, LinkedList sortedList) { recorder.time += 1; vertex.color = Color.GRAY; vertex.discover = recorder.time; Map edgeMap = graph.getAdjacencys(); Vertex[] adjacencys = edgeMap.get(vertex); if (adjacencys != null && adjacencys.length > 0) { for (Vertex adjacency : adjacencys) { if (adjacency.color == Color.WHITE) { adjacency.parent = vertex; visitVertex(graph, adjacency, recorder, sortedList); } } } recorder.time += 1; vertex.color = Color.BLACK; vertex.finish = recorder.time; sortedList.addLast(vertex); }

构建图以及测试

我们的测试图例如下(箭头的方向表示的是依赖):

为了打印排好序的结果，实现了printVertex函数。测试代码如下:

public static void main(String[] args) {
		Graph graph = new Graph();
		Set
  
    vertexSet = graph.getVertexSet();
		Map
   
     edgeMap = graph.getAdjacencys(); Vertex twoVertex = new Vertex("2"); Vertex threeVertex = new Vertex("3"); Vertex fiveVertex = new Vertex("5"); Vertex sevenVertex = new Vertex("7"); Vertex eightVertex = new Vertex("8"); Vertex nineVertex = new Vertex("9"); Vertex tenVertex = new Vertex("10"); Vertex elevenVertex = new Vertex("11"); vertexSet.add(twoVertex); vertexSet.add(threeVertex); vertexSet.add(fiveVertex); vertexSet.add(sevenVertex); vertexSet.add(eightVertex); vertexSet.add(nineVertex); vertexSet.add(tenVertex); vertexSet.add(elevenVertex); edgeMap.put(twoVertex, new Vertex[] { elevenVertex }); edgeMap.put(nineVertex, new Vertex[] { elevenVertex, eightVertex }); edgeMap.put(tenVertex, new Vertex[] { elevenVertex, threeVertex }); edgeMap.put(elevenVertex, new Vertex[] { sevenVertex, fiveVertex }); edgeMap.put(eightVertex, new Vertex[] { sevenVertex, threeVertex }); Vertex[] sortedVertexs = topologicalSort(graph); printVertex(sortedVertexs); } public static void printVertex(Vertex[] Vertexs) { for (Vertex vertex : Vertexs) { System.out.println(vertex.getName() + " discover time:" + vertex.getDiscover() + " finish time:" + vertex.getFinish()); } }

后记

以上Java实现参考的是算法导论的深度优先排序算法。如果想对排序的精确度有更好的控制，可以在Vertex类中加一个priority属性。每一次遍历之前都针对顶点以priority即可。参考链接:维基百科

拓扑排序(Topologicalsort)之Java实现(二)

构建图以及测试

后记