/**
* 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) {
// write your code here
ArrayList<DirectedGraphNode> list = new ArrayList<DirectedGraphNode>();
HashSet<DirectedGraphNode> set = new HashSet<DirectedGraphNode>();
for(DirectedGraphNode root : graph){
if(!set.contains(root)) dfs(list, set, root);
}
// 现在的 list 是由若干个顺序倒转的 topological order list 组成的
// 这里的处理类似于 reverse words in a string
// 把每个单词单独翻转之后,再把整个句子翻转
Collections.reverse(list);
return list;
}
private void dfs(ArrayList<DirectedGraphNode> list,
HashSet<DirectedGraphNode> set,
DirectedGraphNode root){
set.add(root);
for(DirectedGraphNode node : root.neighbors){
if(!set.contains(node)) dfs(list, set, node);
}
// 到这一步,root 节点的所有 sub path 都已经被访问过了
// 最后才在 list 中添加元素,得到的是一个反序的 topological order
list.add(root);
}
}
做了欧拉回路之后,发现一个更好的做法是直接建 LinkedList,然后用 addFirst();
熟练使用 API 很重要啊~
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
// write your code here
LinkedList<DirectedGraphNode> list = new LinkedList<DirectedGraphNode>();
HashSet<DirectedGraphNode> visited = new HashSet<DirectedGraphNode>();
for(DirectedGraphNode root : graph){
dfs(list, root, visited);
}
return new ArrayList<DirectedGraphNode>(list);
}
private void dfs(LinkedList<DirectedGraphNode> list, DirectedGraphNode root, HashSet<DirectedGraphNode> visited){
if(visited.contains(root)) return;
for(DirectedGraphNode next : root.neighbors){
dfs(list, next, visited);
}
list.addFirst(root);
visited.add(root);
}