描述
给出 n 个节点，标号分别从 0 到 n - 1 并且给出一个 无向 边的列表 (给出每条边的两个顶点), 写一个函数去判断这张｀无向｀图是否是一棵树
你可以假设我们不会给出重复的边在边的列表当中. 无向边 [0, 1] 和 [1, 0] 是同一条边， 因此他们不会同时出现在我们给你的边的列表当中。
在线评测地址：领扣题库官网
样例1
输入: n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
输出: true.样例2
输入: n = 5 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
输出: false.算法：bfs
算法思路
- 一棵拥有n个节点的树有n-1条边，树是连通的，没有环的。
- 给定一个无向图让我们判断是否为树，我们只需要判断是否连通且无环即可。
- 我们可以从根节点出发向儿子节点进行广度优先搜索bfs，如果能遍历完所有的点，且没有环存在，那么说明这个无向图是树。
- 已知给定的边不重复，所以可以通过判断边数是否为(n - 1)条来判断是否无环。
代码思路 - 首先判断边数是否为(n - 1)条，若不是则返回false
- 然后从根节点开始进行bfs搜索
模板：*/ queue <int> q; //声明一个队列 q.push(...); //压入起始元素 while (!q.empty()) { //当队列不为空 ... = q.front(); //取出队列头 q.pop(); //弹出队列头 for (...){ if(...) { 改变状态 q.push(...); //压入队列 } } } - 最后判断是否能够遍历完所有节点，如果能说明是树，返回true。
复杂度分析 - 假设有n个点，m条边。
- 用邻接矩阵存储n个点之间的边的关系，空间复杂度为O(n^2)。
- 建图时每条边都会访问 1 次，搜索时每个点都会被询问1次，时间复杂度为O(max(n, m))。
public class Solution { /** * @param n: An integer * @param edges: a list of undirected edges * @return: true if it's a valid tree, or false */ public boolean validTree(int n, int[][] edges) { int numOfEdge = edges.length; // 判断是否为 (n - 1) 条边 if (numOfEdge != n - 1) { return false; } // adjacent[i][j]里存i与j是否相邻 int[][] adjacent = new int[n + 2][n + 2]; for (int i = 0; i < numOfEdge; i++) { int u = edges[i][0], v = edges[i][1]; adjacent[u][v] = adjacent[v][u] = 1; } // visit[i]记录i是否被访问 int[] visit = new int[n + 5]; // 0作为根结点，开始向下遍历 visit[0] = 1; int root = 0, numOfVisited = 1; Queue<Integer> q = new LinkedList<Integer>(); q.add(root); while (!q.isEmpty()) { root = q.poll(); for (int i = 0; i < n; i++) { if (adjacent[root][i] != 1) { continue; } // 如果相邻且没有被访问过，说明是儿子，加入队列 if(visit[i] == 0) { visit[i] = 1; numOfVisited++; q.add(i); } } } if(numOfVisited == n) { return true; } return false; } }更多题解参考：领扣题库官网
