一、拓扑排序的介绍拓扑排序对应施工的流程图具有特别重要的作用它可以决定哪些子工程必须要先执行哪些子工程要在某些工程执行后才可以执行。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系可用一个有向图来表示图中的顶点代表活动(子工程)图中的有向边代表活动的先后关系即有向边的起点的活动是终点活动的前序活动只有当起点活动完成之后其终点活动才能进行。通常我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)简称AOV网。一个AOV网应该是一个有向无环图即不应该带有回路因为若带有回路则回路上的所有活动都无法进行对于数据流来说就是死循环。在AOV网中若不存在回路则所有活动可排列成一个线性序列使得每个活动的所有前驱活动都排在该活动的前面我们把此序列叫做拓扑序列(Topological order)由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的满足上述定义的任一线性序列都称作它的拓扑序列。二、拓扑排序的实现步骤1.在有向图中选一个没有前驱的顶点并且输出2.从图中删除该顶点和所有以它为尾的弧白话就是删除所有和它有关的边3.重复上述两步直至所有顶点输出或者当前图中不存在无前驱的顶点为止后者代表我们的有向图是有环的因此也可以通过拓扑排序来判断一个图是否有环。三、拓扑排序示例手动实现如果我们有如下的一个有向无环图我们需要对这个图的顶点进行拓扑排序过程如下首先我们发现V6和v1是没有前驱的所以我们就随机选去一个输出我们先输出V6删除和V6有关的边得到如下图结果然后我们继续寻找没有前驱的顶点发现V1没有前驱所以输出V1删除和V1有关的边得到下图的结果然后我们又发现V4和V3都是没有前驱的那么我们就随机选取一个顶点输出具体看你实现的算法和图存储结构我们输出V4得到如下图结果然后我们输出没有前驱的顶点V3得到如下结果然后我们分别输出V5和V2最后全部顶点输出完成该图的一个拓扑序列为v6–v1—-v4—v3—v5—v2四、拓扑排序的代码实现下面我们将用两种方法来实现我么的拓扑排序1.Kahn算法2.基于DFS的拓扑排序算法首先我们先介绍第一个算法的思路Kahn的算法的思路其实就是我们之前那个手动展示的拓扑排序的实现我们先使用一个栈保存入度为0 的顶点然后输出栈顶元素并且将和栈顶元素有关的边删除减少和栈顶元素有关的顶点的入度数量并且把入度减少到0的顶点也入栈。具体的代码如下1234567891011121314151617181920212223242526272829303132333435363738394041424344boolGraph_DG::topological_sort() {cout 图的拓扑序列为 endl;//栈s用于保存栈为空的顶点下标stackint s;inti;ArcNode * temp;//计算每个顶点的入度保存在indgree数组中for(i 0; i !this-vexnum; i) {temp this-arc[i].firstarc;while(temp) {this-indegree[temp-adjvex];temp temp-next;}}//把入度为0的顶点入栈for(i 0; i !this-vexnum; i) {if(!indegree[i]) {s.push(i);}}//count用于计算输出的顶点个数intcount0;while(!s.empty()) {//如果栈为空则结束循环i s.top();s.pop();//保存栈顶元素并且栈顶元素出栈cout this-arc[i].data ;//输出拓扑序列temp this-arc[i].firstarc;while(temp) {if(!(--this-indegree[temp-adjvex])) {//如果入度减少到为0则入栈s.push(temp-adjvex);}temp temp-next;}count;}if(count this-vexnum) {cout endl;returntrue;}cout 此图有环无拓扑序列 endl;returnfalse;//说明这个图有环}现在我们来介绍第二个算法的思路其实DFS就是深度优先搜索它每次都沿着一条路径一直往下搜索知道某个顶点没有了出度时就停止递归往回走所以我们就用DFS的这个思路我们可以得到一个有向无环图的拓扑序列其实DFS很像Kahn算法的逆过程。具体的代码实现如下123456789101112131415161718192021222324252627282930313233343536373839404142boolGraph_DG::topological_sort_by_dfs() {stackstring result;inti;bool* visit newbool[this-vexnum];//初始化我们的visit数组memset(visit, 0,this-vexnum);cout 基于DFS的拓扑排序为 endl;//开始执行DFS算法for(i 0; i this-vexnum; i) {if(!visit[i]) {dfs(i, visit, result);}}//输出拓扑序列因为我们每次都是找到了出度为0的顶点加入栈中//所以输出时其实就要逆序输出这样就是每次都是输出入度为0的顶点for(i 0; i this-vexnum; i) {cout result.top() ;result.pop();}cout endl;returntrue;}voidGraph_DG::dfs(intn,bool* visit, stackstring result) {visit[n] true;ArcNode * temp this-arc[n].firstarc;while(temp) {if(!visit[temp-adjvex]) {dfs(temp-adjvex, visit,result);}temp temp-next;}//由于加入顶点到集合中的时机是在dfs方法即将退出之时//而dfs方法本身是个递归方法//仅仅要当前顶点还存在边指向其他不论什么顶点//它就会递归调用dfs方法而不会退出。//因此退出dfs方法意味着当前顶点没有指向其他顶点的边了//即当前顶点是一条路径上的最后一个顶点。//换句话说其实就是此时该顶点出度为0了result.push(this-arc[n].data);}两种算法总结对于基于DFS的算法增加结果集的条件是顶点的出度为0。这个条件和Kahn算法中入度为0的顶点集合似乎有着异曲同工之妙Kahn算法不须要检测图是否为DAG假设图为DAG那么在入度为0的栈为空之后图中还存在没有被移除的边这就说明了图中存在环路。而基于DFS的算法须要首先确定图为DAG当然也可以做出适当调整让环路的检测測和拓扑排序同一时候进行毕竟环路检測也可以在DFS的基础上进行。二者的复杂度均为O(VE)。五、完整的代码和输出展示topological_sort.h文件的代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#pragma once//#pragma once是一个比较常用的C/C杂注//只要在头文件的最开始加入这条杂注//就能够保证头文件只被编译一次。/*拓扑排序必须是对有向图的操作算法实现1Kahn算法2DFS算法采用邻接表存储图*/#includeiostream#includestring#includestackusingnamespacestd;//表结点structArcNode {ArcNode * next;//下一个关联的边intadjvex;//保存弧尾顶点在顶点表中的下标};structVnode {string data;//顶点名称ArcNode * firstarc;//第一个依附在该顶点边};classGraph_DG {private:intvexnum;//图的顶点数intedge;//图的边数int* indegree;//每条边的入度情况Vnode * arc;//邻接表public:Graph_DG(int,int);~Graph_DG();//检查输入边的顶点是否合法boolcheck_edge_value(int,int);//创建一个图voidcreateGraph();//打印邻接表voidprint();//进行拓扑排序,Kahn算法booltopological_sort();//进行拓扑排序DFS算法booltopological_sort_by_dfs();voiddfs(intn,bool* visit, stackstring result);};topological_sort.cpp文件代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171#includetopological_sort.hGraph_DG::Graph_DG(intvexnum,intedge) {this-vexnum vexnum;this-edge edge;this-arc newVnode[this-vexnum];this-indegree newint[this-vexnum];for(inti 0; i this-vexnum; i) {this-indegree[i] 0;this-arc[i].firstarc NULL;this-arc[i].data v to_string(i 1);}}//释放内存空间Graph_DG::~Graph_DG() {ArcNode * p, *q;for(inti 0; i this-vexnum; i) {if(this-arc[i].firstarc) {p this-arc[i].firstarc;while(p) {q p-next;deletep;p q;}}}delete[]this-arc;delete[]this-indegree;}//判断我们每次输入的的边的信息是否合法//顶点从1开始编号boolGraph_DG::check_edge_value(intstart,intend) {if(start1 || end1 || startvexnum || endvexnum) {returnfalse;}returntrue;}voidGraph_DG::createGraph() {intcount 0;intstart, end;cout 输入每条起点和终点的顶点编号从1开始编号 endl;while(count !this-edge) {cin start;cin end;//检查边是否合法while(!this-check_edge_value(start, end)) {cout 输入的顶点不合法请重新输入 endl;cin start;cin end;}//声明一个新的表结点ArcNode * temp newArcNode;temp-adjvex end - 1;temp-next NULL;//如果当前顶点的还没有边依附时if(this-arc[start - 1].firstarc NULL) {this-arc[start - 1].firstarc temp;}else{ArcNode * now this-arc[start - 1].firstarc;while(now-next) {now now-next;}//找到该链表的最后一个结点now-next temp;}count;}}voidGraph_DG::print() {intcount 0;cout 图的邻接矩阵为 endl;//遍历链表输出链表的内容while(count !this-vexnum) {//输出链表的结点cout this-arc[count].data ;ArcNode * temp this-arc[count].firstarc;while(temp) {coutthis-arc[count].data,this-arc[temp-adjvex].data ;temp temp-next;}cout ^ endl;count;}}boolGraph_DG::topological_sort() {cout 图的拓扑序列为 endl;//栈s用于保存栈为空的顶点下标stackint s;inti;ArcNode * temp;//计算每个顶点的入度保存在indgree数组中for(i 0; i !this-vexnum; i) {temp this-arc[i].firstarc;while(temp) {this-indegree[temp-adjvex];temp temp-next;}}//把入度为0的顶点入栈for(i 0; i !this-vexnum; i) {if(!indegree[i]) {s.push(i);}}//count用于计算输出的顶点个数intcount0;while(!s.empty()) {//如果栈为空则结束循环i s.top();s.pop();//保存栈顶元素并且栈顶元素出栈cout this-arc[i].data ;//输出拓扑序列temp this-arc[i].firstarc;while(temp) {if(!(--this-indegree[temp-adjvex])) {//如果入度减少到为0则入栈s.push(temp-adjvex);}temp temp-next;}count;}if(count this-vexnum) {cout endl;returntrue;}cout 此图有环无拓扑序列 endl;returnfalse;//说明这个图有环}boolGraph_DG::topological_sort_by_dfs() {stackstring result;inti;bool* visit newbool[this-vexnum];//初始化我们的visit数组memset(visit, 0,this-vexnum);cout 基于DFS的拓扑排序为 endl;//开始执行DFS算法for(i 0; i this-vexnum; i) {if(!visit[i]) {dfs(i, visit, result);}}//输出拓扑序列因为我们每次都是找到了出度为0的顶点加入栈中//所以输出时其实就要逆序输出这样就是每次都是输出入度为0的顶点for(i 0; i this-vexnum; i) {cout result.top() ;result.pop();}cout endl;returntrue;}voidGraph_DG::dfs(intn,bool* visit, stackstring result) {visit[n] true;ArcNode * temp this-arc[n].firstarc;while(temp) {if(!visit[temp-adjvex]) {dfs(temp-adjvex, visit,result);}temp temp-next;}//由于加入顶点到集合中的时机是在dfs方法即将退出之时//而dfs方法本身是个递归方法//仅仅要当前顶点还存在边指向其他不论什么顶点//它就会递归调用dfs方法而不会退出。//因此退出dfs方法意味着当前顶点没有指向其他顶点的边了//即当前顶点是一条路径上的最后一个顶点。//换句话说其实就是此时该顶点出度为0了result.push(this-arc[n].data);}main.cpp文件12345678910111213141516171819202122232425262728#includetopological_sort.h//检验输入边数和顶点数的值是否有效可以自己推算为啥//顶点数和边数的关系是((Vexnum*(Vexnum - 1)) / 2) edgeboolcheck(intVexnum,intedge) {if(Vexnum 0 || edge 0 || ((Vexnum*(Vexnum - 1)) / 2) edge)returnfalse;returntrue;}intmain() {intvexnum;intedge;cout 输入图的顶点个数和边的条数 endl;cin vexnum edge;while(!check(vexnum, edge)) {cout 输入的数值不合法请重新输入 endl;cin vexnum edge;}Graph_DG graph(vexnum, edge);graph.createGraph();graph.print();graph.topological_sort();graph.topological_sort_by_dfs();system(pause);return0;}输入6 81 21 31 43 23 54 56 46 5输出输入13 151 21 61 73 13 44 66 57 47 108 79 810 1110 1210 1312 13输出以上就是详解C实现拓扑排序算法的详细内容