178. Graph Valid Tree#

Difficulty: Medium

Link to Problem: To see the Graph Valid Tree problem on LintCode, click here!

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.

Constraints:

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

Probelm Explanation:#

The problem is to determine whether a given set of undirected edges can form a valid tree. In this context, a “tree” is a specific type of graph with the following properties:

  1. It is a connected graph, meaning there is a path between any pair of nodes in the graph.

  2. It has no cycles, which means there are no closed loops or circuits in the graph.

  3. It has exactly n - 1 edges, where n is the number of nodes in the tree.

The problem is typically given with two pieces of information:

  1. The number of nodes (n), which are usually labeled from 0 to n-1.

  2. A list of undirected edges, where each edge is represented as a pair of nodes.

The task is to write a function or algorithm to determine whether the provided set of edges can be arranged to form a valid tree based on the properties mentioned above.

To solve this problem, you need to check the following conditions:

  1. There should be exactly n - 1 edges to ensure that the graph is connected and tree-like.

  2. There should be no cycles in the graph. If there are any cycles, the set of edges cannot form a tree.

  3. The graph should be connected, which means you can reach any node from any other node through a series of edges.

The solution typically involves using graph traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the graph and check these conditions. If all conditions are met, the given edges form a valid tree; otherwise, they do not.

Solution:#

Here’s a Python function to implement this algorithm:

def validTree(n, edges):
    if len(edges) != n - 1:
        return False  # A tree with n nodes must have n-1 edges.

    # Create an adjacency list to represent the graph.
    adj_list = {i: [] for i in range(n)}
    for u, v in edges:
        adj_list[u].append(v)
        adj_list[v].append(u)

    visited = set()

    # Define a recursive DFS function.
    def dfs(node, parent):
        if node in visited:
            return False  # If we encounter a visited node, there's a cycle.
        visited.add(node)

        for neighbor in adj_list[node]:
            if neighbor != parent:
                if not dfs(neighbor, node):
                    return False

        return True

    # Start DFS from any node (e.g., node 0).
    if not dfs(0, -1):
        return False  # If there's a cycle, it's not a valid tree.

    return len(visited) == n

Explanation:#

The validTree function checks if a given set of undirected edges forms a valid tree. A valid tree must satisfy these conditions:

  1. It has exactly n - 1 edges, where n is the number of nodes.

  2. There are no cycles in the graph.

  3. The graph is connected, meaning all nodes are reachable from any starting node.

The code accomplishes this as follows:

  • It first checks if the number of edges is equal to n - 1. If not, it immediately returns False since a tree with n nodes must have n - 1 edges to be connected.

  • It then constructs an adjacency list (adj_list) to represent the graph efficiently. This data structure stores the neighbors of each node.

  • The code uses a visited set to keep track of nodes visited during depth-first search (DFS).

  • The dfs function is a recursive function that checks for cycles in the graph. It does this by visiting nodes and marking them as visited. If it encounters a node that has already been visited (indicating a cycle), it returns False.

  • The DFS function explores the neighbors of each node, avoiding revisiting the parent node to prevent cycles.

  • After the DFS is complete, the code checks if the number of visited nodes is equal to n, ensuring the graph is connected.

  • Finally, if all conditions are met, the code returns True, indicating that the given edges form a valid tree. Otherwise, it returns False.

The code provides examples to demonstrate how to use the validTree function to check whether a set of edges forms a valid tree or not.

Test cases:#

Here’s how you can use this solution:

# Example 1
n1 = 5
edges1 = [[0, 1], [0, 2], [0, 3], [1, 4]]
print(validTree(n1, edges1))  # Output: true

True

# Example 2
n2 = 5
edges2 = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
print(validTree(n2, edges2))  # Output: false

False

Time and Space Complexity Analysis#

Let’s analyze the time and space complexities of the validTree function:

Time Complexity:

  1. Constructing the adjacency list (adj_list) takes O(E) time, where E is the number of edges in the input graph (|edges|).

  2. The DFS function, when considering all nodes, has a time complexity of O(V + E), where V is the number of nodes in the graph. This is because, in the worst case, the DFS function visits each node and each edge once.

  3. Checking if the number of visited nodes is equal to n takes O(1) time.

Overall, the time complexity of the validTree function is O(E + V) in the worst case.

Space Complexity:

  1. The adjacency list (adj_list) consumes additional space to store the graph structure, taking O(V + E) space. This is because it stores information about each node and its adjacent nodes.

  2. The visited set keeps track of visited nodes, and its space complexity is O(V) in the worst case, as there can be at most V unique nodes in the set.

  3. The depth of the function call stack during DFS can be at most V, which contributes O(V) space to the space complexity.

Overall, the space complexity of the validTree function is O(V + E) due to the adjacency list and O(V) due to the visited set and DFS call stack.

In summary, the time complexity is O(E + V), and the space complexity is O(V + E). These complexities are based on the worst-case scenario, where all nodes and edges are considered. In practical cases, the actual complexities may be smaller, depending on the specific structure of the graph.

Challenging Exercises:#

  1. Minimum Spanning Tree (MST): Implement an algorithm to find the minimum spanning tree of a connected graph using either Kruskal’s or Prim’s algorithm. Compare the MST to the original graph to determine if the original graph is a tree. This exercise reinforces the concept of tree properties.

  2. Detecting Cycles: Modify the code to not only check if the input forms a tree but also to identify and print out any cycles present in the graph if it’s not a tree. This exercise enhances your ability to detect and visualize cycles in a graph.