Graph Valid Tree

Source

• leetcode: 261

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.

Hint:
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this
case a valid tree?
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.”
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 inedges.

java

// 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;
}

Reference

Graph Valid Tree