夕拾算法进阶篇：31)拓扑排序(图论)

如果一个有向图的任意顶点都无法通过有向边回到自身，那么称这个有向图为有向无环图(Directed Acyclic Graph)。拓扑排序就是将DAG图的所有顶点排成一个线性序列，使得对图G中的任意两个顶点u、v，如果存在边u->v，那么在序列中u一定就在v前面。这个序列又被称为拓扑序列。

比如下图，在修数据结构之前，必须得修操作系统和计算机导论，而学算法导论之前必须得修C语言课程，而C语言和操作系统、计算机导论的学修顺序是任意的。由此可以把上面的课程排成一个学修的先后序列：C语言->操作系统->计算机导论->算法导论->数据结构->数据挖掘->大数据。

如何求得这个拓扑排序?通过上面的例子可以发现，若一个课程没有先导课程或者所有的先导课程都已经学修完毕，那么这门课程就可以学修了。而这个做法可以抽象为：

(1)定义一个队列Q，并把所有入度为零的结点加入队列中。

(2)取队首结点，输出。然后删除所有从它从发的边，并令这些边到达的顶点的入度减1，如果某个顶点的入度减为0，则将其加入队列。

(3)反复执行步骤2，直到队列为空。如果队列为空时入过队的结点数目恰好为N，则说拓扑排序成功，图G为有向无环图；否则拓扑排序是吧，图G中有环。

下面使用邻接表实现拓扑排序，由于要记录结点的入度，因此需要一个数组inDegree[M]，并在创建图的时候初始化该数组，其实现代码如下

bool topologicalSort(int n){ //n为顶点数 	int num=0; //记录出队的结点数目 	queue<int> q;	for(int i=0;i<n;i++){		if(inDegree[i]==0){			q.push(i); //入度为0的顶点入队 		}	}	while(!q.empty()){		int u=q.front(); 		//PRintf("%d/n",u); //此处可以打印拓扑排序的顶点u		q.pop();		for(int i=0;i<adj[u].size();i++){			int v=adj[u][i]; //u的相连结点v 			inDegree[v]--; //v的入度减1 			if(inDegree[v]==0){ //入度为0则入队 				q.push(i);				}		}		 num++; // 加入拓扑排序的顶点数加1 	}	return num==n; //是否没环 } 
问题 B: 确定比赛名次题目描述有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。输入输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队，输入0 0表示结束。输出给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。样例输入3 23 13 217 160 0样例输出3 1 2
分析：该题可以直接使用上面的代码求解，但是注意题目“此时要求输出时编号小的队伍在前”，所以队列应该使用优先队列
#include <iostream>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int M=505;int inDegree[M]; //入度 vector<int> adj[M];//邻接表 bool topologicalSort(int n){ //n为顶点数 	int num=0; //记录出队的结点数目 	priority_queue<int,vector<int>,greater<int> >q;//从小到大排序 	for(int i=0;i<n;i++){		if(inDegree[i]==0){			q.push(i); //入度为0的顶点入队 		}	}	while(!q.empty()){		int u=q.top(); 		cout<<u+1<<(num<n-1?" ":"/n");		q.pop();		for(int i=0;i<adj[u].size();i++){			int v=adj[u][i]; //u的相连结点v 			inDegree[v]--; //v的入度减1 			if(inDegree[v]==0){ //入度为0则入队 				q.push(v);				}		}		num++; // 加入拓扑排序的顶点数加1 	}	return num==n; //是否没环 } int main(){	int n,m,i,x,y;	while(cin>>n>>m&&(m||n)){		memset(inDegree,0,sizeof(inDegree));		for(i=0;i<m;i++){			cin>>x>>y;			x--;y--; //编号减1 			adj[x].push_back(y);			inDegree[y]++; 		}		topologicalSort(n);		for(i=0;i<n;i++) adj[i].clear();	} } 题目来源：http://codeup.cn/problem.php?cid=100000623&pid=1