leetcode解题: Graph Valid Tree (261)

发表于 | 分类于

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 = 5 and edges = [[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.

总结

此题用Union Find最简便，DFS 和 BFS 都可以。

解法1： DFS

按照题目意思，这是一个undirectedgraph判定是否是tree的问题，那么一个无向图要满足两个条件。一个是要全连通，另一个是要没有环。
基本思想是用DFS遍历，如果遍历到之前遇过的节点说明有环。遍历之后如果还有没有遍历过的节点那么就不是全通图。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class Solution {
    public boolean validTree(int n, int[][] edges) {
		// Construct the graph using hashmap
		// Empty Tree
		// Need to satisfy two conditions, 1) all nodes are linked 2) no cycle in the list
		if ((edges.length == 0 || edges[0].length == 0)) {
		    return n == 1 || n == 0;
		}
		HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
		for (int[] edge: edges) {
			if (!map.containsKey(edge[0])) {
				map.put(edge[0], new ArrayList<Integer>());
			}
			if (!map.containsKey(edge[1])) {
				map.put(edge[1], new ArrayList<Integer>());
			}
			map.get(edge[0]).add(edge[1]);
			map.get(edge[1]).add(edge[0]);
		}
	
		List<Boolean> visited = new ArrayList<Boolean>(n);
		for (int i = 0; i < n; ++i) {
		    visited.add(false);
		}
		boolean res = dfs(map, visited, 0, -1);
		if (!res) {
			return false;
		}
		for (boolean node: visited) {
			if (!node) {
				return false;
			}
		}
		return true;
    }
	private boolean dfs(HashMap<Integer, List<Integer>> map, List<Boolean> visited, int cur, int prev) {
		if (visited.get(cur)) {
			return false;
		}
		// prev records the node that link to the current dfs function call
		visited.set(cur, true);
		List<Integer> connected = map.get(cur);
		if (connected == null) {
		    return false;
		}
		for (int node: connected) {
		    if (node != prev) {
    			boolean res = dfs(map, visited, node, cur);
    			if (!res) {
    				return false;
    			}
		    }
		}
		return true;
	}
			
}

解法2： BFS

BFS 的思想和DFS的基本一致。要注意的是，在存储图的信息的时候，用一个Set比较方便。因为之后当我们在扫描一个节点连接的节点时，要删除对应节点中的edge（就是a连向b，那么b的相连node中一定有a，为了避免出现再遇到a，需要把对应的a从b相连的节点的list中删除，用set比较方便的解决此问题）
同时用一个set来维护已经访问过的节点。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
	public boolean validTree(int n, int[][] edges) {
		if (edges.length == 0 || edges[0].length == 0) {
			return n == 1 || n == 0;
		}
		
		HashMap<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
		for (int[] edge: edges) {
			if (!map.containsKey(edge[0])) {
				map.put(edge[0], new HashSet<Integer>());
			}
			if (!map.containsKey(edge[1])) {
				map.put(edge[1], new HashSet<Integer>());
			}
			map.get(edge[0]).add(edge[1]);
			map.get(edge[1]).add(edge[0]);
		}
		
		// Start BFS
		Queue<Integer> queue = new LinkedList<Integer>();   
		Set<Integer> set = new HashSet<Integer>();
		queue.offer(0);
		set.add(0);
		while (!queue.isEmpty()) {
		    int node = queue.poll();
		    Set<Integer> elements = map.get(node);
		    if (elements != null) {
		        for (int element: elements) {
		            if (set.contains(element)) {
		                return false;
		            }
		            queue.offer(element);
		            set.add(element);
		            map.get(element).remove(node);
		        }
		    }
		    
		}
		
		// Check the length of Set
		return set.size() == n;
	
	}
}

解法3： Union Find

Union Find的算法就不详述了。Union Find很适合来解决Graph找circle的问题。 这里的思路是如果两个node同属于一个parent那么就有circle存在。
如果不属于同一个parent，那么就把他们union起来成为一个group.
要注意的是最后如果没有出现circle，要比较一下是否每一个node都连接起来了，用edges.length == n - 1就可以判断
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public boolean validTree(int n, int[][] edges) {
        
        
        int[] parents = new int[n];
        Arrays.fill(parents, -1);
        for (int[] edge: edges) {
            int x = find(parents, edge[0]);
            int y = find(parents, edge[1]);
            if (x == y) {
                return false;
            }
            parents[x] = y;
        }
        
        return edges.length == n - 1;
        
    }
    
    int find(int[] parents, int x) {
        while (parents[x] != -1) x = parents[x];
        return x;
    }
}