图的dfs和bfs(基于链式前向星)

看了半天,,总算是对链式前向星了解更深些了,其实就是一种邻接顺序表(邻接表的顺序实现)
图的dfs

bool visit[1000];
void dfs(int x)
{
	visit[x]=true;
	visit x;
	for(k=head[x];k!=-1;k=edge[k].next)
	{
		if(!visit[edge[k].to])
			dfs(edge[k].to);
	}
}

图的bfs

bool visit[1000];
int queue[maxn];//maxn  顶点数
int indegree[maxm];//maxm  弧数,在链式前向星建图时赋值
void bfs(int x)
{
	int iq=0,k;
	queue[iq++]=x;
	visit[x]=true;
	for(i=0;i<=iq-1;i++)
		for(k=head[queue[i]];k!=-1;k=edge[k].next)
		{
			if(!visit[edge[k].to])
			{
				queue[iq++]=edge[k].to;
				visit[edge[k].to]=true;
			}
		}
}
//最终的队列queue就是bfs序列

发表评论

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

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>