Graph Valid Tree
update Jul 16, 2017 15:54
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.
Notice
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.
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.Basic Idea:
首先是树的两个性质：
#node = 1 + #edge所有node连通 （解决这个问题有两种方法，一是普通的bfs或者dfs，再就是并查集（又叫 Union Find 或 Disjoint Set））；
于是我们从这两个性质出发，先判断node和edge的个数是否符合要求，然后用一个BFS来判断是否connected。
题目中给的是node个数以及edges，我们需要先把图转换为adjacent list的形式，即Java中的：List<Set<Integer>>的形式，然后再做bfs。为了应对back edge，我们需要用一个HashSet visited 记录已经visited 的 node。另外要注意，所给的边都是directed的，我们需要将图转化为 undirected 的。
Java Code：
// 方法1，对每个V BFS，结束之后看是否已经完成所有V
class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges == null || edges.length != n - 1) return false;
List<Set<Integer>> graph = initGraph(n, edges);
// bfs, 以 0 为入口
Deque<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.addFirst(0);
visited.add(0);
while (! queue.isEmpty()) {
int v = queue.removeLast();
for (int neighbor : graph.get(v)) {
if (visited.contains(neighbor)) continue;
visited.add(neighbor);
queue.addFirst(neighbor);
}
}
return visited.size() == n;
}
private List<Set<Integer>> initGraph(int n, int[][] edges) {
List<Set<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; ++i) {
graph.add(new HashSet<Integer>());
}
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);
}
return graph;
}
}Python Code:
class Solution:
# @param {int} n an integer
# @param {int[][]} edges a list of undirected edges
# @return {boolean} true if it's a valid tree, or false
def validTree(self, n, edges):
# 先把edges list的形式转化成adjacent list的形式，即{node：neighbors}
def init_graph(n, edges):
graph = collections.defaultdict(set)
for edge in edges:
u = edge[0]
v = edge[1]
graph[u].add(v)
graph[v].add(u)
return graph
# 先生成adj list格式的graph，然后用bfs判断是否连通
if n != len(edges) + 1: return False
if n == 1: return True
graph = init_graph(n, edges)
queue = collections.deque()
visited = set()
queue.appendleft(0)
visited.add(0)
while queue:
node = queue.pop()
for neighbor in graph[node]:
if neighbor in visited:
continue
queue.appendleft(neighbor)
visited.add(neighbor)
return len(visited) == nupdate Sep 8, 2017 22:08
更新，Union Find Solution：
和前面类似的思路，只要判断两点，一是 E=V-1，二是连通，所以问题的主体就是判断全图的 v 连通。
这里我们使用并查集来解决连通性的问题，只要先将 0 ~ n-1 个 vertex 加入并查集，然后将所有的边两端的节点（u,v）进行 union 操作。只要最终并查集的 size==1 就可以说明图是连通的。
TimeComplexity: 这么做的时间复杂度虽然和之前的算法相同，但是因为我们不必使用 initGraph 函数生成希望的 List<Set<Integer>> 形式的图，所以理论上速度会更快。
Java Code:
// 方法2，传说中的 Union Find Algorithm
class Solution {
private int[] ids;
private int[] rank;
private int count;
private void makeSet(int size) {
ids = new int[size];
rank = new int[size];
count = size;
// initialize union set data structure
Arrays.fill(rank, 0);
for (int i = 0; i < size; ++i) ids[i] = i;
}
private int find(int x) {
while (ids[x] != x) {
ids[x] = find(ids[x]);
x = ids[x];
}
return x;
}
private void union(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx == rooty) return;
if (rank[rootx] < rank[rooty]) {
ids[rootx] = rooty;
} else if (rank[rootx] > rank[rooty]) {
ids[rooty] = rootx;
} else {
ids[rootx] = rooty;
rank[rooty]++;
}
count--;
}
public boolean validTree(int n, int[][] edges) {
if (edges == null || edges.length != n - 1) return false;
makeSet(n);
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
union(u, v);
}
return count == 1;
}
}update 2018-05-19 15:13:53
C++ Union Find Solution
class Solution {
vector<int> ids;
vector<int> ranks;
int count;
void makeSet(int size) {
ids.resize(size);
ranks.resize(size);
count = size;
for (int i = 0; i < size; ++i) {
ids[i] = i;
}
}
int find(int id) {
if (ids[id] == id) return id;
while (ids[id] != id) {
id = ids[id];
}
return id;
}
void _union(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx == rooty) return;
if (ranks[rootx] < ranks[rooty]) ids[rootx] = rooty;
else if (ranks[rootx] > ranks[rooty]) ids[rooty] = rootx;
else {
ids[rootx] = rooty;
ranks[rooty]++;
}
count--;
}
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
if (edges.size() != n - 1) return false;
makeSet(n);
for (auto& _pair : edges) {
_union(_pair.first, _pair.second);
}
return count == 1;
}
};