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.
For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
Hint:
- Given
n = 5andedges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree? - According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
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来辅助遍历，这里我们没有用一维向量来标记节点是否访问过，而是用了一个set，如果遍历到一个节点，在set中没有，则加入set，如果已经存在，则返回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; } };
本文转自博客园Grandyang的博客，原文链接：图验证树[LeetCode] Graph Valid Tree ，如需转载请自行联系原博主。
