频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
拓扑排序(Topologicalsort)之Java实现
2013-12-09 15:35:39         来源:永无止境,上下求索  
收藏   我要投稿

拓扑排序算法介绍

拓扑排序解决的是一系列相互依赖的事件的排序问题,比如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 sortedList.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即可。参考链接:维基百科

点击复制链接 与好友分享!回本站首页
相关TAG标签 拓扑
上一篇:Java_io体系之Writer、Reader简介、走进源码——12
下一篇:Java项目开发中一些BUG的总结
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站