拓扑排序 topologicalSort

背景知识 ---- 图 （Graph）

顶点和边 (vertex and edge)

下图中的数字为图的顶点，数字之间的线为图的边

无向图 （Undirected Graph）

下图中顶点和顶点之间是没有方向性的，可以双向通行。
也就是同时存在 （1, 2) 和 (2, 1)

有向图 （Directed Graph）

下图是有方向性的，只能往箭头的方向通行
也就是只存在 (1, 2), 不存在 （2, 1)

有向图的degree

• 对于有向图，每个顶点都有一个degree，并且分为

• in-degree: number of edgs into vertex a
• out-degree: number of edges out of vertex a

• 下图中
  1: in-degree = 0, out-degree = 1
  2: in-degree = 2, out-degree = 1
  3: in-degree = 0, out-degree = 2
  4: in-degree = 2, out-degree = 0
  

图中的环

图中可以形成回路的是环
下图中 2 —> 4 ----> 3 —> 2，就形成了环

基本概念

什么是拓扑排序

• 对于一个有向无环图，将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前
• 如下图： 2 永远不可能在 1和3之前出现，4 用于不可能在1，2，3之前出现
• 拓扑排序不是传统的排序算法，一个图可能有多种拓扑排序

下图的拓扑排序是： 1，3，2，4 或者 3，1，2，4，有两种拓扑排序

拓扑排序的代码思路 — 利用广度优先搜索（BFS）

1. 统计每个点的 in-degree
2. 将每个in-degree为0的点放进队列 （Queue），作为初始值
3. 不断的从队列里拿出一个点 (pop操作), 将这个点的所有邻居的indegree减1
4. 如果发现有新的indegree为0的点，则放入队列
5. 重复3，4步，直到队列为空

Example：
Step 1: 初始化队列：
Queue: {1，3} 因为1和3的indegree为0
Output: { };

Step 2：队首元素出队放入output, 更新2的indegree为 1
Queue: {3}
Output: {1};

Step 3: 队首元素出队放入output, 更新2的indegree为 0, 同时将 2 放进 Queue
Queue: {2}
Output: {1, 3};

Step 4: 队首元素出队放入output, 更新4的indegree为 0, 同时将 4 放进 Queue
Queue: {4}
Output: {1, 3, 2};

Step 3: 队首元素出队放入output, Queue为空，结束顺换，排序完成
Queue: {}
Output: {1, 3, 2, 4};

拓扑排序的实现

/**
 * 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) {
    
        ArrayList<DirectedGraphNode> outputList = new ArrayList<DirectedGraphNode>();
        //用于储存每个点的inderee
        HashMap<DirectedGraphNode, Integer> indegree = new HashMap<>();
        //找出每个node的indegree
        for (DirectedGraphNode node: graph) {
            for (DirectedGraphNode neighbor: node.neighbors) {
                if (indegree.get(neighbor) != null) {
                    indegree.put(neighbor, indegree.get(neighbor) + 1);
                }
                else {
                    indegree.put(neighbor, 1);
                }
            }
        }
        
        //将indegree为0的点放进Queue
        List<DirectedGraphNode> queue = new ArrayList<DirectedGraphNode>();
        for (DirectedGraphNode node: graph) {
            if (indegree.get(node) == null) {
                queue.add(node);
            }
        }
        
        //BFS搜索，不断的出队列，同时更新每个点的indegree
        //如果遇到indegree为0的节点就加入队列
        while (!queue.isEmpty()) {
            DirectedGraphNode tempNode = queue.get(0);
            queue.remove(0);
            outputList.add(tempNode);
            
            for (DirectedGraphNode neighbor: tempNode.neighbors) {
                //对neighbor的indegree减1
                indegree.put(neighbor, indegree.get(neighbor)-1);
                if (indegree.get(neighbor) == 0) {
                    queue.add(neighbor);
                }
            }
        }
        
        return outputList;
    }
}

时间复杂度

拓扑排序的时间复杂度为 O(V + E) , 也就是在拓扑排序中每个点被遍历一次，每个边被遍历一次

拓扑排序的相关问题

判断是否存在拓扑排序

• 当最后被排序的顶点数量小于图中的总顶点数时，就说明图中存在环，所以没有拓扑排序
  当下图中的1 出队之后，就没有indegree为0的顶点了，所以队列为空循环结束
  此时被排序的顶点只有 1个，小于总顶点数 3
  所以不存在拓扑排序
  

判断是否仅存一个拓扑排序

• 如果队列中始终只有一个元素，则说明只存在一个拓扑排序

如何求按最小或最大顺序排列拓扑排序

• 用Heap代替Queue，就可以每次pop出最大或最小元素

Leetcode Example：

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //储存所有的点对应的进阶课程，放进hash
        Map<Integer, List<Integer>> graph = new HashMap<>(); //Key: course, value: next-level courses
        //储存所有点的indegree
        Map<Integer, Integer> indegree = new HashMap<>(); //Key: courses, Value: indegree

        //初始化两个hashtable
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new ArrayList<Integer>());
            indegree.put(i, 0);
        }

        //记录每个点的indegree和neighbors
        for (int i = 0; i < prerequisites.length; i++) {
            indegree.put(prerequisites[i][0], indegree.get(prerequisites[i][0])+ 1);
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }

        //进行拓扑排序
        List<Integer> queue = new ArrayList<>();
        int [] output = new int[numCourses];
        int totalCourse = 0;
        //找出indegree为0的course，放进queue
        for(Map.Entry<Integer, Integer> entry: indegree.entrySet()) {
           if (entry.getValue() == 0) {
               queue.add(entry.getKey());
           }
        }

        while (!queue.isEmpty()) {
           int course = queue.get(0);
           queue.remove(0);
           output[totalCourse] = course;
           totalCourse++;
           List<Integer> neighbors = graph.get(course);
           //遍历所course的所有neighbor
           for (int i = 0; i < neighbors.size(); i++) {
               int neighbor = neighbors.get(i);
               //将course的neighbor的indegree减一
               indegree.put(neighbor, indegree.get(neighbor) - 1);
               //如果有neighbor的indegree变为0，加入queue
               if (indegree.get(neighbor) == 0) {
                   queue.add(neighbor);
               }
           }
        }
        
        //如果最后排序的数量小于总数量，则说明有环的存在, 返回false
        if (totalCourse < numCourses) {
            return new int[0];
        }

        return output;
    }
}