Topological sort题型总结

本文主要是介绍Topological sort题型总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

拓扑排序是对有向无环图的顶点的一种排序，

• 检测编译时的循环依赖

• 制定有依赖关系的任务的执行顺序

拓扑排序的算法是典型的宽度优先搜索算法，其大致流程如下：

1. 统计所有点的入度，并初始化拓扑序列为空。

2. 将所有入度为 0 的点，也就是那些没有任何依赖的点，放到宽度优先搜索的队列中

3. 将队列中的点一个一个的释放出来，放到拓扑序列中，每次释放出某个点 A 的时候，就访问 A 的相邻点（所有A指向的点），并把这些点的入度减去 1。

4. 如果发现某个点的入度被减去 1 之后变成了 0，则放入队列中。

5. 直到队列为空时，算法结束，

1. graph怎么构建

Graph 一般是adjecent list，

class DirectedGraphNode {

    int label;

    List<DirectedGraphNode> neighbors;

    ...

}

也可以使用 HashMap 和 HashSet 搭配的方式来存储邻接表

hashmap<Integer, List<Integer>>() 或者HashMap<Integer, HashSet<Integer>>() 来表示；

2.indegree怎么构建

array 或者hashmap<Node, Integer>

3. queue，构建拓扑排序，每次pop 入度为0的node；

首先来个经典的题目: Topological sort;

For graph as follow:

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]

思路：标准topo排序的算法；算indegree，然后每次remove node，neighbor的入度全部减1，以此循环；

/*** Definition for Directed graph.* class DirectedGraphNode {*     int label;*     ArrayList<DirectedGraphNode> neighbors;*     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }* };*/public class Solution {/** @param graph: A list of Directed graph node* @return: Any topological order for the given graph.*/public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {ArrayList<DirectedGraphNode> list = new ArrayList<DirectedGraphNode>();HashMap<DirectedGraphNode, Integer> indegree = new HashMap<DirectedGraphNode, Integer>();for(DirectedGraphNode node: graph) {// node -> neighbor, neighbor indegree + 1 ;for(DirectedGraphNode neighbor: node.neighbors) {if(indegree.containsKey(neighbor)){indegree.put(neighbor, indegree.get(neighbor) + 1);} else {indegree.put(neighbor, 1);}}}Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();for(DirectedGraphNode node: graph) {// if indegree not contains, means indegree is 0;if(!indegree.containsKey(node)){queue.offer(node);}}while(!queue.isEmpty()) {DirectedGraphNode node = queue.poll();list.add(node);for(DirectedGraphNode neighbor : node.neighbors) {indegree.put(neighbor, indegree.get(neighbor) - 1);if(indegree.get(neighbor) == 0) {queue.offer(neighbor);}}}return list;}
}

Course Schedule

[1,0] 代表的物理意义是：0 --> 1 

思路：用hashmap build adjecent list，然后记录indegree，neighbor indegree相互减1.  return count == numCourses.

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {if(prerequisites == null || numCourses < 0) {return false;}int[] indegree = new int[numCourses];HashMap<Integer, List<Integer>> graph = new HashMap<>();for(int i = 0; i < numCourses; i++) {graph.putIfAbsent(i, new ArrayList<>());}for(int[] prerequist : prerequisites) {int course = prerequist[0];int pcourse = prerequist[1];// pcourse -> course;graph.get(pcourse).add(course);indegree[course]++;}Queue<Integer> queue = new LinkedList<>();for(int i = 0; i < numCourses; i++) {if(indegree[i] == 0) {queue.offer(i);}}int count = 0;while(!queue.isEmpty()) {Integer node = queue.poll();count++;for(Integer neighbor: graph.get(node)) {indegree[neighbor]--;if(indegree[neighbor] == 0) {queue.offer(neighbor);}}}return count == numCourses;}
}

Alien Dictionary 思路：从单词之间的关系来得到图的关系， 注意所有的char都是一个node，都是字母；然后用hashmap<Character, HashSet<Character>>来建立图。注意分函数写程序，这样清晰；注意indegree需要把每个node全部赋值为0；然后再进行+1；

class Solution {public String alienOrder(String[] words) {if(words == null || words.length == 0) {return "";}HashMap<Character, HashSet<Character>> graph = new HashMap<>();// 每个character，都得在graph里面建立一个node；for(String word: words) {for(int i = 0; i < word.length(); i++) {graph.putIfAbsent(word.charAt(i), new HashSet<Character>());}}for(int i = 0; i < words.length - 1; i++) {String worda = words[i];String wordb = words[i + 1];int minlen = Math.min(worda.length(), wordb.length());for(int j = 0; j < minlen; j++) {char ac = worda.charAt(j);char bc = wordb.charAt(j);graph.putIfAbsent(ac, new HashSet<Character>());graph.putIfAbsent(bc, new HashSet<Character>());// ac -> bc;if(ac != bc) {graph.get(ac).add(bc);break;}}// 特殊情况return abc -> ab, return "";if(worda.length() > wordb.length() && worda.substring(0, minlen).equals(wordb.substring(0, minlen))) {return "";}}HashMap<Character, Integer> indegree = new HashMap<>();buildIndegree(indegree, graph);Queue<Character> queue = new LinkedList<Character>();StringBuilder sb = new StringBuilder();for(Character node: indegree.keySet()) {if(indegree.get(node) == 0) {queue.offer(node);}}while(!queue.isEmpty()) {Character node = queue.poll();sb.append(node);for(Character neighbor: graph.get(node)) {indegree.put(neighbor, indegree.get(neighbor) - 1);if(indegree.get(neighbor) == 0) {queue.offer(neighbor);}}}return sb.length() == indegree.keySet().size() ? sb.toString() : "";}private void buildIndegree(HashMap<Character, Integer> indegree,HashMap<Character, HashSet<Character>> graph) {// graph的每个node，indegree初始为0；for(Character node: graph.keySet()) {indegree.putIfAbsent(node, 0);}for(Character node: graph.keySet()) {for(Character neighbor: graph.get(node)) {indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1);}}}
}

这篇关于Topological sort题型总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---