Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
Example 1:
Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true
Example 2:
Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false
Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges.
这道题给了一个无向图，让我们来判断其是否为一棵树，如果是树的话，所有的节点必须是连接的，也就是说必须是连通图，而且不能有环，所以焦点就变成了验证是否是连通图和是否含有环。首先用 DFS 来做，根据 pair 来建立一个图的结构，用邻接链表来表示，还需要一个一位数组v来记录某个结点是否被访问过，然后用 DFS 来搜索结点0，遍历的思想是，当 DFS 到某个结点，先看当前结点是否被访问过，如果已经被访问过，说明环存在，直接返回 false，如果未被访问过，现在将其状态标记为已访问过，然后到邻接链表里去找跟其相邻的结点继续递归遍历，注意还需要一个变量 pre 来记录上一个结点，以免回到上一个结点，这样遍历结束后，就把和结点0相邻的节点都标记为 true，然后再看v里面是否还有没被访问过的结点，如果有，则说明图不是完全连通的，返回 false，反之返回 true，参见代码如下：
解法一：
// DFS
class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<vector<int>> g(n, vector<int>());
vector<bool> v(n, false);
for (auto a : edges) {
g[a.first].push_back(a.second);
g[a.second].push_back(a.first);
}
if (!dfs(g, v, 0, -1)) return false;
for (auto a : v) {
if (!a) return false;
}
return true;
}
bool dfs(vector<vector<int>> &g, vector<bool> &v, int cur, int pre) {
if (v[cur]) return false;
v[cur] = true;
for (auto a : g[cur]) {
if (a != pre) {
if (!dfs(g, v, a, cur)) return false;
}
}
return true;
}
};
下面来看 BFS 的解法，思路很相近，需要用 queue 来辅助遍历，这里没有用一维向量来标记节点是否访问过，而是用了一个 HashSet，如果遍历到一个节点，在 HashSet 中没有，则加入 HashSet，如果已经存在，则返回false，还有就是在遍历邻接链表的时候，遍历完成后需要将结点删掉，参见代码如下：
解法二：
// BFS
class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<unordered_set<int>> g(n, unordered_set<int>());
unordered_set<int> s{{0}};
queue<int> q{{0}};
for (auto a : edges) {
g[a.first].insert(a.second);
g[a.second].insert(a.first);
}
while (!q.empty()) {
int t = q.front(); q.pop();
for (auto a : g[t]) {
if (s.count(a)) return false;
s.insert(a);
q.push(a);
g[a].erase(t);
}
}
return s.size() == n;
}
};
我们再来看 Union Find 的方法，这种方法对于解决连通图的问题很有效，思想是遍历节点，如果两个节点相连，将其 roots 值连上，这样可以找到环，初始化 roots 数组为 -1，然后对于一个 pair 的两个节点分别调用 find 函数，得到的值如果相同的话，则说明环存在，返回 false，不同的话，将其 roots 值 union 上，参见代码如下：
解法三：
// Union Find
class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<int> roots(n, -1);
for (auto a : edges) {
int x = find(roots, a.first), y = find(roots, a.second);
if (x == y) return false;
roots[x] = y;
}
return edges.size() == n - 1;
}
int find(vector<int> &roots, int i) {
while (roots[i] != -1) i = roots[i];
return i;
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/261
类似题目：
Number of Connected Components in an Undirected Graph
参考资料：
https://leetcode.com/problems/graph-valid-tree/
https://leetcode.com/problems/graph-valid-tree/discuss/69018/AC-Java-Union-Find-solution
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
