参考链接:https://zhuanlan.zhihu.com/p/34871092
含义:
是一个有向无环图(DAG)的所有顶点的线性序列。若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
满足条件:
1、每个顶点出现且只出现一次。
2、只有有向无环图(DAG)才有拓扑排序,非DAG图没有拓扑排序一说。
实现:
1、从DAG图中选择一个入度为零的顶点输出并删除该顶点以及以该顶点为起点的有向边。
2、重复上述两个步骤,直到图为空或图中没有入度为零的顶点为止,后一种情况说明图中必然存在环。
int check(int step){if(step+1==n) return 1;int tt[30][30];for(int i=0; i<n; i++)for(int j=0; j<n; j++)tt[i][j]=t[i][j];int fin=0;//这一层是否删除了无入度但有出度的节点for(int i=0; i<n; i++){int fone=0;//被选定的i是否有入度for(int j=0; j<n; j++)if(tt[j][i]==1){fone=1;break;}if(!fone){int fput=0;//被选定的i是否有出度for(int j=0; j<n; j++)if(t[i][j]==1){fin=1;fput=1;t[i][j]=0;}if(fput){ans[++ans[0]]=i;alp[i]=1;}}}if(!fin){//回路判断for(int i=0; i<n; i++)for(int j=0; j<n; j++)if(t[i][j]==1) return 2;}if(fin) return check(step+1);else return 0;}
