Depth-First Search
Graph Valid Tree
DESCRIPTION (inspired by Lintcode.com)
You are given an integer n and a list of undirected edges where each entry in the list is a pair of integers representing an edge between nodes 0 and n - 1. You have to write a function to check whether these edges make up a valid tree.
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.
public class Solution {
public Boolean graph_valid_tree(Integer n, int[][] edges) {
// Your code goes here
}
}Run your code to see results here
Have suggestions or found something wrong?
Explanation
In order for a graph to be a valid tree, it must satisfy the following conditions:
- 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.
We can use a depth-first search to check for these conditions. We'll start by converting the list of edges into an adjacency list. This allows us to easily find the neighbors of any node, which is required by the depth-first search algorithm.
We'll walkthrough how this solution determines that a graph with a cycle is not a valid tree when n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], which forms the following graph:
public boolean validTree(int n, int[][] edges) {List<List<Integer>> adjList = new ArrayList<>();for (int i = 0; i < n; i++) {adjList.add(new ArrayList<>());}for (int[] edge : edges) {adjList.get(edge[0]).add(edge[1]);adjList.get(edge[1]).add(edge[0]);}// Use DFS to check if the graph is a valid treeboolean[] visited = new boolean[n];if (hasCycle(adjList, 0, visited, -1)) {return false;}for (boolean v : visited) {if (!v) return false;}return true;}private boolean hasCycle(List<List<Integer>> adjList, int node, boolean[] visited, int parent) {visited[node] = true;for (int neighbor : adjList.get(node)) {if (visited[neighbor] && parent != neighbor) {return true;} else if (!visited[neighbor] &&hasCycle(adjList, neighbor, visited, node)) {return true;}}return false;}
graph valid tree
0 / 6
Depth-First Search
Next, we use a recursive function hasCycle to check for cycles in the graph. Each call to hasCycle returns true if there is a cycle connected to the input node. The function first marks the current node as visited, then recursively visits all its neighbors using depth-first search, checking for cycles. To keep track of the nodes we've visited already, we use a boolean array visited.
public boolean validTree(int n, int[][] edges) {List<List<Integer>> adjList = new ArrayList<>();for (int i = 0; i < n; i++) {adjList.add(new ArrayList<>());}for (int[] edge : edges) {adjList.get(edge[0]).add(edge[1]);adjList.get(edge[1]).add(edge[0]);}// Use DFS to check if the graph is a valid treeboolean[] visited = new boolean[n];if (hasCycle(adjList, 0, visited, -1)) {return false;}for (boolean v : visited) {if (!v) return false;}return true;}private boolean hasCycle(List<List<Integer>> adjList, int node, boolean[] visited, int parent) {visited[node] = true;for (int neighbor : adjList.get(node)) {if (visited[neighbor] && parent != neighbor) {return true;} else if (!visited[neighbor] &&hasCycle(adjList, neighbor, visited, node)) {return true;}}return false;}
build adjacency list
0 / 5
Detecting a Cycle
If at any point during our search, we encounter a node that we've already visited and is not the parent of the current node, then we've found a cycle. We return true to indicate that the graph is not a valid tree, which causes the depth-first search to terminate early, until the main function returns false.
public boolean validTree(int n, int[][] edges) {List<List<Integer>> adjList = new ArrayList<>();for (int i = 0; i < n; i++) {adjList.add(new ArrayList<>());}for (int[] edge : edges) {adjList.get(edge[0]).add(edge[1]);adjList.get(edge[1]).add(edge[0]);}// Use DFS to check if the graph is a valid treeboolean[] visited = new boolean[n];if (hasCycle(adjList, 0, visited, -1)) {return false;}for (boolean v : visited) {if (!v) return false;}return true;}private boolean hasCycle(List<List<Integer>> adjList, int node, boolean[] visited, int parent) {visited[node] = true;for (int neighbor : adjList.get(node)) {if (visited[neighbor] && parent != neighbor) {return true;} else if (!visited[neighbor] &&hasCycle(adjList, neighbor, visited, node)) {return true;}}return false;}
private boolean hasCycle(List<List<Integer>> adjList, int node, boolean[] visited, int parent) {visited[node] = true;for (int neighbor : adjList.get(node)) {if (visited[neighbor] && parent != neighbor) {return true;} else if (!visited[neighbor] &&hasCycle(adjList, neighbor, visited, node)) {return true;}}return false;}
private boolean hasCycle(List<List<Integer>> adjList, int node, boolean[] visited, int parent) {visited[node] = true;for (int neighbor : adjList.get(node)) {if (visited[neighbor] && parent != neighbor) {return true;} else if (!visited[neighbor] &&hasCycle(adjList, neighbor, visited, node)) {return true;}}return false;}
private boolean hasCycle(List<List<Integer>> adjList, int node, boolean[] visited, int parent) {visited[node] = true;for (int neighbor : adjList.get(node)) {if (visited[neighbor] && parent != neighbor) {return true;} else if (!visited[neighbor] &&hasCycle(adjList, neighbor, visited, node)) {return true;}}return false;}
private boolean hasCycle(List<List<Integer>> adjList, int node, boolean[] visited, int parent) {visited[node] = true;for (int neighbor : adjList.get(node)) {if (visited[neighbor] && parent != neighbor) {return true;} else if (!visited[neighbor] &&hasCycle(adjList, neighbor, visited, node)) {return true;}}return false;}
iterate over neighbors
0 / 5
If no cycle is found, then we have to make sure there is a single connected component. We do this by checking if all nodes have been visited. If so, the graph is a valid tree and we return true. If not, then the graph is not a valid tree and we return false.
Animated Solution
public boolean validTree(int n, int[][] edges) {List<List<Integer>> adjList = new ArrayList<>();for (int i = 0; i < n; i++) {adjList.add(new ArrayList<>());}for (int[] edge : edges) {adjList.get(edge[0]).add(edge[1]);adjList.get(edge[1]).add(edge[0]);}// Use DFS to check if the graph is a valid treeboolean[] visited = new boolean[n];if (hasCycle(adjList, 0, visited, -1)) {return false;}for (boolean v : visited) {if (!v) return false;}return true;}private boolean hasCycle(List<List<Integer>> adjList, int node, boolean[] visited, int parent) {visited[node] = true;for (int neighbor : adjList.get(node)) {if (visited[neighbor] && parent != neighbor) {return true;} else if (!visited[neighbor] &&hasCycle(adjList, neighbor, visited, node)) {return true;}}return false;}
graph valid tree
0 / 27
Complexity Analysis
For this problem, let n be the number of nodes and e be the number of edges.
What is the time complexity of this solution?
O(2ⁿ)
O(n + e)
O(m * n * 4^L)
O(m * n)