引言

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边 ∈ E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

说了这么多，实际上可以用下图来直观的表示：

如果以树来表示的话，那么拓扑排序实际上就是树的后序遍历，然后反转输出，图也是一样的道理。

拓扑排序的原理可以见下面的链接
拓扑排序

对于图的遍历一般我们有bfs和dfs两种方式，同样的，对于拓扑排序，我们也可以使用dfs和bfs这两种方式来解决，下面以
210. 课程表 II这个题目为例子来说明。

dfs的拓扑排序实现

首先需要根据题目的数据构造出图的数据模型
然后对图进行后续遍历，新增一个Path用来存放后续遍历的结果
将结果反转，得到拓扑排序的结果。

class Solution {
public:
    vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto& edge : prerequisites) {
            graph[edge[1]].push_back(edge[0]);
        }
        return graph;
    }
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
        
        vector<bool> visited(numCourses);
        vector<bool> onPath(numCourses, false);
        for (int i = 0; i < numCourses; ++i) {
            tranverse(i, graph, visited, onPath);
        }

        vector<int> ret;
        if (isCycle) {
            return ret;
        }
        
        for (int i = path.size() - 1; i >= 0 ; --i) {
            ret.push_back(path[i]);
        }
        return ret;
    }
    void tranverse(int index, vector<vector<int>>& graph, vector<bool>& visited, vector<bool>& onPath) {
        if (onPath[index]) {
            isCycle = true;
        }
        if (visited[index] || isCycle) {
            return;
        }
        visited[index] = true;
        onPath[index] = true;
        for (auto item : graph[index]) {
            tranverse(item, graph, visited, onPath);
        }
        onPath[index] = false;
        path.push_back(index);
    }
private:
    bool isCycle = false;
    vector<int> path;
};

bfs的拓扑排序实现

跟图论的章节中用bfs检测环的算法一致，每次从队列汇总pop出来的节点将其输出到一个vector中，然后将其反转，即为拓扑排序的结果

class Solution {
public:
    vector<vector<int>> buildGrap(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto edge : prerequisites) {
            graph[edge[1]].push_back(edge[0]);
        }
        return graph;
    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> path;
        vector<vector<int>> graph = buildGrap(numCourses, prerequisites);
        vector<int> indegree(numCourses);
        for (auto edge : prerequisites) {
            indegree[edge[0]]++;
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        int count = 0;
        while (!q.empty()) {
            int curr = q.front();
            path.push_back(curr); // 就加了这一行
            q.pop();
            count++;
            for (auto item : graph[curr]) {
                indegree[item]--;
                if (indegree[item] == 0) {
                    q.push(item);
                }
            }
        }
        
        if (count != numCourses) {
            return vector<int> ();
        }
        return path;
    }
};