Graph Valid Tree

Question (LC.261)

Given n nodes (label in [0, n-1]) and list of undirected edges, validate the given graph is a tree.

Assume that no duplicate edges will appear in edges.

Example

Input: n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Graph:   ->1->4
        0->2
         ->3
Output: true it is a valid tree

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Graph:      0
            |
            1
          / \  \
         2  |   4
         \ /
          3 
Output: A tree cannot contain cycles. False.

Analysis

What differentiates a tree from a graph? Here are the things we want to check:

• The graph is acyclic

• The graph is connected

Each tree has |nodes| - 1 edges. If the graph does not have cycle, then it is a valid tree.

DFS

This should be the most intuitive approach. We want to see if the component is connected and without any cycle.

Approach:
Step 1 Build graph (adjacency list)
Step 2 DFS the graph from any vertex (detect cycle)
Step 3 check to see if the component is connected

Main function

public boolean validTree(int n, int[][] edges) {
    // Step 0 edge cases and quick check
    // invalid graph
    if (n < 1) {
        return false;
    }
    // not all nodes are connected or over connected
    if (edges.length + 1 != n) {
        return false;
    }
    // Step 1 build a graph
    Map<Integer, List<Integer>> graph = new HashMap<>();
    buildGraph(graph, edges, n);
    // Step 2 DFS the graph (check cycle)
    // Map<V, Parent(V)> will work in the general case
    Set<Integer> visited = new HashSet<>(); 
    // start from anywhere is fine cause undirected graph
    if (cycleDFS2(graph, 0, -1, visited)) {
        return false;
    }
    // Step 3 Check the component is connected
    return visited.size() == n;
}

Build (Directed) Graph

private void buildGraph(Map<Integer, List<Integer>> graph, int[][] edges, int n) {
    // init vertices
    for (int i = 0; i < n; i++) {
        graph.put(i, new ArrayList<>());
    }
    // add undirected edges
    for (int[] edge : edges) {
        // need to add both directions
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }
}

DFS and Cycle Detection

private boolean cycleDFS2(Map<Integer, List<Integer>> graph, 
        Integer visit, Integer parent, Set<Integer> visited) {
    visited.add(visit);
    for (Integer neighbor : graph.get(visit)) { 
        if (visited.contains(neighbor) && !neighbor.equals(parent)) {
            return true;
        }
        if (!visited.contains(neighbor) && 
            cycleDFS2(graph, neighbor, visit, visited)) {
            return true;
        }
    }
    return false;
}

BFS

If the graph is neighbor under connected nor over connected, then we can try to explore the whole graph from a node. If we explored all the nodes on this graph (connected), then it is acyclic. Otherwise, it has cycles and it's not connected.

Main function

public boolean validTree(int n, int[][] edges) {
    // Step 0 check over/under connected
    if (n < 1 || edges.length + 1 != n) {
        return false;
    }
    // Step 1 build a graph
    Map<Integer, List<Integer>> graph = new HashMap<>();
    buildGraph(graph, edges, n);
    // Step 2 BFS the graph
    int explored = bfsExplore(graph);
    // Step 3 Check the component is connected
    return explored == n;
}

BFS Explore

private int bfsExplore(Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>(); 
    Queue<Integer> queue = new LinkedList<>();
    int explored = 0;
    queue.offer(0);
    visited.add(0);
    while (!queue.isEmpty()) {
        Integer current = queue.poll();
        explored++;
        for (Integer neighbor : graph.get(current)) {
            if (!visited.contains(neighbor)) {
                queue.offer(neighbor);
                visited.add(neighbor);
            }
        }
    }
    return explored;
}

Note 1: We have to add visited after offer bucause some elements can still be in queue but not processed yet. We don't want to visit the same node again. Note 2: Stay away from Integer and other wrappers if you can since they are all immutable.

Union Find

The solution can be very elegant using this approach. The idea to find two vertices (v1, v2) first. If they don't belong to the same set (no cycle), then union them.

References

• Quora - How are DAGs different from trees?
• Quora - How do I detect a cycle in a directed graph?