拓扑排序（BFS，DFS）

版权声明：本文为博主原创文章，转载请标明出处~ https://blog.****.net/Love_wanling/article/details/74275773

我们用两种方法来做这道题。

BFS

宽度优先搜索，是说我们每次把没有父亲节点的节点打印。具体操作可以是计算所有节点的入度。将入度为0的节点输出，同时将输出节点的儿子的入度减去一。我们用队列维持入度为0的节点集合。

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        vector<int> indegree(graph.size(),0);


        for(auto node:graph){
            for(int i = 0; i < node->neighbors.size(); ++i){
                indegree[node->neighbors[i]->label]++;
            }
        }

        queue<DirectedGraphNode*> que;
        for(int i = 0; i < indegree.size(); ++i){
            if(indegree[i] == 0) que.push(graph[i]);
        }
        vector<DirectedGraphNode *> res;
        while(!que.empty()){
            DirectedGraphNode *temp = que.front();
            for(auto pi:temp->neighbors){
                indegree[pi->label]--;

                if(indegree[pi->label] == 0) que.push(graph[pi->label]);
            }
            que.pop();
            res.push_back(temp);
        }
        return res;
    }
};

DFS

深度优先搜索则是一旦我们要输出一个节点，则把它的父亲全部输出即可。考虑到我们的数据结构是记录每个节点的儿子节点，所以我们这样考虑：
一旦要输出一个节点，先把儿子节点全部输出；最后reverse即可。
创建childinres布尔数组是为了查询O(1)。《—–感谢roommate

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */


    void dfs(vector<DirectedGraphNode*> &res, vector<DirectedGraphNode*>& graph, int target, vector<bool>& targetinres){
        if(targetinres[target]) return;
        //cout<<target<<endl;
        for(auto node:graph[target]->neighbors)
            dfs(res,graph,node->label,targetinres);
        res.push_back(graph[target]);
        targetinres[target] = true;
    }

    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        vector<DirectedGraphNode*> res;
        vector<bool> targetinres(graph.size(),false);
        for(int i = 0; i < graph.size(); ++i){
            dfs(res,graph,i,targetinres);
        }
        reverse(res.begin(),res.end());
        return res;
    }

};