Algorithms to Check if a Graph is a Valid Tree by Using Disjoint Set (Union Find) and Breadth First Search

According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

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.

Determine Valid Tree using Breadth First Search Algorithm

We can start BFS (Breadth First Seach) for any given node so that the connected nodes can be recorded. At last, we just need to check if all nodes are visited – as we already check that the tree with N nodes should have exactly N-1 edges.

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

class Solution {
public:
    bool validTree(int n, vector<vector <int>>& edges) {       
        if (n - 1 != edges.size()) return false;
        if (edges.size() == 0) return true;
        vector<bool> v(n, false);
        vector<unordered_set<int>> g(n); // adjacency matrix
        for (const auto &e: edges) {
            g[e[0]].insert(e[1]);
            g[e[1]].insert(e[0]);
        }
        queue<int> Q;
        Q.push(edges[0][0]);
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            for (const auto x: g[p]) {
                if (!v[x]) {
                    Q.push(x);
                    v[x] = true;
                }
            }
        }
        for (const auto &n: v) {
            if (!n) return false;
        }
        return true;
    }
};

class Solution {
public:
    bool validTree(int n, vector<vector <int>>& edges) {       
        if (n - 1 != edges.size()) return false;
        if (edges.size() == 0) return true;
        vector<bool> v(n, false);
        vector<unordered_set<int>> g(n); // adjacency matrix
        for (const auto &e: edges) {
            g[e[0]].insert(e[1]);
            g[e[1]].insert(e[0]);
        }
        queue<int> Q;
        Q.push(edges[0][0]);
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            for (const auto x: g[p]) {
                if (!v[x]) {
                    Q.push(x);
                    v[x] = true;
                }
            }
        }
        for (const auto &n: v) {
            if (!n) return false;
        }
        return true;
    }
};

The space complexity is O(N^2) as we need a adjacency matrix to record the edges.

Determine Valid Tree using Union Find (Disjoint Set) Algorithm

Using Disjoint Set is another good solution. The disjoin set allows us to find groups of connected nodes by marking the parents. The union find is an important operation that find the parent of a given node.

Initialialy, all nodes are isolated with label of their index. Two nodes of the edges are then marked with the same parent (group), by any time, if two nodes are already in the same group, that means there is cycle.

When we find the parents of a node i, we can compress the path by using parent[i] = parent[parent[i]]. Otherwise, without path compression, the union find may take O(N) to finish and thus making the entire complexity O(N^2).

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

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {       
        if (n - 1 != edges.size()) return false;
        vector<int> parent(n);
        for (int i = 0; i < n; ++ i) {
            parent[i] = i;
        }
        for (const auto &e: edges) {
            int x = find(parent, e[0]);
            int y = find(parent, e[1]);
            // if parents are equal, we know there is a cycle.
            if (x == y) return false;
            // make two nodes same parent (group)
            parent[x] = y;        
        }
        return true;
    }
    
private:
    int find(vector<int> &parent, int i) {
        while (i != parent[i]) {
            parent[i] = parent[parent[i]]; // compress the disjoint set
            i = parent[i];
        }
        return i;
    }
};

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {       
        if (n - 1 != edges.size()) return false;
        vector<int> parent(n);
        for (int i = 0; i < n; ++ i) {
            parent[i] = i;
        }
        for (const auto &e: edges) {
            int x = find(parent, e[0]);
            int y = find(parent, e[1]);
            // if parents are equal, we know there is a cycle.
            if (x == y) return false;
            // make two nodes same parent (group)
            parent[x] = y;        
        }
        return true;
    }
    
private:
    int find(vector<int> &parent, int i) {
        while (i != parent[i]) {
            parent[i] = parent[parent[i]]; // compress the disjoint set
            i = parent[i];
        }
        return i;
    }
};

You can also use Depth First Search (DFS) algorithm to validate if a graph is a tree, could you do it?

Tree Detection Algorithms

• Teaching Kids Programming – Tree Detection Algorithm via Breadth First Search (Determine a Binary Tree)
• Algorithms to Check if a Graph is a Valid Tree by Using Disjoint Set (Union Find) and Breadth First Search
• Teaching Kids Programming – Tree Detection via Depth First Search Algorithm (Determine a Binary Tree via Recursion)
• Teaching Kids Programming – Tree Detection via Union Find + Disjoint Set (Determine a Binary Tree)

–EOF (The Ultimate Computing & Technology Blog) —