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

Contact me on wechat to get Amazon、Google requent Interview questions . (wechat id : jiuzhang0607)

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.

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.

解析

題目給定一個正整數 n , 代表具有 label 0 到 label n-1 的 vertex

還有一個矩陣 edges 每個 entry $edges[i] = [a_i, b_i]$ 代表 $a_i$ 與 $b_i$ 兩個 vertex 有相連

要求寫一個演算法來判斷給定的 n, edges 能不能形成一個合法的樹結構

要形成合法的樹必須符合以下條件

1. 不能有 cycle
2. 假設有 n 個 vertex ， 必須要有 n-1 的 edges

第一個條件可以透過 Union/Find 演算法來檢驗, 當發現兩個要 Union 的 vertex 居有相同的 ancestor 就知道形成 cycle

程式碼

public class Solution {
    /**
     * @param n: An integer
     * @param edges: a list of undirected edges
     * @return: true if it's a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        int numEdges = edges.length;
        if (numEdges != n-1) {
            return false;
        }
        int[] parent = new int[n];
        int[] rank = new int[n];
        for (int node = 0; node < n; node++) {
            parent[node] = node;
            rank[node] = 1;
        }
        for (int[] edge: edges) {
            if (!union(edge[0], edge[1], parent, rank)) {
                return false;
            }
        }
        return true;
    }
    public int find(int node, int[] parent) {
        int p = parent[node];
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }
    public boolean union(int node1, int node2, int[] parent, int[] rank) {
        int p1 = find(node1, parent);
        int p2 = find(node2, parent);
        if (p1 == p2) {
            return false;
        }
        if (rank[p1] > rank[p2]) {
            parent[p2] = p1;
            rank[p1] += rank[p2];
        } else {
            parent[p1] = p2;
            rank[p2] += rank[p1];
        }
        return true;
    }
}

困難點

1. 理解 valid tree 的條件
2. 理解 Union/Find 演算法

Solve Point

• 理解 valid tree 的條件
• 實作 union/find 演算法