Tree & Undirected Graph

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

For an undirected graph to be a valid tree

1. no cycle
2. the number of tree/components should be 1. If no cycle and no duplicated edges, #edges equals #vertices - 1

Leetcode 261

Leetcode 323

One intuitive approach is using graph traversal to detect cycle and count #components. But a more efficient way is using Union-Find to detect cycle.

Union-Find is more efficient only in the adjacency list representation.

** If the graph is represented in adjacency matrix, union find might need $$O(n^3)$$in worst case. We traverse over the complete matrix once. Union and find operations take $$O(n)$$ time in the worst case.

Union-Find approach:

class Solution {

    public boolean validTree(int n, int[][] edges) {
        //more than one connected components/tree
        if(n-1 != edges.length) return false;

        int[] nums = new int[n]; //parent list for union find
        Arrays.fill(nums, -1);

        for(int[] edge: edges) {
            int x = find(nums, edge[0]);
            int y = find(nums, edge[1]);

            if(x==y) return false; //the two end of the edge belongs to the same set.

            //union
            nums[x] = y;
        }

        return true;

    }

    public int find(int[] nums, int i) {
        if(nums[i]==-1) return i; // the number is alone
        return find(nums, nums[i]); //keep searhing its parent/set representative
    }
}

Graph DFS approach:

class Solution {
    private int[] status;
    private List<Integer>[] graph;

    public boolean validTree(int n, int[][] edges) {
        //represent the graph in adjacency list
        graph = new ArrayList[n];
        //0 is unvisited, 1 is visited, 2 is done
        status = new int[n]; 

        for(int i = 0; i < n; i++){
            graph[i] = new ArrayList<Integer>();
        }

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

        int numTree=0; //the DFS may produce a forest of trees
        for(int i=0; i<n; i++) {
            if(status[i]==0) {
                numTree++;
                if(DFSDetectCycle(i, -1)) return false;
            }
        }

        //check componenet
        return numTree==1;
    }

    public boolean DFSDetectCycle(int v, int parent) {
        status[v] = 1;

        boolean hasCycle = false;
        for(Integer child:graph[v]) {
            if(child!=parent) { // it is undirectional graph, we need to avoid going back from where we are from in DFS
                System.out.println(child);
                System.out.println("status: "+ status[child]);
                if(status[child]==0) {
                    hasCycle = DFSDetectCycle(child, v);
                } else if (status[child]==2) {

                } else {
                    hasCycle = true; //cycle detected;
                }
            }

            if(hasCycle) break;
        }

        status[v] = 2;
        return hasCycle;
    } 
}