Graph Valid Tree
Problem Statement
You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph. Return true if the graph is a valid tree, or false otherwise.
Constraints:
- 1 <= n <= 2000
- 0 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- There are no self-loops or repeated edges
Input Format:
- An integer n representing the number of nodes
- A 2D array edges where each edge is [ai, bi]
Output Format:
- Return true if the graph is a valid tree, or false otherwise
Examples:
Example 1:
Input:
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output:
true
Explanation:
The graph is a tree with 5 nodes and 4 edges, which satisfies the condition for a tree.
Example 2:
Input:
n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output:
false
Explanation:
The graph has a cycle between nodes 1-2-3-1, so it's not a tree.
Example 3:
Input:
n = 3, edges = [[0,1],[1,2]]
Output:
true
Explanation:
The graph is a valid tree with 3 nodes and 2 edges.
Solutions
DFS Approach
Use depth-first search to check if the graph has cycles and if all nodes are reachable.
Union-Find Approach
Use Union-Find to detect cycles in the graph.
BFS Approach
Use breadth-first search to check for connectivity and cycles.
Algorithm Walkthrough
Example input:
Step-by-step execution:
- Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
- Check condition 1: edges.length (4) === n-1 (5-1=4)? true
- Build adjacency list:
- Node 0: [1, 2, 3]
- Node 1: [0, 4]
- Node 2: [0]
- Node 3: [0]
- Node 4: [1]
- Start DFS from node 0:
- Mark node 0 as visited
- Visit neighbor 1:
- Mark node 1 as visited
- Visit neighbor 0: Already visited but it's the parent, skip
- Visit neighbor 4:
- Mark node 4 as visited
- Visit neighbor 1: Already visited but it's the parent, skip
- Visit neighbor 2:
- Mark node 2 as visited
- Visit neighbor 0: Already visited but it's the parent, skip
- Visit neighbor 3:
- Mark node 3 as visited
- Visit neighbor 0: Already visited but it's the parent, skip
- Check if all nodes visited: Visited nodes = [0, 1, 4, 2, 3], size = 5, n = 5
- Return true (the graph is a valid tree)
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the graph structure and the DFS/BFS traversal process to check if it is a valid tree.
Key visualization elements:
- current node
- visited nodes
- cycle detection
Similar Questions
Course Schedule
MediumThere are a total of numCourses courses you have to take, labeled from 0 to numCourses-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]. Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Number of Connected Components in an Undirected Graph
MediumYou have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph. Return the number of connected components in the graph.
Implementation Notes
This problem demonstrates important graph theory concepts. A graph is a valid tree if it has exactly n-1 edges, has no cycles, and all nodes are connected. The Union-Find solution is particularly elegant for this problem.