基于java的图(三) 图的拓扑排序

相关：

基于java的图的实现

 

基于java的图的实现(二) 图的两种遍历

 

 

方法一:

(1)在又向图中选一个没有前驱的点点输出。

(2)从图中删除该顶点和所有以它为尾的弧。

重复以上步骤，直至全部顶点均一输出，或者当前图中不存在五前驱的顶点为止。拓扑排序要求图示无环图后一种情况 说明该图存在环。

再实现中，我们可以用一个队列存入所有入度为0的顶点。然后依次删除这些顶点，和其对应的边，如果对应边删除后其终点的入度减为0者也将其存入队列中，如此循环下去，知道队列为空。最后比列表中的节点数是否等于图的顶点数，如果不等者图存在一个环。

基于以上的规则可以用下面的代码来实现图的拓扑排序。

 

/**
	 * 图的拓扑排序2，该方法会改变图的结构
	 * @param <T>
	 * @return
	 */
	public static<T> List<T> topologicalSort2(Graph<T> graph){
		Queue<T> vQueue = new LinkedList<T>();
		List<T> vList = new ArrayList<T>();
		Set<T> vSet = graph.vertexSet();
		Set<T> neighbors = null;
		T vertex = null;
		//将入度为0的节点存入队列中
		for(T v : vSet){
			if(graph.getIndegree(v) == 0){
				vQueue.add(v);
				vList.add(v);
			}
		}
		while(!vQueue.isEmpty()){
			vertex = vQueue.poll();
			neighbors = graph.getNeighbors(vertex);
			for(T neighbor : neighbors){
				graph.removeEdge(vertex, neighbor);//删除该边
				if(graph.getIndegree(neighbor) == 0){//若neighbor的入度变为0，者也将其加入队列中
					vQueue.add(neighbor);
					vList.add(neighbor);
				}
			}
		}
		if(vList.size() != graph.numberOfVertices()){
			throw new IllegalStateException("存在环");
		}
		return vList;
	}

 

 方法二:

可以证明在被路径p(v,w)连接的任意顶点所在的图中，对于v和w来说，v在列表中必须出现在w之前。

依据这个结论可以对图的每个节点进行一个dfs的遍历，最终的节点列表就是拓扑排序的一个结果(要对这个列表反转).

 

 

/**
	 * 图的拓扑排序
	 * @param <T>
	 * @param graph
	 * @return
	 */
	public static<T> List<T> topologicalSort(Graph<T> graph){
		List<T> vList = new ArrayList<T>();
		graph.allUnVisted();
		for(T v : graph.vertexSet()){
			if(graph.getState(v) == VertexState.UNVISITED){
				try{
					dfsHandler(graph, v, true, vList);
				}catch (IllegalStateException e) {
					throw new IllegalStateException("图有一个环");
				}
			}
		}
		Collections.reverse(vList);
		return vList;
		
		
	}

 

 测试：

针对下面这个图进行测试

 /**

	 * 测试图的拓扑排序
	 */
	public void testTopologicalSort(){
		List<String> vList = GraphUtil.topologicalSort(graph);
		System.out.println(Arrays.toString(vList.toArray()));
		
		vList = GraphUtil.topologicalSort2(graph);
		System.out.println(Arrays.toString(vList.toArray()));
	}

 Output:

[c2, c5, c1, c3, c7, c6, c4, c8]

[c1, c2, c3, c5, c4, c6, c7, c8]