用 bfs 判断一个 graph 是否是 valid tree，有三个条件，满足其中任意两个即可： 1) n 个点 对应 n-1 条边 2) n 个点连通 3) 没有环
这里的解法用 1) 2) 做。第一个条件十分好判断。第二个条件也即判断连通性，可以用 bfs 做。
因为题目中的 input graph 是 2D array 的形式，所以在做之前需要把 2D array 转化成更易于处理的图的表现方式，我们这里用 adjacency list。
接着建立一个 queue，一个 hashset，开始做 bfs。便利结束后看一下 hashset 是否包含了所有的点，也即 flood fill 有否从根结点出发把整个图连通。
Time Complexity = O(V + E) Space Complexity = O(V)
class Solution {
public boolean validTree(int n, int[][] edges) {
if (n == 0) {
return false;
}
if (n - 1 != edges.length) {
return false;
}
// Build the graph using adjacency list
// Initialize adjacency list
List<List<Integer>> graph = new ArrayList<>();
// initialize vertices
for (int i = 0; i < n; i++) {
graph.add(i, new ArrayList<>());
}
// add edges
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);
}
// do BFS
Queue<Integer> queue = new LinkedList<>();
Set<Integer> set = new HashSet<>();
queue.offer(0);
set.add(0);
while (!queue.isEmpty()) {
int cur = queue.poll();
List<Integer> neighbors = graph.get(cur);
for (int neighbor : neighbors) {
if (!set.contains(neighbor)) {
set.add(neighbor);
queue.offer(neighbor);
}
}
}
// whether all vertexes are connected
return set.size() == n;
}
}
下面再写一下如何用 dfs 求解。实际上用 dfs 求解的时候，也要判断两件事情：
1) 是否所有点连通 2) 是否图中不存在环 （这里有一个比较好的视频是讲 how to detect cycle in undirected graph 的，主要思想是 keep 一个 visitedSet 并进行递归进行 dfs。）
如果这两个条件都满足，就可以说这个 graph 是否是 valid tree 了。
class Solution {
public boolean validTree(int n, int[][] edges) {
// Build the graph using adjacency list
// Initialize adjacency list
List<List<Integer>> graph = new ArrayList<>();
// initialize vertices
for (int i = 0; i < n; i++) {
graph.add(i, new ArrayList<>());
}
// add edges
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);
}
boolean[] visited = new boolean[n];
// do DFS
// make sure there's no cycle
if (hasCycle(0, -1, visited, graph)) {
return false;
}
// make sure all vertices are connected
for (int i = 0; i < n; i++) {
if (!visited[i]) {
return false;
}
}
return true;
}
private boolean hasCycle(int u, int parent, boolean[] visited, List<List<Integer>> graph) {
visited[u] = true;
for (int i = 0; i < graph.get(u).size(); i++) {
int v = graph.get(u).get(i);
if ( (visited[v] && parent != v) || (!visited[v] && hasCycle(v, u, visited, graph))) {
return true;
}
}
return false;
}
}
TODO