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

拓扑排序算法介绍

拓扑排序解决的是一系列相互依赖的事件的排序问题，比如Ant中有很多的Task，而某些Task依赖于另外的Task，编译之前需要清理空间，打包之前要先编译，但其它一些Task处理顺序可以调换(是无所谓前后，不是并行), 如何安排Task的执行顺序就可以用拓扑排序解决。熟悉Java的朋友应该都知道Spring，一个非常优秀的解决组件(Bean)依赖的框架，组件之间可能有依赖关系，也可能没有关系，如何按顺序创建组件也是相同的问题。本文使用的是图搜索算法里面的深度优先排序算法解决问题。需要特别指出的是拓扑排序算法的结果很可能有多个(不依赖的可以调换位置)，而算法也可以有多种，深度优先排序算法只是其中一种而已。拓扑排序为线性排序，效率为O(|V|+|E|)，其中|V|表示顶点数，|E|表示边的数量

拓扑排序算法Java实现

图像(Graph)的Java抽象实现

图可以抽象为顶点和边，分为有向图和无向图，拓扑排序里面使用的事有向图(依赖)，本文中图的边用相邻链表方法表示。每一个顶点有名字(name)，颜色(color, 搜索时候用来标记处理状态)，父节点(parent，搜索结束可以得到多棵树)，开始处理时间(discover)，结束处理时间(finish)。请注意Vertex类override了equals和hash方法。具体代码如下:

 enum Color {
		WHITE, GRAY, BLACK
	}

	static class Vertex {
		private String name;
		private Color color;
		private Vertex parent;
		private int discover;
		private int finish;

		public Vertex(String name) {
			this.name = name;
			this.color = Color.WHITE;
		}

		public String getName() {
			return name;
		}

		public void setName(String name) {
			this.name = name;
		}

		public Color getColor() {
			return color;
		}

		public void setColor(Color color) {
			this.color = color;
		}

		public Vertex getParent() {
			return parent;
		}

		public void setParent(Vertex parent) {
			this.parent = parent;
		}

		public int getDiscover() {
			return discover;
		}

		public void setDiscover(int discover) {
			this.discover = discover;
		}

		public int getFinish() {
			return finish;
		}

		public void setFinish(int finish) {
			this.finish = finish;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + ((name == null)   0 : name.hashCode());
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Vertex other = (Vertex) obj;
			if (name == null) {
				if (other.name != null)
					return false;
			} else if (!name.equals(other.name))
				return false;
			return true;
		}
	}

	static class Graph {
		private Set
  
    vertexSet = new HashSet
   
    (); // 相邻的节点 private Map
    
      adjacencys = new HashMap
     
      (); public Set
      
        getVertexSet() { return vertexSet; } public void setVertexSet(Set
       
         vertexSet) { this.vertexSet = vertexSet; } public Map
        
          getAdjacencys() { return adjacencys; } public void setAdjacencys(Map
         
           adjacencys) { this.adjacencys = adjacencys; } }

深度优先算法

遍历图的顶点，如果当前顶点还没有处理过(color为white)，就处理该节点(visitVertex)，处理节点的算法(visitVertex)也不难，时间维度加1，当前节点颜色置为gray(开始处理)，然后优先处理其子节点(深度优先)，结束之后时间维度加1，当前节点颜色置为black(结束处理)。此时就可以把该节点放到目标链表里面了(最终排好序的链表)。由于Java里面Integer值不可变(Immutable)，只能选择全局变量或者自己实现时间计数器，本文选择后者(TimeRecorder)。代码如下:

 static class TimeRecorder {
		private int time = 0;

		public int getTime() {
			return time;
		}

		public void setTime(int time) {
			this.time = time;
		}
	}

	public static Vertex[] topologicalSort(Graph graph) {
		Set
  
    vertexSet = graph.getVertexSet();
		if (vertexSet.size() < 2) {
			return vertexSet.toArray(new Vertex[0]);
		}

		LinkedList
   
     sortedList = new LinkedList
    
     (); TimeRecorder recorder = new TimeRecorder(); for (Vertex vertex : vertexSet) { if (vertex.color == Color.WHITE) { visitVertex(graph, vertex, recorder, sortedList); } } return sor

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

拓扑排序算法介绍

拓扑排序算法Java实现

图像(Graph)的Java抽象实现

深度优先算法