Given an directed graph, a topological order of the graph nodes is defined as follow:
A -> B in graph, A must before B in the order list.Find any topological order for the given graph.
For graph as follow:
The topological order can be:
[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...
You can assume that there is at least one topological order in the graph.
Can you do it in both BFS and DFS?
SOLUTION ：
拓扑排序，这题思路很简单，就是放在图里，显得有些难，首先看这是一个有向图，有向图的就是说不能从任一点开始遍历，一定要找到头，然后拓扑排序如果把它当成树，就有点像level order了，就这么理解一下这个遍历过程就行，是一层一层过去的，每一层的点到开始头的点，距离是一样的。 一看是BFS，肯定用一个queue。
用hash纪录入度的变化，最开始遍历所有的点，然后把neighbors都存下来，看每个neighbor被访问多少次。再第二次遍历所有图，找到没有在图里出现过的点，那个就是头（没有一个点的neighbor指向这个点，所以没在图里出现，所以就是头）。先把这个头加入q跟result里面。第三遍，类似level order，把queue里的点poll出来，然后看这个点的neighbor是谁，然后把图里这个点的value（就是纪录被指向次数的数字） －1，看是不是有value ＝＝ 0的情况，有就是跟这个头点最近的点，加入q，加入result，然后依次这样操作。
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) { // write your code here ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>(); HashMap<DirectedGraphNode, Integer> map = new HashMap(); for (DirectedGraphNode node : graph) { for (DirectedGraphNode neighbor : node.neighbors) { if (map.containsKey(neighbor)) { map.put(neighbor, map.get(neighbor) + 1); } else { map.put(neighbor, 1); } } } Queue<DirectedGraphNode> q = new LinkedList<DirectedGraphNode>(); for (DirectedGraphNode node : graph) { if (!map.containsKey(node)) { q.offer(node); result.add(node); } } while (!q.isEmpty()) { DirectedGraphNode node = q.poll(); for (DirectedGraphNode n : node.neighbors) { map.put(n, map.get(n) - 1); if (map.get(n) == 0) { result.add(n); q.offer(n); } } } return result; } }
[LintCode] Topological Sorting
原文：http://www.cnblogs.com/tritritri/p/4922268.html
