拓扑排序算法思想:
(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.
(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.
注:拓扑排序得到的拓扑序列不唯一。
例如:
将下图进行一次拓扑排序,输出其中的一个拓扑序列。
第一步:搜索图中入度为0的点,我们可以找到a、e,我们选择a,删去该点,同时删去改定点出发的所有有向边,得到:
第二步:循环该操作,选择处理c点,得到:
第三步:处理b点:
第四步:处理e点:
第五、第六步如此类推,得到:
最后再也找不到入度为0的点了,得到该拓扑序列为:a、c、b、e、d、f
注意前面所说的,拓扑排序得到的拓扑序列不唯一,因为在第一步、第二步和第三步,我们可以先处理点e而不是a、c、b,所以e、a、c、b、d、f这个序列也是正确的,我们应该根据题目的要求选择优先处理各个点。
下面是一道题目代码:
确定比赛名次
这道题目有一个小陷阱,就是重边问题。也就是,题目输入的时候,可能会输入2次或者3次同一条边。
#include <iostream> using namespace std; const int MAXN=500+50; int map[MAXN][MAXN];//保存图的信息 int dis[MAXN];//保存每个点的入度 int num[MAXN]; int main() { int n,m; int a,b; while(cin>>n>>m) { memset(map,0,sizeof(map)); memset(dis,0,sizeof(dis)); int i; for(i=1;i<=m;i++) { cin>>a>>b; if(!map[a][b])//防止重边 { map[a][b]++; dis[b]++; } } int index; int k=0; for(int l=1;l<=n;l++) { for(int j=n;j>0;j--) { if(dis[j]==0) { index=j; } } num[k++]=index; for(int i=1;i<=n;i++) { if(map[index][i]) dis[i]--; } dis[index]--; } for(i=0;i<n;i++) { printf(i?" %d":"%d",num[i]); } cout<<endl; } }