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.

Example 1:

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:

Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: 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​

# Graph Valid Tree# DFS# Time Complexity: O(N+E), Space Complexity : O(N + E)class Solution:    def validTree(self, n: int, edges: List[List[int]]) -> bool:        if len(edges) != n - 1: return False        adj_list = [[] for _ in range(n)]        for A, B in edges:            adj_list[A].append(B)            adj_list[B].append(A)        stack = [0]        visited = {0}        while stack:            node = stack.pop()            for neighbour in adj_list[node]:                if neighbour in visited: continue                stack.append(neighbour)                visited.add(neighbour)        return len(visited) == n

BFS​

# Graph Valid Tree# BFS# Time Complexity: O(N+E), Space Complexity : O(N + E)class Solution:    def validTree(self, n: int, edges: List[List[int]]) -> bool:        if len(edges) != n - 1: return False        adj_list = [[] for _ in range(n)]        for A, B in edges:            adj_list[A].append(B)            adj_list[B].append(A)        queue = deque([0])        visited = {0}        while queue:            node = queue.popleft()            for neighbour in adj_list[node]:                if neighbour in visited: continue                queue.append(neighbour)                visited.add(neighbour)        return len(visited) == n