拓扑排序的意思：
对一个(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)，由 构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。
拓扑排序的步骤：
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有 。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有 ”信息，否则输出的顶点序列就是一种拓扑
拓扑排序排序：
/** * Definition for Directed graph. * struct DirectedGraphNode { * int label; * vector neighbors; * DirectedGraphNode(int x) : label(x) {}; * }; */ //使用bfs进行拓扑排序：//1、统计各个节点的入度信息，//2、查找入度为0的点放入队列和返回的vector中初始化bfs的队列//3、进行bfs，将从队列中弹出的元素的neighbors的入度减1然后判断该节点入度是否为0.为0// 则加入队列同时加入返回vector中（这一步的主要框架就是bfs的程序框架）class Solution {public: vector topSort(vector graph) { // write your code here //1、得到所有节点的入度信息 map indegree = getIndegree(graph); //2、将入度为0的放入队列 return addQueue(indegree, graph); } map getIndegree(vector graph){ int size = graph.size(); map 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 addQueue(map & indegree,vector & graph){ vector res; if(graph.size() == 0){ return res; } queue 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; }};