# 178.Graph Valid Tree

## 1.Description(Medium)

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 edges are`undirected`,`[0, 1]`is the same as`[1, 0]`and thus will not appear together in edges.

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

## 2.Code

<http://www.jiuzhang.com/solutions/graph-valid-tree/>

<http://www.cnblogs.com/grandyang/p/5257919.html>

这道题给了我们一个无向图，让我们来判断其是否为一棵树，我们知道如果是树的话，所有的节点必须是连接的，也就是说必须是连通图，而且不能有环，所以我们的焦点就变成了验证是否是连通图和是否含有环,即

1. 这些边是否构成环路，如果有环则不能构成树
2. 这些边是否能将所有节点连通，如果有不能连通的节点则不能构成树

Version 1：Union Find

我们定义一个并查集的数据结构，并提供标准的四个接口：

* `union`将两个节点放入一个集合中
* `find`找到该节点所属的集合编号
* `areConnected`判断两个节点是否是一个集合
* `count`返回该并查集中有多少个独立的集合

具体并查集的原理，参见<http://blog.csdn.net/dm_vincent/article/details/7655764>。简单来讲，就是先构建一个数组，节点0到节点n-1，刚开始都各自独立的属于自己的集合。这时集合的编号是节点号。然后，每次union操作时，我们把整个并查集中，所有和第一个节点所属集合号相同的节点的集合号，都改成第二个节点的集合号。这样就将一个集合的节点归属到同一个集合号下了。我们遍历一遍输入，把所有边加入我们的并查集中，加的同时判断是否有环路。最后如果并查集中只有一个集合，则说明可以构建树。因为要判断是否会产生环路，union方法要返回一个boolean，如果两个节点本来就在一个集合中，就返回假，说明有环路.

Version 2:BFS

```
public boolean validTree(int n, int[][] edges) {
        if (n == 0) {
            return false;
        }

        if (edges.length != n - 1) {
            return false;
        }

        //Initial and fill the adjacencylist
        List<ArrayList<Integer>> adjacencylist=new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<n;i++){
            adjacencylist.add(new ArrayList<Integer>());
        }
        for(int i=0;i<edges.length;i++){
            int a=edges[i][0];
            int b=edges[i][1];
            adjacencylist.get(a).add(b);
            adjacencylist.get(b).add(a);
        }

        HashSet<Integer> set=new HashSet<Integer>();
        Queue<Integer> queue=new LinkedList<Integer>();
        queue.offer(0);
        set.add(0);

        while(!queue.isEmpty()){
            int current=queue.poll();
            for(int element : adjacencylist.get(current)){
                if(set.contains(element)){
                    continue; //注意这里是continue
                }
                else{
                    set.add(element);
                    queue.offer(element);
                }
            }            
        }
        return (set.size()==n);
    }
```

BFS 解法2：用一个visited数组

```
public boolean validTree(int n, int[][] edges) {
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
    for(int i=0; i<n; i++){
        ArrayList<Integer> list = new ArrayList<Integer>();
        map.put(i, list);
    }

    for(int[] edge: edges){
        map.get(edge[0]).add(edge[1]);
        map.get(edge[1]).add(edge[0]);
    }

    boolean[] visited = new boolean[n];

    LinkedList<Integer> queue = new LinkedList<Integer>();
    queue.offer(0);
    while(!queue.isEmpty()){
        int top = queue.poll();
        if(visited[top])
            return false;

        visited[top]=true;

        for(int i: map.get(top)){
            if(!visited[i])
                queue.offer(i);
        }
    }

    for(boolean b: visited){
        if(!b)
            return false;
    }

    return true;
}
```

BFS解法3：每次遍历到一个点的邻接点a时，就把a从他的邻接表中去掉别的点就不会再遍历到了。

```
// BFS, using queue
private boolean valid(int n, int[][] edges) {
    // build the graph using adjacent list
    List<Set<Integer>> graph = new ArrayList<Set<Integer>>();   
    for(int i = 0; i < n; i++)
        graph.add(new HashSet<Integer>());
    for(int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }

    // no cycle
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new ArrayDeque<Integer>();
    queue.add(0);
    while(!queue.isEmpty()) {
        int node = queue.poll();
        if(visited[node])
            return false;
        visited[node] = true;
        for(int neighbor : graph.get(node)) {
            queue.offer(neighbor);
            graph.get(neighbor).remove((Integer)node);
        }
    }

    // fully connected
    for(boolean result : visited){
        if(!result)
            return false;
    }

    return true;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/178.graph-valid-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.