【Lintcode】178. Graph Valid Tree

题目地址：

https://www.lintcode.com/problem/graph-valid-tree/description

判断一个无向图是否构成一棵树。

树的定义有非常多个版本。比较容易编程判断的是如下的版本：

一个无向图是树，当且仅当：
1、其连通
2、其边数等于顶点数 - 1

第二条的顶点与边的关系，主要保证了这个图是无环的，也保证了任意两点之间有且仅有一条路径可以到达。

第二条性质非常好判断，而要判断第一条性质的话，我们只需要从图中任意一点出发，去做搜索，如果搜索完成之后发现已经访问过的点的个数正好等于顶点数，那就说明了图是连通的。在这里我们可以用BFS来实现。由于要BFS来搜索图的时候，需要知道每个顶点的邻边都有哪些，所以我们需要在搜索之前把图建立为一个邻接表。代码如下：

import java.util.*;

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) {
        // write your code here
        // 如果顶点和边的个数关系不成立，直接返回false        
        if (n - 1 != edges.length) {
            return false;
        }
        // 接下来建图，用邻接表
        Map<Integer, Set<Integer>> graph = buildGraph(n, edges);
        // 为了BFS，开一个队列和哈希表。哈希表主要用于判断是否访问过，以避免重复访问
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        // 我们可以从顶点0开始出发去搜索整个图，将0入队，也加入哈希表
        queue.offer(0);
        visited.add(0);
        
        while (!queue.isEmpty()) {
            int cur = queue.poll();
    		// 得到当前访问顶点的邻居们
            for (Integer neighbor : graph.get(cur)) {
            	// 如果该邻居没有访问过，则将其入队，也标记其邻居为访问过
                if (visited.add(neighbor)) {
                    queue.offer(neighbor);
                }
            }
        }
        // 如果总共访问过的顶点个数刚好为n，说明图是连通的，可以构成一棵树，返回true，否则返回false
        return visited.size() == n;
    }
	
	// 用邻接表建图
    private Map<Integer, Set<Integer>> buildGraph(int n, int[][] edges) {
    	// key是顶点编号，value是该顶点的邻居编号
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new HashSet<>());
        }
    
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        return graph;
    }
}

时空复杂度$O(n)$O(n)。