Graph Valid Tree

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.

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。注意树有个特征就是一个child不能有两个parent, 根平时拓扑排序找环的的差别，当然由于这道题是无向图，不用考虑这方面。这题有几个要注意的地方，比如一个树只能有一个root，如果这个树存在多个root, 那肯定无效。

由于这道题是无向图，那么我们其实可以从任意一个点开始DFS，不用必须从root，因为无向图从任意一点都可以遍历到整块部分。添加edge的时候两个方向都添就可以了，另外就是还有个注意的地方就是如果在遍历neighbors的时候，自己parent不要遍历，否则直接返回false以为有环了。总结一句就是，这种无向图每个点遍历一次就可以了，否则就意味着有环。

如果这道题换成是有向图的话，解法见下文。

复杂度

time: O(V + E), space: O(h)

代码

public class Solution {     public boolean validTree(int n, int[][] edges) {        List<Integer>[] graph = new List[n];        for (int i = 0; i < n; i++) {graph[i] = new ArrayList<Integer>();        }        for (int i = 0; i < edges.length; i++) {graph[edges[i][0]].add(edges[i][1]);graph[edges[i][1]].add(edges[i][0]);        }        boolean[] visited = new boolean[n];        if (!dfs(graph, 0, visited, -1)) {return false;        }    // 检测是否存在多个root, 如是意味着图无效        for (int i = 0; i < n; i++) {if (!visited[i]) {    return false;}        }        return true;    }    private boolean dfs(List<Integer>[] graph, int i, boolean[] visited, int prev) {        // 发现环        if (visited[i]) {return false;        }        visited[i] = true;        for (int num : graph[i]) {if (prev != num && !dfs(graph, num, visited, i)) {    return false;}        }        return true;    }}

Graph Valid Tree(Directed Edges)

Given n nodes labeled from 0 to n - 1 and a list of directed 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.
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return false.

分析

有向图要注意的地方不仅是不能有多个root存在，与上题不同的是需要从root开始遍历才能慢慢遍历到整个图，其他方面基本跟上题一样，遍历过程中一个点只能visit一次，否则即是那种一个child多个parent情况。

复杂度

time: O(V+E), space: O(h)

代码

public class Solution {    public boolean validTree(int n, int[][] edges) {        List<Integer>[] graph = new List[n];        Set<Integer> inDegree = new HashSet<>();        for (int i = 0; i < n; i++) {graph[i] = new ArrayList<Integer>();        }        for (int i = 0; i < edges.length; i++) {graph[edges[i][0]].add(edges[i][1]);inDegree.add(edges[i][1]);        }        int root = 0;        int count = 0;        for (int i = 0; i < n; i++) {if (!inDegree.contains(i)) {    root = i;    count++;}        }        if (count != 1)return false;        boolean[] visited = new boolean[n];        if (!dfs(graph, root, visited)) {return false;        }        return true;    }    private boolean dfs(List<Integer>[] graph, int i, boolean[] visited) {    // 发现环或一child多个parents        if (visited[i]) {return false;        }        visited[i] = true;        for (int num : graph[i]) {if (!dfs(graph, num, visited)) {    return false;}        }        return true;    }          }