拓撲排序的意思：

　　對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。

　　一個較大的工程往往被劃分成許多子工程，我們把這些子工程稱作活動(activity)。在整個工程中，有些子工程(活動)必須在其它有關子工程完成之後才能開始，也就是説，一個子工程的開始是以它的所有前序子工程的結束為先決條件的，但有些子工程沒有先決條件，可以安排在任何時間開始。為了形象地反映出整個工程中各個子工程(活動)之間的先後關係，可用一個有向圖來表示，圖中的頂點代表活動(子工程)，圖中的有向邊代表活動的先後關係，即有向邊的起點的活動是終點活動的前序活動，只有當起點活動完成之後，其終點活動才能進行。通常，我們把這種頂點表示活動、邊表示活動間先後關係的有向圖稱做頂點活動網(Activity On Vertex network)，簡稱AOV網。　

　　在AOV網中，若不存在迴路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅活動都排在該活動的前面，我們把此序列叫做拓撲序列(Topological order)，由AOV網構造拓撲序列的過程叫做拓撲排序(Topological sort)。AOV網的拓撲序列不是唯一的，滿足上述定義的任一線性序列都稱作它的拓撲序列。

由AOV網構造出拓撲序列的實際意義是：如果按照拓撲序列中的頂點次序，在開始每一項活動時，能夠保證它的所有前驅活動都已完成，從而使整個工程順序進行，不會出現衝突的情況。

 

拓撲排序的步驟：　

　　由AOV網構造拓撲序列的拓撲排序算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止。

　　　　(1) 選擇一個入度為0的頂點並輸出之；

　　　　(2) 從網中刪除此頂點及所有出邊。

　　循環結束後，若輸出的頂點數小於網中的頂點數，則輸出“有迴路”信息，否則輸出的頂點序列就是一種拓撲序列

 

拓撲排序排序：

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
 
//使用bfs進行拓撲排序：
//1、統計各個節點的入度信息，
//2、查找入度為0的點放入隊列和返回的vector中初始化bfs的隊列
//3、進行bfs，將從隊列中彈出的元素的neighbors的入度減1然後判斷該節點入度是否為0.為0
//   則加入隊列同時加入返回vector中（這一步的主要框架就是bfs的程序框架）
class Solution {
public:

    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        //1、得到所有節點的入度信息
        map<DirectedGraphNode*, int> indegree = getIndegree(graph);
        
        //2、將入度為0的放入隊列
        
        return addQueue(indegree, graph);
        
    }
    
    map<DirectedGraphNode*, int> getIndegree(vector<DirectedGraphNode*> graph){
        int size = graph.size();
        map<DirectedGraphNode*, int> res;
        if(size == 0){
            return res;
        }
        
        for(int i = 0; i < size; i++){
            DirectedGraphNode* temp = graph[i];
             if(res.find(temp) == res.end()){
                    res[temp] = 0;
             }
            int nbSize = temp->neighbors.size();
            for(int i = 0; i < nbSize; i++){
                DirectedGraphNode* nbNode = temp->neighbors[i];
                if(res.find(nbNode) == res.end()){
                    res[nbNode] = 1;
                    continue;
                }
                res[nbNode]++;
            }
        }
        return res;
    }
    
    vector<DirectedGraphNode*> addQueue(map<DirectedGraphNode*, int>& indegree,vector<DirectedGraphNode*>& graph){
        vector<DirectedGraphNode*> res;
        if(graph.size() == 0){
            return res;
        }
        
        queue<DirectedGraphNode*> nodeQueue;
        //找到一個入度為0的點
        for(auto it = indegree.begin(); it != indegree.end(); ++it){
            if(it->second == 0){
                nodeQueue.push(it->first);
                res.push_back(it->first);
            }
        }
        
        while(nodeQueue.empty() != true){
            DirectedGraphNode* temp = nodeQueue.front();
            nodeQueue.pop();
            int nbSize = temp->neighbors.size();
            for(int i = 0; i < nbSize; i++){
                indegree[temp->neighbors[i]]--;
                if(indegree[temp->neighbors[i]] == 0){
                    nodeQueue.push(temp->neighbors[i]);
                    res.push_back(temp->neighbors[i]);
                }
            }
        }
        
        return res;
        
    }
};

topo sort