Graph Valid Tree

A graph is a valid tree if and only if it has exactly ( n - 1 ) edges, and there is a way to traverse from one node to any other node. If a graph has more than or fewer than ( n - 1 ) edges, it can’t be a valid tree.

Here’s a simple step-by-step method to determine if a given graph is a valid tree:

  1. Check the Number of Edges: If the number of edges is not equal to ( n - 1 ), return false.
  2. Build an Adjacency List: Create an adjacency list from the given edges to represent the graph.
  3. Perform Depth-First Search (DFS): Perform a DFS to see if you can visit all the nodes. Keep track of visited nodes to avoid cycles.
  4. Check if All Nodes Were Visited: After the DFS, if there are any nodes that were not visited, it means the graph is not connected, so return false.
  5. If all the above conditions are satisfied, return true.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        # Build the adjacency list
        graph = collections.defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        # DFS to check if the graph is connected
        visited = [False] * n
        stack = [0] # Start DFS from node 0
        while stack:
            node = stack.pop()
            if not visited[node]:
                visited[node] = True
                stack.extend(neighbor for neighbor in graph[node] if not visited[neighbor])

        return all(visited) # Return true if all nodes were visited

Key Insights

  • A valid tree must have exactly ( n - 1 ) edges.
  • A valid tree must be connected, meaning there is a path between every pair of nodes.
  • DFS is a convenient way to check if all nodes are connected.
  • If any node is not visited after a complete DFS traversal, it means that the graph is not connected, and thus it is not a valid tree.

title: Graph Valid Tree excerpt: Given n nodes labeled from 0 to n-1 and a list of undirected edges, check whether these edges make up a valid tree. tags: cycle-detection

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Example 1:

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:
Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges.

Thought Process

Define the Interface

  • Input: array of integers (edges), n - number of nodes
  • Output: boolean

Identify the Invariants

  • Number of nodes will not change
  • Edges will also remain the same
  • You cannot visit a node more than once

Identify the constraints

  • If we have 5 nodes, we can have only n-1 edges if it is a graph valid tree

Classify the Problem

  • Graph Traversal

Analyze the Examples

Example 1

3
|
0 ---- 1 ---- 4
|
2

We should always have n-1 edges to return true. Return true (we have n-1 edges for n nodes - no cycle)

Example 2

0 ---- 1 ---- 2 ---- 3
       |
       4

Return false. Because we have a cycle in the graph. You have 5 edges and 5 nodes (you have a cycle)

Edge Case

[[0,1], [0,3], [1,4]]

0 ---- 1 ---- 4
|
3      2

If you have two components then return false If you cannot reach a node, return false.

We can have more 0 or more neighbors for a given node.

Time and Space Complexity

Time: O(V+E) Space: O(N) + O(N) (for recursion)

Solution Outline

  1. Check for the edge case and return false if it is edge case.

  2. Convert the edges to adjacency list.

  3. Traverse the graph Explore all the neighbors Keep track of visited nodes Detect the cycle

    0 1 2 3 4 [t ,t ,f ,f, f]

  4. Return whether the graph has cycle or not

[0] -> [1,2,3] [1] -> [4, 0] [2] -> [0] [3] -> [0] [4] -> [1]

Key Takeaways

  • Break down the problem into smaller subproblems
    • Creating the adjacency list from edges
    • Graph traversal dfs can be replace with bfs
    • Iterative traversal will also work
  • Identify the invariant
  • Express the invariant in the code to avoid infinite recursion
  • Undirected graph You can to create the connection both ways when you create the adjacency list

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def adjacency_list(n, edges)
  list = (0...n).map {|node| [node, []]}.to_h  
  
  edges.each_with_index do |edge, index|
    list[edge[0]] << edge[1]
    list[edge[1]] << edge[0]
  end
  
  list
end

def dfs(list, current, seen)
  seen[current] = true 
   
  for neighbor in list[current]
    # Express the invariant
    if !seen[neighbor]
      dfs(list, neighbor, seen)
    end
  end
end

# @param {Integer} n
# @param {Integer[][]} edges
# @return {Boolean}
def valid_tree(n, edges)
  if edges.size != n-1
    return false
  end
  
  list = adjacency_list(n, edges)  
  
  seen = [false] * n
  dfs(list, 0, seen)
  seen.all?{|i| i}
end

0 1 2 3 4 [t,t,f,f,f]

Define the Interface

  • Input: array of integers (edges), n - number of nodes
  • Output: boolean

Identify the Invariants

  • number of nodes will not change
  • edges will also remain the same
  • You cannot visit a node more than once

Identify the constraints

  • If we have 5 nodes, we can have only n-1 edges if it is a graph valid tree

Search the Problem Space

Classify the Problem

  • Graph Traversal

Analyze the Examples

Example 1

3 | 0 —- 1 —- 4 | 2

We should always have n-1 edges to return true.

Return true (we have n-1 edges for n nodes - no cycle)

Example 2

0 —- 1 —- 2 —- 3 | 4

Return false Because we have a cycle in the graph. You have 5 edges and 5 nodes (you have a cycle)

Edge Case

[[0,1], [0,3], [1,4]]

0 —- 1 —- 4 | 3 2

If you have two components then return false If you cannot reach a node, return false.

Solve the Problem by Hand

Describe the Pattern

We can have more 0 or more neighbors for a given node.

Brute Force Approach

Analyze Time and Space Complexity

Time: O( ) Space: O( )

Outline the Solution

  1. Check for the edge case and return false if it is edge case
  2. Convert the edges to adjacency list
  3. Traverse the graph Explore all the neighbors Keep track of visited nodes Detect the cycle
  4. Return whether the graph has cycle or not

[0] -> [1,2,3] [1] -> [4, 0] [2] -> [0] [3] -> [0] [4] -> [1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

def adjacency_list(n, edges)
  list = (0...n).map {|node| [node, []]}.to_h  
  edges.each_with_index do |edge, index|
     list[edge[0]] << edge[1]
     list[edge[1]] << edge[0]
  end
  list
end

def dfs(list, current, seen)
   seen[current] = true 
   
    for neighbor in list[current]
    # Express the invariant
        if !seen[neighbor]
            dfs(list, neighbor, seen)
        end
    end
end

# @param {Integer} n
# @param {Integer[][]} edges
# @return {Boolean}
def valid_tree(n, edges)
  if edges.size != n-1
      return false
  end
  list = adjacency_list(n, edges)  
  
  seen = [false] * n
  dfs(list, 0, seen)
  seen.all?{|i| i}
end