Leetcode: Graph Valid Tree && Summary: Detect cycle in undirected graph

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.

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 in edges.

This problem can be solved by using union find, reference this blog:https://segmentfault.com/a/1190000003791051

复杂度

时间 O(N^M) 空间 O(N)

思路

判断输入的边是否能构成一个树，我们需要确定两件事：

1. 这些边是否构成环路，如果有环则不能构成树

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

因为不需要知道具体的树长什么样子，只要知道连通的关系，所以Union Find(并查集)相比深度优先搜索是更好的方法。我们定义一个并查集的数据结构，并提供标准的四个接口：

• union 将两个节点放入一个集合中

• find 找到该节点所属的集合编号

• areConnected 判断两个节点是否是一个集合

• count 返回该并查集中有多少个独立的集合

具体并查集的原理，参见这篇文章。简单来讲，就是先构建一个数组，节点0到节点n-1，刚开始都各自独立的属于自己的集合。这时集合的编号是节点号。然后，每次union操作时，我们把整个并查集中，所有和第一个节点所属集合号相同的节点的集合号，都改成第二个节点的集合号。这样就将一个集合的节点归属到同一个集合号下了。我们遍历一遍输入，把所有边加入我们的并查集中，加的同时判断是否有环路。最后如果并查集中只有一个集合，则说明可以构建树。

注意

因为要判断是否会产生环路，union方法要返回一个boolean，如果两个节点本来就在一个集合中，就返回假，说明有环路

Union Find based on quick find:  17ms

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        unionfind uf = new unionfind(n);
        for (int i=0; i<edges.length; i++) {
            if (uf.areConnected(edges[i][0], edges[i][1])) return false;
            else {
                uf.union(edges[i][0], edges[i][1]);
            }
        }
        return uf.count()==1;
    }
    
    public class unionfind {
        int[] ids;  //union id for each node
        int cnt; //the number of independent union 
        
        public unionfind(int size) {
            this.ids = new int[size];
            for (int i=0; i<size; i++) {
                ids[i] = i;
            }
            this.cnt = size;
        }
        
        public boolean union(int i, int j) {
            int src = find(i);
            int dst = find(j);
            if (src != dst) {
                for (int k=0; k<ids.length; k++) {
                    if (ids[k] == src) {
                        ids[k] = dst;
                    }
                }
                cnt--;
                return true;
            }
            return false;
        }
        
        public int find(int i) {
            return ids[i];
        }
        
        public boolean areConnected(int i, int j) {
            return find(i)==find(j);
        }
        
        public int count() {
            return cnt;
        }
    }
}

faster: Union Find based on quick union: 3ms

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        unionfind uf = new unionfind(n);
        for (int i=0; i<edges.length; i++) {
            if (uf.areConnected(edges[i][0], edges[i][1])) return false;
            else {
                uf.union(edges[i][0], edges[i][1]);
            }
        }
        return uf.count()==1;
    }
    
    public class unionfind {
        int[] ids;  //union id for each node
        int cnt; //the number of independent union 
        
        public unionfind(int size) {
            this.ids = new int[size];
            for (int i=0; i<size; i++) {
                ids[i] = i;
            }
            this.cnt = size;
        }
        
        public void union(int i, int j) {
            int rooti = find(i);
            int rootj = find(j);
            ids[rooti] = rootj;
            this.cnt--;
        }
        
        public int find(int i) {
            while (ids[i] != i) i = ids[i];
            return i;
        }
        
        public boolean areConnected(int i, int j) {
            return find(i)==find(j);
        }
        
        public int count() {
            return cnt;
        }
    }
}

Summary:

Dectect cycle in directed graph:

Detect cycle in a directed graph is using a DFS. Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. In the following graph, there are 3 back edges, marked with cross sign. We can observe that these 3 back edges indicate 3 cycles present in the graph.

To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is back edge. We have used recStack[] array to keep track of vertices in the recursion stack.

Detect cycle in undirected graph:

method 1: Union Find  The time complexity of the union-find algorithm is O(ELogV).

method 2: DFS + parent node  Like directed graphs, we can use DFS to detect cycle in an undirected graph in O(V+E) time. We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle. The assumption of this approach is that there are no parallel edges between any two vertices.