图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 graphn");
		else printf("Unconnected graphn");
	}
}

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!