Topological Sort

本文主要是介绍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;}
}

 

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

---