FC04-判断无向图是否是一棵树
[[#2. 并查集方法]]
代码实现
| C |
|---|
| // 深度优先搜索函数：遍历图并统计访问的顶点数
// 参数：
// G - 图的邻接表表示
// v - 当前访问的顶点
// visit[] - 访问标记数组
// vn - 指向已访问顶点数的指针
void DFS(Graph G, int v, int visit[], int *vn) {
visit[v] = 1; // 标记当前顶点为已访问
++(*vn); // 已访问顶点数加 1
// 获取当前顶点的第一条边
Node p = G.adjlist[v].firstarc;
// 遍历当前顶点的所有邻接顶点
for (; p != NULL; p = p->nextarc) {
// 如果邻接顶点未被访问，则递归访问
if (visit[p->adjvex] == 0) {
DFS(G, p->adjvex, visit, vn);
}
}
}
// 函数 IsTree：判断无向图是否是一棵树
// 参数：G - 图的邻接表表示
bool IsTree(Graph G) {
int v = 0; // 从顶点 0 开始遍历
int vn = 0; // 已访问顶点数
int visit[maxsize] = {0}; // 访问标记数组，初始化为 0
// 从顶点 0 开始进行深度优先搜索
DFS(G, v, visit, &vn);
// 判断是否满足树的条件
// 条件1：所有顶点都能被访问到（连通性）
// 条件2：顶点数 - 边数 = 1（无环性）
if (vn == G.numver && (G.numver - G.numedg) == 1) {
return true; // 是树
} else {
return false; // 不是树
}
}
|
代码逻辑解析
1. 树的定义和性质
无向图是一棵树当且仅当满足以下两个条件：
- 连通性：图中任意两个顶点之间都存在路径
- 无环性：图中不存在环路
2. 树的等价性质
对于有 n 个顶点和 e 条边的无向图，以下条件等价：
- 图是一棵树
- 图连通且 e = n - 1
- 图无环且 e = n - 1
- 图连通且无环
3. 算法思路
- 使用深度优先搜索（DFS）检查图的连通性
- 通过验证
顶点数 - 边数 = 1 检查无环性
4. DFS 函数详解
- 标记访问：将当前顶点标记为已访问
- 计数：增加已访问顶点数
- 递归遍历：访问所有未被访问的邻接顶点
5. IsTree 函数详解
- 连通性检查：通过 DFS 统计能访问到的顶点数，如果等于总顶点数，则连通
- 无环性检查：验证
顶点数 - 边数 = 1
时间复杂度分析
1. DFS 时间复杂度
- 每个顶点被访问 exactly 一次：O(V)
- 每条边被检查 exactly 一次：O(E)
- 总时间复杂度：O(V + E)
2. 数组初始化时间复杂度
3. 总体时间复杂度
O(V + E)
空间复杂度分析
1. 额外空间使用
2. 递归调用栈空间
- 最坏情况下递归深度为 V（退化为链表时）
- 空间复杂度：O(V)
较难理解部分的说明
1. 为什么 顶点数 - 边数 = 1 表示无环？
数学证明：
对于树的归纳证明：
- 基础情况：1 个顶点，0 条边，满足 1 - 0 = 1
- 归纳步骤：假设 k 个顶点的树满足性质，添加一个新顶点和一条边连接到树上，得到 (k+1) 个顶点和 k 条边，满足 (k+1) - k = 1
图解说明：
| Text Only |
|---|
| 顶点数 = 4, 边数 = 3
A
/ \
B C
/
D
满足：4 - 3 = 1，是树
顶点数 = 4, 边数 = 4
A --- B
/ \ /
D --- C
满足：4 - 4 = 0 ≠ 1，有环，不是树
顶点数 = 4, 边数 = 2
A B
/ \
C D
满足：4 - 2 = 2 ≠ 1，不连通，不是树
|
2. 算法正确性分析
连通性检查：
- 从任意顶点开始 DFS，如果能访问所有顶点，则图连通
- 为什么从顶点 0 开始就够了？如果图连通，从任何顶点开始都能访问所有顶点
无环性检查：
- 对于连通图，边数 = 顶点数 - 1 当且仅当图无环
- 这是树的基本性质
延伸知识点
1. 改进版本 - BFS 实现
| C |
|---|
| // 使用广度优先搜索判断连通性
bool IsTree_BFS(Graph G) {
if (G.numver == 0) return true;
if (G.numver - G.numedg != 1) return false; // 先检查边数条件
int visit[maxsize] = {0};
int vn = 0;
Queue* queue = createQueue();
visit[0] = 1;
enqueue(queue, 0);
vn = 1;
while (!isEmpty(queue)) {
int v = dequeue(queue);
Node p = G.adjlist[v].firstarc;
for (; p != NULL; p = p->nextarc) {
int adj = p->adjvex;
if (!visit[adj]) {
visit[adj] = 1;
enqueue(queue, adj);
vn++;
}
}
}
return vn == G.numver;
}
|
2. 并查集方法
| C |
|---|
| /**
* 使用并查集判断给定的无向图 G 是否是一棵树
*
* 树的定义：
* 1. 必须是连通图（所有节点属于同一个连通分量）
* 2. 恰好有 n-1 条边（n 为节点数），且无环
*
* 算法思路：
* - 遍历所有边，利用并查集合并两端节点
* - 若某条边的两个端点已在同一集合中，则说明存在环，返回 false
* - 边数检查 + 无环 可推出连通
*
* @param G 图结构（邻接表表示的无向图）
* @return true 表示 G 是一棵树；false 表示不是树
*/
bool IsTree_UnionFind(Graph G) {
// 初始化并查集：每个节点独立成一个集合
init();
int edge=0;
// 遍历图中每一个顶点的邻接边（无向图每条边只处理一次即可）
for (int i = 0; i < G.numver; i++) {
for(ArcNode* temp = G.adjlist[i].firstarc;temp!=NULL;temp=temp->nextarc){
// 为了避免重复处理无向边 (i, adj)，我们只处理 i < adj 的情况
// 这样每条无向边只会被处理一次，防止重复 union 或误判环
if (i < temp->adjvex) {
edge++;
int rootI = find(i);
int rootAdj = find(temp->adjvex);
// 如果两个端点已经连通，说明加入这条边会形成环
if (rootI == rootAdj) {
return false; // 发现环，不是树
}
// 合并两个集合
unionSet(i, temp->adjvex);
}
}
}
// 到这里说明没有环，且边数为 n-1
// 数学性质保证：n 个节点、n-1 条边、无环 ⇒ 连通 ⇒ 是一棵树
return countSet() == 1 && edge == G.vexnum-1;
}
|
3. 其他树的判定方法
| C |
|---|
| // 方法1：检查每个连通分量是否为树
bool IsForest(Graph G) {
int visit[maxsize] = {0};
int components = 0;
int trees = 0;
for (int i = 0; i < G.numver; i++) {
if (!visit[i]) {
components++;
int vn = 0;
DFS(G, i, visit, &vn);
// 检查这个连通分量是否为树
// 需要额外的边数统计...
}
}
return components == 1; // 只有一个连通分量且为树
}
|
4. 实际应用场景
- 网络设计：判断网络拓扑是否为树形结构
- 文件系统：验证目录结构的合法性
- 电路设计：检查电路连接是否形成树状结构
- 社交网络：分析用户关系的树形特征
- 编译器：语法分析树的验证
5. 边界情况处理
| C |
|---|
| // 完整版本，处理各种边界情况
bool IsTree_Complete(Graph G) {
// 空图
if (G.numver == 0) return true;
// 单个顶点
if (G.numver == 1) return (G.numedg == 0);
// 边数检查（必要条件）
if (G.numver - G.numedg != 1) return false;
// 连通性检查
int visit[maxsize] = {0};
int vn = 0;
DFS(G, 0, visit, &vn);
return vn == G.numver;
}
|
这种方法体现了图论基本性质应用的思想，通过简单的数学关系就能高效判断复杂的图结构性质，是图算法中的经典问题。