求无向图是否为一颗树,请写出c语言代码实现
时间: 2024-03-25 19:39:05 浏览: 56
带权无向图
5星 · 资源好评率100%
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来判断一张无向图是否为一棵树。以下是使用深度优先搜索的C语言代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAXN 100
int G[MAXN][MAXN]; // 无向图的邻接矩阵
bool visited[MAXN]; // 记录节点是否被访问过
int n, m; // 无向图的节点数和边数
bool is_tree(int u, int parent)
{
visited[u] = true; // 标记节点为已访问
for (int v = 0; v < n; v++)
{
if (G[u][v]) // 如果节点u和节点v之间有边相连
{
if (!visited[v]) // 如果节点v没有被访问过
{
if (is_tree(v, u) == false) // 递归判断节点v是否在以u为根的子树中出现过
{
return false;
}
}
else if (v != parent) // 如果节点v已经被访问过,且不是节点u的父节点
{
return false; // 说明出现了环,不是一棵树
}
}
}
return true; // 没有出现环,是一棵树
}
int main()
{
scanf("%d%d", &n, &m);
// 读入边
for (int i = 0; i < m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
G[u][v] = G[v][u] = 1; // 无向图的边是双向的
}
// 判断是否是一棵树
if (is_tree(0, -1) == true && m == n - 1) // 从节点0开始遍历,-1表示没有父节点
{
printf("This is a tree.\n");
}
else
{
printf("This is not a tree.\n");
}
return 0;
}
```
注意,这里假设无向图的节点编号从0开始,节点数不超过100。如果节点编号从1开始,需要将数组下标减1。
阅读全文