求无向图是否为一颗树,请写出c语言代码实现
时间: 2024-03-25 18:38:47 浏览: 29
以下是使用深度优先搜索(DFS)判断无向图是否为一棵树的 C 语言代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAXN 10000 // 最大节点数
int head[MAXN], nxt[MAXN*2], ver[MAXN*2]; // 邻接表存储图
bool vis[MAXN]; // 标记节点是否被访问过
int fa[MAXN]; // 记录每个节点的父节点
int cnt = 0; // 边数
int n; // 节点数
// 添加一条边
void add_edge(int u, int v) {
nxt[++cnt] = head[u];
ver[cnt] = v;
head[u] = cnt;
}
// DFS 遍历整个无向图,判断是否为一棵树
bool dfs(int u, int father) {
fa[u] = father; // 记录父节点
vis[u] = true; // 标记已经访问过
for (int i = head[u]; i; i = nxt[i]) { // 遍历与当前节点相邻的节点
int v = ver[i];
if (vis[v] && v != father) { // 如果当前节点已经被访问过,且不是父节点
return false; // 发现环路,不是一棵树
}
if (!vis[v]) { // 如果当前节点没有被访问过
if (!dfs(v, u)) { // 递归调用 DFS
return false; // 发现环路,不是一棵树
}
}
}
return true; // 没有发现环路,是一棵树
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n-1; i++) { // 读入边
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
if (dfs(1, 0) && !vis[n]) { // 从节点 1 开始 DFS,判断是否为一棵树
printf("Yes\n");
} else {
printf("No\n");
}
return 0;
}
```
代码中使用邻接表存储无向图,其中 `head[u]` 存储与节点 `u` 相连的第一条边在数组中的位置,`nxt[i]` 存储与第 `i` 条边同起点的下一条边在数组中的位置,`ver[i]` 存储第 `i` 条边的终点。
在 DFS 遍历过程中,使用数组 `vis` 标记节点是否被访问过,使用数组 `fa` 记录每个节点的父节点。如果发现当前节点已经被访问过,且不是父节点,则说明发现了环路,不是一棵树。
最后判断从节点 1 开始 DFS 是否能够访问到所有节点,并且不发现环路,如果满足条件,则说明这个无向图是一棵树。