题目描述

给定一个有向图，图节点的拓扑排序定义如下:

对于图中的每一条有向边 A -> B , 在拓扑排序中A一定在B之前.
拓扑排序中的第一个节点可以是图中的任何一个没有其他节点指向它的节点.
针对给定的有向图找到任意一种拓扑排序的顺序.

样例

例如以下的图:



拓扑排序可以为:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]

算法1

(bfs)

C++ 代码

/**
 * 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<DirectedGraphNode*> res;
        std::queue<DirectedGraphNode*>  q;
        unordered_map<DirectedGraphNode*,int> map;
        for(auto node:graph){
            vector<DirectedGraphNode*> neighbors=node->neighbors;
            for(auto neighbor:neighbors){
                if(map.find(neighbor)==map.end()){
                    map[neighbor]=1;
                }
                else{
                    map[neighbor]++;
                }
            }
        }
        for(auto node:graph){
            if(map.find(node)==map.end())
                q.push(node);
        }
        cout<<q.size()<<endl;
        while(!q.empty()){
            DirectedGraphNode* t=q.front();
            q.pop();
            res.push_back(t);
            vector<DirectedGraphNode*> neighbors=t->neighbors;
            for(auto neighbor:neighbors){
                map[neighbor]--;
                if(map[neighbor]==0){
                    q.push(neighbor);
                    map.erase(neighbor);
                }
            }
        }
        return res;
    }
};