[LeetCode#261] Graph Valid Tree

Problem:

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.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Show Hint

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.

General Analysis:

This problem should give you a good taste of magic algorithm. With the right algorithm, a problem could be solved so elegantly and concisely. My first solution is complex and wrong. 

Big picture, if a graph is a tree, it should possess following qualifications:
1. there is only one source node in the graph.
2. there is no circle in the graph. 

Wrong Solution:

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges == null)
            throw new IllegalArgumentException("edges is null");
        boolean[] flag = new boolean[n];
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>> ();
        for (int[] edge : edges) {
            flag[edge[1]] = true;
            if (map.containsKey(edge[0])) {
                map.get(edge[0]).add(edge[1]);
            } else{
                ArrayList<Integer> item = new ArrayList<Integer> ();
                item.add(edge[1]);
                map.put(edge[0], item);
            }
        }
        int source = -1;
        for(int i = 0; i < n; i++) {
            if (!flag[i]) {
                if (source == -1)
                    source = i;
                else
                    return false;
            }
        }
        if (source == -1)
            return false;
        Arrays.fill(flag, false);
        Queue<Integer> queue = new LinkedList<Integer> ();
        queue.offer(source);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (flag[cur])
                return false;
            flag[cur] = true;
            if (map.containsKey(cur)) {
                ArrayList<Integer> ends = map.get(cur);
                for (int end : ends)
                    queue.offer(end);
            }
        }
        return true;
    }
}

Mistake Analysis:

Error cases:
The above solution try to use BFS traversal over the graph to identify if there is a circle in the graph. However, the solution ignores a very important fact: the graph is undirected rather than directed. When means[0 1] [1 0] is actually the same edge, they could be used interchangely. Thus
1. You could not base on whether a node appears on the left side or not, to decide whether it‘s a source node.
2. Also, you could not based on it to detect a cycle.
The above method only works for Directed Graph.

Analysis:

Actually for Undireted Grpah, we have a classic algorithm to test if there is a circle in the graph. And how many independent sets are there in a graph.

The classic method is called: Union-Find.
Idea: Imagine we could divide the whole grpah into separate sets. (there is no edge to connect two sets). When we read an edge: [start end] from the edge array, it means those two edges actually in the same set, we enlarge the set. If both "start" and "end" have already appeared in the same set before we use the edge, it means a circle was detected. 

Key skills in the implementation:
1. How to record each node‘s set? Could it be very complex?
Absolutely no! A node‘s beloning set could be recored through a int array.
------------------------------------------------------------------------
int[] union = new int[n];
------------------------------------------------------------------------
Before we absorb any edge in the edges array, we treat each node as an independent set. The set number is its own node number.
------------------------------------------------------------------------
Arrays.fill(union, -1);
...
private int findUnion(int[] union, int i) {
    if (union[i] == -1)
        return i;
    ...
}
Note : -1 means it has not been connected with any set yet.
------------------------------------------------------------------------

2. How to find a node‘s belonging set?
We could use DFS method to find a node‘s beloning set.

private int findUnion(int[] union, int i) {
    if (union[i] == -1)
        return i;
    return findUnion(union, union[i]);
}

Note: the way to update union.
for (int[] edge : edges) {
    int x = findUnion(union, edge[0]);
    int y = findUnion(union, edge[1]);
    ...
    union[y] = x;
}
We can trace a node‘s directly connected node back, so as to find out the set‘s no. 

Note: the set‘s no is not fixed, it could be affected by the [start, end]‘s order, but it does not matter. After a edge was updated, we still could trace through any node back to a same node(it is number is the temporay set no). 

Suppose we have already known "node_m" in the set 0. we update the union array through following way:
int x = findUnion(union, edge[0]);
int y = findUnion(union, edge[1]);
union[y] = x;

Case 1: [node_m node_n]
case 2: [node_n node_m]

for case 1:
x = findUnion(union, node_m) = 0;
y = findUnion(union, node_n) = node_n;
union[node_n] = 0;
When we use DFS method, we can track node_n‘s set no is 0.

for case 2:
x = findUnion(union, node_n) = node_n;
y = findUnion(union, node_m) = 0;
union[0] = node_n
When we use DFS method, we can track all nodes in the set back to node_n.

Haha!!!So tricky and powerful!
Thus, we could easily detect if there is a circle in the graph.
if (x == y)
    return false;

3. How to detect if there are more than two independt sets in the graph?
You may think about through counting how many elements in the union array is "-1".

Acutally, we should use a property of tree to answer this question very quickly.
For a tree with N nodes in total, it must have N-1 edges.
return edges.length == n - 1;
If there are more than N-1 edges, it must have circle.
If there are edges < N-1, there are must more than 1 sets(more than two sources).

Solution:

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges == null)
            throw new IllegalArgumentException("edges is null");
        int[] union = new int[n];
        Arrays.fill(union, -1);
        for (int[] edge : edges) {
            int x = findUnion(union, edge[0]);
            int y = findUnion(union, edge[1]);
            if (x == y)
                return false;
            union[y] = x;
        }
        return edges.length == n - 1;
    }

    private int findUnion(int[] union, int i) {
        if (union[i] == -1)
            return i;
        return findUnion(union, union[i]);
    }
}
时间: 09-10

[LeetCode#261] Graph Valid Tree的相关文章

261. Graph Valid Tree

也是卡了好多天的题目 主要就是介绍了union-find的算法,用于检查Undirected graph有没有环 http://www.geeksforgeeks.org/union-find/ 1 public boolean validTree(int n, int[][] edges) { 2 int[] parent = new int[n]; 3 Arrays.fill(parent, -1); 4 for(int i = 0; i < edges.length ; i++) { 5

Leetcode: Graph Valid Tree &amp;&amp; Summary: Detect cycle in directed graph and undirected graph

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. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

LeetCode Graph Valid Tree

原题链接在这里:https://leetcode.com/problems/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. For example: Given n

Graph Valid Tree -- LeetCode

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. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

[Swift]LeetCode261.图验证树 $ 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. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

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. Notice You can assume that no duplicate edges will appear in edges. Since all edg

[LintCode] Graph Valid Tree

http://www.lintcode.com/en/problem/graph-valid-tree/ DFS 解法: 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) {

leetcode 261-Graph Valid Tree(medium)(BFS, DFS, Union find)

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. 这道题主要就是判断1.是否有环路 2. 是否是连通图 可以用DFS, BFS 和 Union find,union find最合适. 对于DFS和BFS,首先都是建立

LeetCode: Validata Binary Search Tree

LeetCode: Validata Binary Search Tree Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree o