- /**
- * 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 topSort(vector graph) {
- // write your code here
- //1、得到所有节点的入度信息mapint> indegree = getIndegree(graph);
- //2、将入度为0的放入队列
- return addQueue(indegree, graph);
- }
- mapint> getIndegree(vector graph){
- intsize = graph.size();
- mapint> res;
- if(size ==0){
- return res;
- }
- for(inti =0; i < size; i++){
- DirectedGraphNode* temp = graph[i];
- if(res.find(temp) == res.end()){
- res[temp] =0;
- }
- intnbSize = temp->neighbors.size();
- for(inti =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(mapint>& 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();
- intnbSize = temp->neighbors.size();
- for(inti =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;
- }
- };
来源: http://www.bubuko.com/infodetail-1990905.html