Graph valid tree#
Description#
- 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.
Example#
1Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
2
3Given 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 inedges.
- Treating input as graph, making sure no cycles and one connected component.
- Check for cycle and connectness in Graph can be done by DFS, BFS and Union-find
Python Solution#
1from collections import defaultdict
2
3
4class Solution(object):
5 def validTree(self, n, edges):
6 """
7 A graph is a tree:
8 1. no cycle
9 2. all connected
10 :type n: int
11 :type edges: List[List[int]
12 :rtype: bool
13 """
14 if not edges:
15 return n in (0, 1)
16
17 V = defaultdict(list)
18 for e in edges:
19 V[e[0]].append(e[1])
20 V[e[1]].append(e[0])
21
22 visited = set()
23 pathset = set()
24 if not self.dfs(V, edges[0][0], None, pathset, visited):
25 return False
26
27 return len(visited) == n
28
29 def dfs(self, V, v, pi, pathset, visited):
30 if v in pathset:
31 return False
32
33 pathset.add(v)
34 for nbr in V[v]:
35 if nbr != pi: # since undirected graph
36 if not self.dfs(V, nbr, v, pathset, visited):
37 return False
38
39 pathset.remove(v)
40 visited.add(v)
41 return True