设计一个算法,判断无向图G是否是一棵树。若是树,则返回l;否则返回0。

2020-04-28 社会 85阅读
算法描述:
即判断该无向图不存在环,并且该图是连通的(排除森林的可能性)

int const N = 100;
bool visit[N];// 标记该节点是否访问过
bool edge[N][N];// 数组记录两点是否存在边
int n;// 图中节点的数目
bool dfs(int x,int fa)
{
if(visit[x])return false;
visit[x] = true;
for(int i=1;i<=n;i++)
if(i!=fa&&edge[x][i])
{
if(dfs(i) == false)return false;
}
return true;
}
int main()
{
// 前面嵌套图的输入

int c=0;
bool flag = true;
memset(visit,false,sizeof(visit));
for(int i=1;i<=n;i++)
if(!visit[i])
{
c++;
if(c==2)break;
flag = dfs(i);
if(flag == false)break;
}
if(flag == flag || c==2)puts("不是树");
else puts("是一颗树");
return 0;
}
声明:你问我答网所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系fangmu6661024@163.com