如何判断一个无向图是不是一棵树？

简化版

无向图是树需要同时满足两个条件：连通、无环。等价地，对 n 个节点来说，如果边数不是 n - 1，一定不是树；边数为 n - 1 时，再确认所有节点连通即可。

详细版

常用做法有两类。DFS/BFS：先判断边数是否为 n - 1，再从 0 出发遍历，最后看是否访问了 n 个节点。并查集：逐条合并边，如果发现两个端点已经在同一集合，说明有环；最后还要保证边数为 n - 1 或连通块数为 1。

树的性质很多，但面试最好抓“连通 + 无环”。边数检查是强剪枝：无向树恰好有 n - 1 条边，边多必有环，边少必不连通。

完整版教学

一、树在无向图里的定义

一棵无向树不是“长得像树”的图，而是满足连通且无环的无向图。连通表示任意两个节点之间都有路径；无环表示不存在从某个节点出发绕一圈回到自己的简单环。

树:
0 - 1 - 2
    |
    3

非树:
0 - 1
|   |
3 - 2   有环

这两个条件缺一不可。只有无环但不连通，是森林；只有连通但有环，是一般连通图，都不是树。

二、边数 n-1 为什么重要

无向树有 n 个节点时，边数一定是 n - 1。这可以从构造理解：第一个节点不需要边，每加入一个新节点，为了保持连通且不成环，只能用一条边把它接到已有树上，所以加入 n-1 次节点，得到 n-1 条边。

边数	可能情况	是否可能是树
小于 n-1	不足以连通所有节点	否
等于 n-1	还需检查连通或无环	可能
大于 n-1	连通情况下必有环	否

例如 n=5 的树必须有 4 条边。只有 3 条边最多连接成森林；有 5 条边则一定多出连接，可能形成环。

三、DFS/BFS 判断连通

有了边数 n - 1 这个前提，只要再确认图连通，就能判断是树。因为边数刚好，连通图不可能再有环；否则连通且有环至少会多出一条边。

boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    List<Integer>[] adj = new ArrayList[n];
    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    for (int[] e : edges) {
        adj[e[0]].add(e[1]);
        adj[e[1]].add(e[0]);
    }
    boolean[] seen = new boolean[n];
    Queue<Integer> q = new ArrayDeque<>();
    q.offer(0);
    seen[0] = true;
    int count = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        count++;
        for (int v : adj[u]) {
            if (!seen[v]) {
                seen[v] = true;
                q.offer(v);
            }
        }
    }
    return count == n;
}

这段代码没有显式判环，因为边数已经排除了边多的情况。这个简化是面试里非常值得讲清楚的点。

四、DFS 显式判环时要带父节点

如果不先用边数剪枝，也可以 DFS 检查无向图是否有环。无向边会从子节点指回父节点，所以 DFS 时遇到已访问节点不能立刻判环，必须排除父节点。

dfs(u, parent):
  mark u
  for v in adj[u]:
    if v == parent: continue
    if visited[v]: cycle
    dfs(v, u)

如果忘记 parent，0-1 这条简单边会在 1 的邻接表里看到 0 已访问，从而被误判成环。无向图判环和有向图三色法不同，这是高频易错点。

五、并查集判断

并查集逐条处理边。如果 u 和 v 已经在同一个集合，再合并会形成环，直接返回 false。处理完所有边后，如果边数是 n - 1 且没有发现环，就可以认为是树。

for each edge (u, v):
  if find(u) == find(v): return false
  union(u, v)
return edges.length == n - 1

也可以维护连通块数量，初始 components = n，每次成功 union 就减 1，最后要求 components == 1。并查集尤其适合边列表输入，不必先建邻接表。

六、复杂度和特殊情况

DFS/BFS 需要建邻接表，时间 O(V+E)，空间 O(V+E)。并查集时间近似 O(E)，空间 O(V)。如果 n=1 且没有边，应该返回 true，因为单个节点本身是一棵树。

方法	优点	注意点
BFS/DFS 连通性	直观，适合讲树性质	要先检查边数
DFS 判环 + 连通	完整覆盖定义	无向图要带 parent
并查集	边列表场景简洁	要处理连通性或边数

面试时推荐先说定义，再给边数剪枝加连通性遍历，这样逻辑最清楚。

七、常见误区与追问

记忆钩子：无向图是树等价于“边数刚好 n-1，并且所有点连成一片”。

误区：只检查没有环。 没有环但可能不连通，那只是森林，不是树。
误区：只检查边数等于 n-1。 边数对了仍可能不连通并有环，例如一个三角形加一个孤立点。
误区：无向图 DFS 遇到访问过节点就判环。 必须排除父节点，否则普通双向边会被误判。
追问：为什么边数小于 n-1 一定不连通？ 每条边最多把两个连通块合成一个，n 个点连成一个块至少需要 n-1 条边。
追问：并查集最后还要检查什么？ 要确保没有环且整体连通；经典写法用 edges.length == n-1 加无环即可。
追问：有向图的树怎么判断？ 要考虑入度、根节点和可达性，不能直接套无向树条件。

八、加强记忆

判断无向图是不是树，不要只背某个算法，而要抓定义：连通且无环。实战中先用 edges.length == n - 1 快速过滤，再 DFS/BFS 检查从一个点能否访问全部节点；或用并查集逐边合并，发现同集合边就是环。边数、连通性、父节点，是这题的三个关键细节。

简化版

详细版