图about连通性,简单路径,深搜,广搜。

前端之家收集整理的这篇文章主要介绍了图about连通性,简单路径,深搜,广搜。前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

星期三又要考试啦,今天来复习下,嘿嘿~

图中两个顶点之间的简单路径

#include<stdio.h>
#include<string.h>
int m,n,a[100][100],v[100],s[100],top,ve,vb,flag;
void dfs()
{
	int i,j,temp;
	if(flag)
	{
		if(s[top]==ve)
		{
			for(j=1;j<=top;j++)
				printf("%d",s[j]);
			flag=0;
		}
		if(v[s[top]]==0)
		{
			v[s[top]]=1;
			temp=s[top];
			for(i=1;i<=m;i++)
			{
				if(v[i]==0&&a[temp][i]==1)
				{
					s[++top]=i;
					dfs();//递归;
					top--;
				}
			}
		}
	}
}//深搜;
int main()
{
	int i,k,p,q,b,cas=1;
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		memset(a,sizeof(a));
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&p,&q);
			a[p][q]=1;a[q][p]=1;
		}
		scanf("%d",&k);
		printf("Case %d:\n",cas++);
		while(k--)
		{
			scanf("%d%d",&vb,&ve);
		top=1;s[top]=vb;
		memset(v,sizeof(v));//做标记;
		flag=1;
		dfs();
		printf("\n");
		}
	}
}


图的连通性:

#include<stdio.h>
#include<string.h>
int m,z;
void dfs()
{
	int i,temp,v[100]={0};
	top=1;s[top]=1;
	while(top>0)
	{
		if(v[s[top]]==0)
		{
			v[s[top]]=1;
			temp=s[top];
			z++;
			for(i=1;i<=m;i++)
			{
				if(a[temp][i]==1&&v[i]==0)
					s[++top]=i;
			}//找出连接的点。
		}
		else top--;
	}
}//深搜;
int main()
{
	int i,q;
	while(scanf("%d%d",&n)!=EOF)
	{
		if(m==0&&n==0)break;
		memset(a,&q);
			a[p][q]=1;a[q][p]=1;
		}
		z=0;
		dfs();
		if(z==m)
			printf("Connected graph\n");
		else printf("Unconnected graph\n");
	}
}

用的是图的深搜+累计搜到的点。

猜你在找的VB相关文章