通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

拓扑排序获取所有可能序列JAVA实现

3976人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法

作者:因情语写

链接:https://www.qingyu.blue/article/93

声明:请尊重原作者的劳动,如需转载请注明出处


    在看算法基础这本书,看到有向无环图,其中介绍到了拓扑排序,讲到了获取拓扑序列的方法,结合自己的理解,用JAVA代码实现了获取所有可能序列,水平有限,效率什么的就没有考虑,下面贴上代码:

package graphics.dag.topologicalsort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 有向无环图所有的走法
 * @author zhangxinren
 *
 */
public class TopologicalSortAll {
	// 所有的走法
	private static List<List<Integer>> result = new ArrayList<>();
	// 顶点和边的邻接表
	private static int[][] edges = {//14个顶点,索引0不用,邻接表
					{},
					{3},
					{4},
					{4,5},
					{6},
					{6},
					{7,11},
					{8},
					{13},
					{10},
					{11},
					{12},
					{13},
					{14},
					{}
				 };
	// 每条边的入度
	private static int[] inDegree;//邻接表元素个变化,inDegree初始长度也变化
	// 当前可以走的边(入度为0的边)
	private static List<Integer> next = new ArrayList<>();;
	
	public static void topologicalSort(List<Integer> oneResult, int[] inDegree, List<Integer> next){
		if(next.size() > 0){
			for(int i = 0; i < next.size(); i++){
				List<Integer> tempNext = new ArrayList<>(next);
				List<Integer> tempOneResult = new ArrayList<>(oneResult);
				tempNext.remove(next.get(i));
				tempOneResult.add(next.get(i));
				
				int[] tempInDegree = Arrays.copyOf(inDegree, inDegree.length);
				int[] tempEdges = edges[next.get(i)];
				for(int j = 0; j < tempEdges.length; j++){
					tempInDegree[tempEdges[j]]--;
					if(tempInDegree[tempEdges[j]] == 0){
						tempNext.add(tempEdges[j]);
					}
				}
				
				topologicalSort(tempOneResult, tempInDegree, tempNext);
			}
		}
		else
		{
			result.add(oneResult);
		}
	}
	
	public static void main(String[] args) {
		// 索引0不用
		inDegree = new int[15];
		
		for(int i = 0; i < inDegree.length; i++){
			inDegree[i] = 0;
		}
		
		for(int i = 1; i < edges.length; i++){
			for(int j = 0; j < edges[i].length; j++){
				inDegree[edges[i][j]]++;
			}
		}
		
		
		for(int i = 1; i < inDegree.length; i++){
			if(inDegree[i] == 0){
				next.add(i);
			}
		}
		
		topologicalSort(new ArrayList<>(), inDegree, next);
		
		for(int i = 0; i < result.size(); i++){
			for(int j = 0; j < result.get(i).size(); j++){
				System.out.print(result.get(i).get(j) + " ");
			}
			System.out.println();
		}
	}
}

    经过测试,没有发现问题,供大家参考,代码写得不好的地方还请包涵,如有不理解的地方请结合拓扑排序的相关知识加以理解。

    结果如下:


自己写的文章声明标题示例:


点赞(0) 打赏

全部评论

还没有评论!