给出 n 个节点，标号分别从 0 到 n - 1 并且给出一个无向边的列表(给出每条边的两个顶点), 写一个函数去判断这张无向图是否是一棵树
注意事项
你可以假设我们不会给出重复的边在边的列表当中. 无向边[0, 1] 和 [1, 0]是同一条边，因此他们不会同时出现在我们给你的边的列表当中。
算法第四版上定义
当一幅含有V个结点的图G满足下面5个条件时，它就是一棵树：
1. G有V-1条边且不含有环
2. G有V-1条边且是连通的
3. G是连通图且删除任意一条边都会使它们不再连通
4. G是无环图但添加任意一条边都会产生一条环
5. G中任意一对顶点间仅存在一条简单路径（顶点序列中顶点不重复出现的路径）
样例
给出n = 5 并且 edges = [[0, 1], [0, 2], [0, 3], [1, 4]], 返回 true.
给出n = 5 并且 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], 返回 false.
判断条件
- n 个点若不存在 n-1 条边一定存在环
- 由一个点可以访问到其它所有点，点的总数为 n
代码
- BFS 判断连通性
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) {
if (n == 0) {
return false;
}
// 判断图是否是树依据上述的第二个条件
if (edges.length != n - 1) {
return false;
}
// set 用于去重，不包含重复元素的集合
Map<Integer, Set<Integer>> graph = initializeGraph(n, edges);
// bfs
// queue 里面存的是结点下标
Queue<Integer> queue = new LinkedList<>();
Set<Integer> hash = new HashSet<>();
queue.offer(0);
hash.add(0); // hashset 没有 offer 用法
// queue 结合 while 使用来保证遍历全部结点
while (!queue.isEmpty()) {
int node = queue.poll();
// foreach 用法，neighbor 是变量名
// graph.get(node) 对应的是一个集合
for (Integer neighbor : graph.get(node)) {
// hash 表用于去除重复结点，来保证队列中没有添加重复结点
// 树只能从上往下遍历，但图没有方向，A 是 B 的相邻结点，B 也是A 的相邻结点，所以要去重
if (hash.contains(neighbor)) {
continue;
}
hash.add(neighbor);
queue.offer(neighbor);
}
}
// 当存在 n-1 条边且有 n 个结点连通时说明图是树
return (hash.size() == n);
}
// 根据结点和边初始化一张图出来
private Map<Integer, Set<Integer>> initializeGraph(int n, int[][] edges) {
// set 的不包含重复元素特性特别重要，set 在后边代表的两点间建立边的关系
// 若某一点重复加了一个点两次则证明出现了环，初始化必须保证无环，算法才有意义
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
// hashset 用于存储不重复整型对象,
// hashmap 中的 put 方法用于关联指定值与指定键，
// 本行代码用于创建 n 个映射
graph.put(i, new HashSet<Integer>());
}
// 注意此处不是 n，n 代表结点数
// i 循环的是边数，边数小于 n，若写成 n 则在 i = n - 1 时代码会卡住，程序超时
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
graph.get(u).add(v);
graph.get(v).add(u);
}
// 在图中建立边的连接实际上就是建立两个整数间的不重复映射关系
// get() 返回指定键映射的值,即 graph 代表 hashset 数组,
// graph.get(v).add(u) 代表 hashset.add()
// u 和 v 代表边的两个端点在 graph.get(u) 中 u,v 代表索引值 i，
// u.add(v) 是指加一条 u 到 v 的边(graph 中下标为 u 的 set 加入
// 一个值为 v 的元素)，把题目提供的输入数据中的边数组进行处理
return graph;
}
}
- Union Find
public class Solution {
class UnionFind{
HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
UnionFind(int n){
for(int i = 0 ; i < n; i++) {
father.put(i, i);
}
}
int compressed_find(int x){
int parent = father.get(x);
while(parent!=father.get(parent)) {
parent = father.get(parent);
}
int temp = -1;
int fa = father.get(x);
while(fa!=father.get(fa)) {
temp = father.get(fa);
father.put(fa, parent) ;
fa = temp;
}
return parent;
}
void union(int x, int y){
int fa_x = compressed_find(x);
int fa_y = compressed_find(y);
if(fa_x != fa_y)
father.put(fa_x, fa_y);
}
}
/**
* @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) {
// tree should have n nodes with n-1 edges
if (n - 1 != edges.length) {
return false;
}
UnionFind uf = new UnionFind(n);
for (int i = 0; i < edges.length; i++) {
if (uf.compressed_find(edges[i][0]) == uf.compressed_find(edges[i][1])) {
return false;
}
uf.union(edges[i][0], edges[i][1]);
}
return true;
}
}
