拓扑排序是针对有向无圈图的顶点的的一种排序。
每个顶点拥有入度，邻接表，拓扑序三个成员。首先找到入度为零的顶点将其放入队列，然后将其出队，删除顶点和它的边。然后更新邻接顶点的入度，如果入度为零，则将顶点放入队列，直到队列为空。最后输出拓扑序。
头文件
#include <vector> class Graph { public: explicit Graph(int vertexNum):v(vertexNum+1) { for(auto x:v) { x.indegree=0; x.topoNum=0; x.adjacentList=std::vector<Vertex*>{}; } } void setVertex(int vertexIndex,const std::vector<int> & adjacentIndex) { //创建邻接表并更新入度 for(auto x:adjacentIndex) { v[vertexIndex].adjacentList.push_back(&v[x]); ++v[x].indegree; } } void topoSort(); private: struct Vertex { int indegree; //入度 std::vector<Vertex*> adjacentList; //邻接表 int topoNum; //拓扑序 explicit Vertex(const std::vector<Vertex*> & adList=std::vector<Vertex*>{}) { indegree=0; topoNum=0; adjacentList=adList; } }; std::vector<Vertex> v; };cpp文件
#include "Graph.hpp" #include <map> #include <iostream> #include <Queue> void Graph::topoSort() { std::queue<Vertex*> q; int count=0; //将入度为零的顶点入队 for(int i=1;i<v.size();++i) if(v[i].indegree==0) q.push(&v[i]); while(!q.empty()) { //出队 auto ver=q.front(); ver->topoNum=++count; q.pop(); //更新邻接表的入度，如果等于零，则入队 for(int j=0;j<ver->adjacentList.size();++j) { if(--ver->adjacentList[j]->indegree==0) q.push(ver->adjacentList[j]); } } //按关键字（拓扑序）进行排列，然后输出值（顶点下标） std::map<int,int> result; for(int i=1;i<v.size();++i) { result[v[i].topoNum]=i; } for(auto itr=result.begin();itr!=result.end();++itr) { std::cout<<itr->second<<std::endl; } }main.cpp
#include "Graph.hpp" #include <iostream> using namespace std; int main(int argc, const char * argv[]) { //图由顶点和边组成 Graph g(7);//顶点数 //输入各个顶点的边（邻接顶点） g.setVertex(1, vector<int>{2,3,4}); g.setVertex(2, vector<int>{4,5}); g.setVertex(3, vector<int>{6}); g.setVertex(4, vector<int>{3,6,7}); g.setVertex(5, vector<int>{4,7}); g.setVertex(6, vector<int>{}); g.setVertex(7, vector<int>{6}); g.topoSort();//拓扑排序并输出结果 std::cout << "Hello, World!\n"; return 0; }输出结果 1 2 5 4 3 7 6 Hello, World!
