拓扑排序, DFS 做法

LintCode - Topological Sort

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 （正单序列，反全序列）里面的多步翻转法。

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

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

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

/**
 * 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);
    }