拓扑排序
1.什么是拓扑排序？
对一个(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
也就是说排序后的一个顶点不存在指向他前面顶点的边。
2.拓扑排序的应用？
拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。
3.怎样进行拓扑排序？
对于一个给定的图，先找到入度为0的点，那么这个点就是排序后的第一个顶点，然后将他指向顶点的入度减1，再寻找下一个入度为0的顶点直至找到所有顶点，但是拓扑排序不能应用在有环图中，因为有环图不存在入度为0的顶点。
int topsort(int x){ priority_queue ,greater
>q; int flag=0,k; int zeroflag=0; int num=0; memcpy(temp,in,sizeof(in)); for(int i=0;i
1) zeroflag=1; k=q.top(); q.pop(); num++; ans[num]=k+'A'; for(int i = 0 ; i < x; i++ ) if(map[k][i]==1 && --temp[i] == 0) q.push(i); } //cout< <<" "< < 
#include #include #include using namespace std;#define maxn 50int n,m;int in[maxn],temp[maxn];bool map[maxn][maxn];char ans[maxn];int topsort(int x){ priority_queue
,greater
>q; int flag=0,k; int zeroflag=0; int num=0; memcpy(temp,in,sizeof(in)); for(int i=0;i
1) zeroflag=1; k=q.top(); q.pop(); num++; ans[num]=k+'A'; for(int i = 0 ; i < x; i++ ) if(map[k][i]==1 && --temp[i] == 0) q.push(i); } //cout< <<" "< < >n>>m) { circleflag=0;orderflag=0; if(n==0&&m==0) return 0; memset(map,0,sizeof(map)); memset(in,0,sizeof(in)); for(int i=1;i<=m;i++) { scanf("%s",s); if(circleflag==0&&orderflag==0) { if(map[s[2]-'A'][s[0]-'A']==1) { circleflag=1; printf("Inconsistency found after %d relations.\n", i); continue; } if(map[s[0]-'A'][s[2]-'A']==0) { map[s[0]-'A'][s[2]-'A']=1; in[s[2]-'A']++; } int k=topsort(n); if(k==1) { circleflag=1; printf("Inconsistency found after %d relations.\n", i); } else if(k==-1) { orderflag=1; step=i; } } } if(circleflag==0&&orderflag==0) printf("Sorted sequence cannot be determined.\n"); else if(orderflag==1) { printf("Sorted sequence determined after %d relations: ", step); for(int i=1;i<=n;i++) { printf("%c",ans[i]); } printf(".\n"); } } return 0;}