LintCode 127-拓扑排序

2019-11-14 12:36:42

字体：大中小

来源：转载

供稿：网友

本人电子系，只为一学生。心喜计算机，小编以怡情。

思路： 1、用字典存储每个节点的入度 2、用队列存储入度为零的节点 3、BFS

static public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) { // write your code here //返回的值 ArrayList<DirectedGraphNode> ret=new ArrayList<>(); //队列 Queue<DirectedGraphNode> que=new LinkedList<>(); //字典 HashMap<DirectedGraphNode, Integer> dict=new HashMap<>(); //入度的计算 for(DirectedGraphNode k : graph) { if(!dict.containsKey(k)) { dict.put(k, 0); for(DirectedGraphNode m:k.neighbors) { if(!dict.containsKey(m)) dict.put(m, 1); else { dict.put(m, dict.get(m)+1); } } } else { for(DirectedGraphNode m:k.neighbors) { if(!dict.containsKey(m)) dict.put(m, 1); else { dict.put(m, dict.get(m)+1); } } } } //将所有最开始入度就为零的节点放到队列里 for(DirectedGraphNode n:dict.keySet()) { if(dict.get(n).equals(0)) { que.add(n); } } //进行主要的循环部分，实现输出 while(!que.isEmpty()) { DirectedGraphNode temp=que.poll();//将队列取出一个 ret.add(temp);//输出：放到ret返回值里 //将输出节点的下一个节点入度减一 for(DirectedGraphNode m : temp.neighbors) { dict.put(m,dict.get(m)-1); if(dict.get(m)==0)//如果减一后入度为0 que.add(m);//就放到队列中 } } //最终返回 return ret; }

上一篇：1017. Queueing at Bank 解析

下一篇：初学者的Git浅谈