Graph Valid Tree

Updated on 02 June, 2025
Graph Valid Tree header image

Problem Statement

In graph theory, a fundamental question often asked is whether a given set of connections between nodes forms a valid tree. A tree is a type of graph that is connected and acyclic, meaning it has no cycles, and there exists exactly one path between any two nodes. In the context of this problem, you are provided with n nodes labeled from 0 to n - 1 and a list of edges where each edge [ai, bi] represents an undirected link between nodes ai and bi. Your task is to determine if the described structure forms a valid tree. You should return true if it forms a tree, and false otherwise. This involves ensuring that all nodes are connected without any cycles.

Examples

Example 1

Input:

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

Output:

true

Example 2

Input:

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

Output:

false

Constraints

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • There are no self-loops or repeated edges.

Approach and Intuition

To determine if the provided edges and nodes form a valid tree, we can employ the following approaches based on graph theory:

  1. Check for Cycles using Union-Find (Disjoint Set Union):

    • This algorithm helps manage a partition of a set into disjoint (non-overlapping) subsets.
    • Initialize each node as its own parent to signify that each node is its own root.
    • For each edge, combine the sets (or trees) containing the two nodes of the edge. If they are already in the same set, a cycle is detected.
  2. Check for Cycles using Depth-First Search (DFS):

    • Start DFS from any node and keep track of visited nodes.
    • If during DFS traversal you encounter a node that has already been visited and is not the parent of the current node, a cycle exists.
    • Also track the parent of each node to prevent mistaking a visited parent node as a cycle.
  3. Connected Components:

    • After using either DFS or Union-Find to ensure there are no cycles, count the number of connected components.
    • For the graph to be a single valid tree, it should exactly have one connected component which includes all nodes.
  4. Matching Number of Edges and Nodes:

    • A theory in graph states that for a cluster of nodes to be a tree, the number of edges should be exactly one less than the number of nodes (edges = nodes - 1).
    • If the count does not match this rule, it is not a tree regardless of the presence of cycles or disjoint sets.

Utilizing the Constraints

Given the constraints (1 <= n <= 2000 and 0 <= edges.length <= 5000), the methods above are computationally feasible. Union-Find and DFS both typically operate in near-linear time relative to the number of nodes and edges, making them efficient for this problem's limits.

Taking an example for better intuition:

  • Example 1:
    Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
    Output: true
    Explanation: Each node is connected to at least one other node, and no cycles are formed (4 edges for 5 nodes).

  • Example 2:
    Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
    Output: false
    Explanation: The edges [1, 2] and [1, 3] form a cycle, thus invalidating it as a tree.

This summarizes how to test if the given set forms a valid tree using the concepts of cycles, connected components, and edge-node count matching.

Solutions

  • Java
  • Python
java
class DisjointSet {

    private int[] leader;
    private int[] rank;

    public DisjointSet(int size) {
        leader = new int[size];
        rank = new int[size];
        for (int index = 0; index < size; index++) {
            leader[index] = index;
            rank[index] = 1;
        }
    }

    public int find(int x) {
        int root = x;
        while (leader[root] != root) {
            root = leader[root];
        }
        while (x != root) {
            int next = leader[x];
            leader[x] = root;
            x = next;
        }
        return root;
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        if (rank[rootX] < rank[rootY]) {
            leader[rootX] = rootY;
            rank[rootY] += rank[rootX];
        } else {
            leader[rootY] = rootX;
            rank[rootX] += rank[rootY];
        }
        return true;
    }
}

class GraphValidation {

    public boolean isValidTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        DisjointSet ds = new DisjointSet(n);
        for (int[] edge : edges) {
            if (!ds.union(edge[0], edge[1])) {
                return false;
            }
        }
        return true;
    }

}

The provided Java code defines two classes, DisjointSet and GraphValidation, to determine if a given graph represents a valid tree. Here's a breakdown of the solution approach:

  • DisjointSet Class:

    • Implements a Union-Find data structure using path compression and union by rank to help in efficiently managing and merging sets.
    • Constructor (DisjointSet): Initializes the leader and rank arrays. Each node is its own leader initially, and all ranks are set to 1.
    • find method: Retrieves the root leader of a node, performing path compression along the way to flatten the structure, improving future search operations.
    • union method: Merges two sets identified by nodes x and y. Uses the root of these nodes and merges smaller ranked trees under larger ranked ones to maintain balance. Returns false if the nodes are already connected, indicating a cycle.
  • GraphValidation Class:

    • Contains the isValidTree method to check if the input graph represented as n nodes and a list of edges defines a valid tree.
    • isValidTree Method:
      • Checks if the number of edges is exactly one less than the number of nodes, a necessary condition for a valid tree.
      • Utilizes the DisjointSet to process each edge, trying to union the nodes of the edge.
      • If a union operation returns false at any point, it signifies the presence of a cycle, making the structure not a valid tree.
      • If all edges process without detecting a cycle, and the number of edges is correct, the structure is considered a valid tree.

In essence, this code effectively checks for the key properties of a tree in a graph, such as connectivity and the absence of cycles, using a Union-Find structure with optimizations for efficient set operations.

python
class DisjointSetUnion:

    def __init__(self, size):
        self.leader = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, x):
        if self.leader[x] != x:
            self.leader[x] = self.find(self.leader[x])
        return self.leader[x]

    def merge(self, x, y):
        lead_x = self.find(x)
        lead_y = self.find(y)
        if lead_x == lead_y:
            return False
        if self.rank[lead_x] < self.rank[lead_y]:
            self.leader[lead_x] = lead_y
            self.rank[lead_y] += self.rank[lead_x]
        else:
            self.leader[lead_y] = lead_x
            self.rank[lead_x] += self.rank[lead_y]
        return True

class Solution:
    def isValidGraph(self, node_count: int, connections: List[List[int]]) -> bool:
        if len(connections) != node_count - 1:
            return False

        dsu = DisjointSetUnion(node_count)

        for node1, node2 in connections:
            if not dsu.merge(node1, node2):
                return False

        return True

The Python3 solution provided uses the Disjoint Set Union (DSU) data structure to determine if a given graph forms a valid tree. The graph's validity as a tree is confirmed through two conditions:

  • The graph must exactly have node_count - 1 connections to form a valid tree without any cycles.
  • All nodes must be connected in a single component.

Key steps and features of the implementation are as follows:

  • Initialization of DSU: A class DisjointSetUnion is initialized with each node being its own leader and having an initial rank of 1. These ranks help in optimizing the union operations by always attaching the smaller tree under the larger tree, thus keeping the depth of the tree minimal.
  • Functions in DSU:
    • find: This method uses path compression. When finding the leader of a node, it sets the leader of each traversed node directly to the root leader. This optimizes future operations involving these nodes.
    • merge: It connects two nodes. If they share the same leader, a cycle is detected, and it returns False. Otherwise, it merges the sets by size and updates ranks accordingly, returning True to indicate a successful merge without a cycle.
  • Graph Validity Check: The isValidGraph method first checks the number of connections. It then iterates through each connection, attempting to merge the components of the two nodes involved. If any merge attempt returns False, it indicates a cycle, and the function returns False. If all merges are successful, and the total connections match node_count - 1, it confirms that the graph is a valid tree.

This structured and efficient approach using DSU ensures the solution handles both connectivity and cycle detection effectively, making it a robust solution for checking if a graph is a valid tree.

Comments

No comments yet.