图论之拓扑排序

拓扑排序常用来确定一个依赖关系的集和中,事物发生的顺序。
例如,在日常工作中,可能会将项目拆分成A、B、C、D四个子部分来完成,但A依赖于B和D,C依赖于D。为了计算这个项目进行的顺序,可对这个关系集进行拓扑排序,得出一个线性的序列,则排在前面的任务就是需要先完成的任务。 显然拓扑排序的序列可能不唯一。

概念:
对一个有向无环图G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若 (u,v)∈E(G),则u在线性序列中出现在v之前。

实现:
(1)从有向图中选择一个入度为0(即没有前驱)的顶点并且输出它.
(2)从图中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的图中不再存在入度为0的顶点为止
这里主要是将入度为0的点加入队列或者栈,直接在队列(栈)内扩展即可,效率为O(n) 。

邻接表实现:

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m;
int head[100100],next[100100],to[100100],tot;
int ans[100100];
int v[100100];
void check()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		if(v[i]==0)     q.push(i);
	}	
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		ans[++ans[0]]=x;
		for(int i=head[x];i!=0;i=next[i])
		{
			v[to[i]]--;
			if(v[to[i]]==0)
			{
				q.push(to[i]);
			}
		}
	}
} 
void add(int x,int y)
{ 
	tot++;
	to[tot]=y;
	next[tot]=head[x];
	head[x]=tot;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		v[y]++;
	}
	check();
	if(ans[0]==n)printf("OK");
	else printf("%d",n-ans[0]);
	return 0;
}

邻接矩阵实现:

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m;
int map[8000][8000];
int ans[8000];
int v[8000];
int len;
void check()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		if(v[i]==0)q.push(i);
	}	
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		ans[++ans[0]]=tmp;
		for(int i=1;i<=n;i++)
		{
			if(map[tmp][i]==1)
			{
				v[i]--;
				if(v[i]==0)
				{
					q.push(i);
				}
			}
		}
	}
} 
int main()
{
	freopen("button.in","r",stdin);
	freopen("button.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		map[x][y]=1;
		v[y]++
	}
	check();
	if(ans[0]==n)printf("OK");
	else printf("%d",n-ans[0]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

 

关于“图论之拓扑排序”我的1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注