拓扑排序

相关题目：剑指 Offer II 114. 外星文字典、802. 找到最终的安全状态。

拓扑排序只能在有向无环图（DAG, Directed Acyclic Graph）中得到正确的结果（在有环图中可以运行拓扑排序，不会报 BUG，但是结果不正确：完成排序的节点个数和总的结点个数不相等），所以，拓扑排序也可以用来检测一个有向图是不是带环。

拓扑排序的结果不是唯一的。这取决于将入度为 0 的节点插入队列的顺序。队列出队顺序为拓扑排序顺序。

与拓扑排序相关的两个概念：

• 入度（indegree）：有多少条边直接指向该节点；

• 出度（outdegree）：由该节点指出的边有多少条。

拓扑排序的基本过程：

1. 起始时，将所有入度为 0 的结点入队。
2. 对队列进行出队操作，出队顺序就是拓扑排序的顺序。对于当前出队元素 v，遍历图中所有和其直接相连接的结点 w，并将 w 的入度减 1。
3. 如果对 w 的入度减 1 后，w 的入度为 0，则将 w 入队。
4. 重复执行步骤 2、3，直至队列为空。

拓扑排序思想很好理解，代码也不难。在我看来难点在于，能够识别出一个问题可以用图建模，并正确的进行建模。

class Solution {
    private boolean[][] grap;
    private int[] indegress;
    private Set<Character> exits;
    
    public String alienOrder(String[] words) {
        grap = new boolean[26][26];
        indegress = new int[26];
        exits = new HashSet<>();
        int n = words.length;
        
        for (int i = 0; i < n; ++i) {
            for (char c : words[i].toCharArray()) exits.add(c);
        }
        
        for (int i = 0; i < n - 1; ++i) {
            int j = i + 1;
            
            char[] w1 = words[i].toCharArray();
            char[] w2 = words[j].toCharArray();
            int idx = 0;
            
            while (idx < w1.length && idx < w2.length && w1[idx] == w2[idx]) idx++;
            if (idx < w1.length && idx == w2.length) return "";
            if (idx < w1.length && idx < w2.length) {
                char from = w1[idx], to = w2[idx];
                
                indegress[to - 'a'] += grap[from - 'a'][to - 'a'] ? 0 : 1;
                grap[from - 'a'][to - 'a'] = true;
            }
        }
        
        return topoSort();
    }
    
    private String topoSort() {
        Queue<Integer> queue = new LinkedList<>();
        int cnt = exits.size();
        StringBuilder ret = new StringBuilder();
        
        for (int i = 0; i < 26; ++i) {
            if (exits.contains((char)(i + 'a')) && indegress[i] == 0)
                queue.offer(i);
        }
        
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            
            ret.append((char)(cur + 'a'));
            
            for (int j = 0; j < 26; ++j) {
                if (grap[cur][j]) {
                    grap[cur][j] = false;
                    
                    if (--indegress[j] == 0) queue.offer(j);
                }
            }
        }
        
        return cnt == ret.length() ? ret.toString() : "";
    }
}