描述

给出 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;     } } 

更多题解参考

大佬有話說 (0)