Depth-First Search
Graph Valid Tree
DESCRIPTION (inspired by Lintcode.com)
You are given an integer n representing a graph with n nodes labeled from 0 to n - 1, and a list of undirected edges where each entry in the list is a pair of integers [u, v] representing an edge between nodes u and v. You have to write a function to check whether these edges make up a valid tree.
Every node from 0 to n - 1 is part of the graph, even if it does not appear in any edge.
There will be no duplicate edges in the edges list. (i.e. [0, 1] and [1, 0] will not appear together in the list).
Input:
n = 4 edges = [[0, 1], [2, 3]]
Output:
false # the graph is not connected.
Explanation
- The graph must contain no cycles.
- There should be a single connected component - if we start from any node, we should be able to reach all other nodes.
def validTree(n, edges):adj_list = [[] for _ in range(n)]for u, v in edges:adj_list[u].append(v)adj_list[v].append(u)# Use DFS to check if the graph is a valid treevisited = [False] * nif hasCycle(adj_list, 0, visited, -1):return Falsereturn all(visited)def hasCycle(adj_list, node, visited, parent):visited[node] = Truefor neighbor in adj_list[node]:if visited[neighbor] and parent != neighbor:return Trueelif not visited[neighbor] and \hasCycle(adj_list, neighbor, visited, node):return Truereturn False
graph valid tree
0 / 6
Depth-First Search
def validTree(n, edges):adj_list = [[] for _ in range(n)]for u, v in edges:adj_list[u].append(v)adj_list[v].append(u)# Use DFS to check if the graph is a valid treevisited = [False] * nif hasCycle(adj_list, 0, visited, -1):return Falsereturn all(visited)def hasCycle(adj_list, node, visited, parent):visited[node] = Truefor neighbor in adj_list[node]:if visited[neighbor] and parent != neighbor:return Trueelif not visited[neighbor] and \hasCycle(adj_list, neighbor, visited, node):return Truereturn False
build adjacency list
0 / 5
Detecting a Cycle
def validTree(n, edges):adj_list = [[] for _ in range(n)]for u, v in edges:adj_list[u].append(v)adj_list[v].append(u)# Use DFS to check if the graph is a valid treevisited = [False] * nif hasCycle(adj_list, 0, visited, -1):return Falsereturn all(visited)def hasCycle(adj_list, node, visited, parent):visited[node] = Truefor neighbor in adj_list[node]:if visited[neighbor] and parent != neighbor:return Trueelif not visited[neighbor] and \hasCycle(adj_list, neighbor, visited, node):return Truereturn False
def hasCycle(adj_list, node, visited, parent):visited[node] = Truefor neighbor in adj_list[node]:if visited[neighbor] and parent != neighbor:return Trueelif not visited[neighbor] and \hasCycle(adj_list, neighbor, visited, node):return Truereturn False
def hasCycle(adj_list, node, visited, parent):visited[node] = Truefor neighbor in adj_list[node]:if visited[neighbor] and parent != neighbor:return Trueelif not visited[neighbor] and \hasCycle(adj_list, neighbor, visited, node):return Truereturn False
def hasCycle(adj_list, node, visited, parent):visited[node] = Truefor neighbor in adj_list[node]:if visited[neighbor] and parent != neighbor:return Trueelif not visited[neighbor] and \hasCycle(adj_list, neighbor, visited, node):return Truereturn False
def hasCycle(adj_list, node, visited, parent):visited[node] = Truefor neighbor in adj_list[node]:if visited[neighbor] and parent != neighbor:return Trueelif not visited[neighbor] and \hasCycle(adj_list, neighbor, visited, node):return Truereturn False
iterate over neighbors
0 / 5
Animated Solution
def validTree(n, edges):adj_list = [[] for _ in range(n)]for u, v in edges:adj_list[u].append(v)adj_list[v].append(u)# Use DFS to check if the graph is a valid treevisited = [False] * nif hasCycle(adj_list, 0, visited, -1):return Falsereturn all(visited)def hasCycle(adj_list, node, visited, parent):visited[node] = Truefor neighbor in adj_list[node]:if visited[neighbor] and parent != neighbor:return Trueelif not visited[neighbor] and \hasCycle(adj_list, neighbor, visited, node):return Truereturn False
graph valid tree
0 / 27
Complexity Analysis
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n + e) Building the adjacency list takes O(e) time, and the DFS visits each node once and traverses each edge once, taking O(n + e) time.
Space Complexity: O(n + e) The adjacency list stores all edges, taking O(n + e) space. The visited array takes O(n) space, and the recursion stack can grow up to O(n) deep in the worst case.