Check If Graph Is a Valid Tree
Question (LC.261)
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), check whether these edges make up a valid tree.
Assume that no duplicate edges will appear in edges.
Example
Input: n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Graph: ->1->4
0->2
->3
Output: true it is a valid tree
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Graph: 0
|
1
/ \ \
2 | 4
\ /
3
Output: A tree cannot contain cycles. False.
Analysis
What differentiates a tree from a graph? First, a tree has to be a DAG. Moreover, nodes can only have one parent (unlike DAG). Here are the things we want to test:
- The graph is acyclic
- The graph is connected
DFS
This should be the most intuitive approach. We want to see if the component is connected and without any cycle.
Approach:
Step 1 Build graph (adjacency list)
Step 2 DFS the graph from any vertex (detect cycle)
Step 3 check to see if the component is connected
Main function
public boolean validTree(int n, int[][] edges) {
// Step 0 edge cases and quick check
// invalid graph
if (n < 1) {
return false;
}
// not all nodes are connected or over connected
if (edges.length + 1 != n) {
return false;
}
// Step 1 build a graph
Map<Integer, List<Integer>> graph = new HashMap<>();
buildGraph(graph, edges, n);
// Step 2 DFS the graph (check cycle)
// Map<V, Parent(V)> will work in the general case
Set<Integer> visited = new HashSet<>();
// start from anywhere is fine cause undirected graph
if (cycleDFS2(graph, 0, -1, visited)) {
return false;
}
// Step 3 Check the component is connected
return visited.size() == n;
}
Build (Directed) Graph
private void buildGraph(Map<Integer, List<Integer>> graph, int[][] edges, int n) {
// init vertices
for (int i = 0; i < n; i++) {
graph.put(i, new ArrayList<>());
}
// add undirected edges
for (int[] edge : edges) {
// need to add both directions
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
}
DFS and Cycle Detection
private boolean cycleDFS2(Map<Integer, List<Integer>> graph,
Integer visit, Integer parent, Set<Integer> visited) {
visited.add(visit);
for (Integer neighbor : graph.get(visit)) {
if (visited.contains(neighbor) && !neighbor.equals(parent)) {
return true;
}
if (!visited.contains(neighbor) &&
cycleDFS2(graph, neighbor, visit, visited)) {
return true;
}
}
return false;
}
BFS
If the graph is neighbor under connected nor over connected, then we can try to explore the whole graph from a node. If we explored all the nodes on this graph (connected), then it is acyclic. Otherwise, it has cycles and it's not connected.
Main function
public boolean validTree(int n, int[][] edges) {
// Step 0 check over/under connected
if (n < 1 || edges.length + 1 != n) {
return false;
}
// Step 1 build a graph
Map<Integer, List<Integer>> graph = new HashMap<>();
buildGraph(graph, edges, n);
// Step 2 BFS the graph
int explored = bfsExplore(graph);
// Step 3 Check the component is connected
System.out.println(explored);
return explored == n;
}
BFS Explore
private int bfsExplore(Map<Integer, List<Integer>> graph) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
int explored = 0;
queue.offer(0);
visited.add(0);
while (!queue.isEmpty()) {
Integer current = queue.poll();
explored++;
for (Integer neighbor : graph.get(current)) {
if (!visited.contains(neighbor)) {
queue.offer(neighbor);
visited.add(neighbor);
}
}
}
return explored;
}
Note 1: We have to add visited after offer bucause some elements can still be in queue but not processed yet. We don't want to visit the same node again. Note 2: Stay away from Integer and other wrappers if you can since they are all immutable.
Union Find
The solution can be very elegant using this approach. The idea to find two vertices (v1, v2) first. If they don't belong to the same set (no cycle), then union them.