拓扑排序 DFS 做法

LintCode - Topological Sort

拓扑排序DFS的本质是搜索到最深节点, 此节点是dependency最多的节点. 加入list头部. DFS返回到当前节点的时候, 证明此节点所有孩子都已加入, 当前节点是dependency最多的点, 加入list头部. dependency为0的点最后加入.

CLRS 上图论的一小节。给定一个有向图，在拓扑排序中可以有很多个正确解，由若干小段的 list 组成。但是要保证：

正确的单序列顺序（具体一个 list 之间的元素）

正确的全序列顺序（所有的 lists 之间）

以下图为例，不论先从哪个点开始 DFS，例如 dfs(belt)会得到一个 belt -> jacket 的 list; 但同时因为 pants -> belt，在最终的结果中，包含 pants 的 list 要排在包含 belt 的 list 前面。

CLRS 上的算法是，每次 DFS 得到一个符合正确拓扑顺序的 list，保证单序列顺序；每次新的 DFS 之后得到的 list 要排在之前结果的前面，保证全序列顺序。

我的写法是，每次 DFS 得到一个相反顺序的 list； 新的 DFS 返回 list 排在之前结果的后面； 最后把整个 list 翻转，思路类似于 类似于reverse words in string（正单序列，反全序列），或者Rotate Array（正单序列，反全序列）里面的多步翻转法。

每次翻转都会改变单序列 & 全序列之间的顺序，对于每一个单序列或者全序列，两次翻转可以互相抵消。

这个思路体现在多步翻转法上就是依次翻转每个单序列，最后全部翻转，因而单序列顺序不变，全序列顺序翻转。

而我这题一开始就是“反单序列” 和 “反全序列”，因此一次完全翻转之后就可以得到“正单序列” 和 “正全序列”。

做了欧拉回路之后，发现一个更好的做法是直接建 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 node : graph){
            if(!visited.contains(node)){
                dfs(node, visited, list);
            }
        }
        return new ArrayList<DirectedGraphNode>(list);
    }

    public void dfs(DirectedGraphNode node, HashSet<DirectedGraphNode> visited,  LinkedList<DirectedGraphNode> list){

        visited.add(node);

        for(DirectedGraphNode n : node.neighbors){
            if(!visited.contains(n))
                dfs(n, visited, list);
        }

        list.addFirst(node);
    }