## Graph Valid Tree

###### DESCRIPTION (credit 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 1 and n. 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).

###### EXAMPLES

Input:

`n = 4 edges = [[0, 1], [2, 3]]`

Output:

`false # the graph is not connected.`

Run your code to see results here

## 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:

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

### 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.

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

### 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.

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

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

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

Loading comments...