[Leetcode] Graph Valid Tree 判断一个图是否为树

xbynet 发布于2019-08-14 14:04 / 752人阅读

摘要：只有一个连通分量还没有环，就是树，无根树。无向图边的两端是对称的，无向图讲究连通这个概念，没有方向，没有拓扑，很像集合，所以非常适合用并查集来解决。并查集写法参考注意方法用找的老大哥，合并的是的老大哥。

Graph Valid Tree

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? Show More Hint 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.

并查集法 复杂度

O( V + E ) 时间 O(V) 空间

并查集(带路径压缩path compression)两个操作的平摊时间(amortized time)复杂度为O(log*n)，读作log星n，它增长得极为缓慢，所以认为O(1)

思路

感性的认识一下无向图中树的样子：假设是连通图，图如果是树，那么树是无根树，即谁都是根，所以无根。
这个树和树这个数据结构(比如二叉树)还不一样，二叉树是一个有根树，有个特殊节点叫根。

这道题里的树，就是任意两点有且只有一条路径可达，这条路径的每个边只走一次。
换句话讲，图想要是树，得是没有回路的连通图，就是要满足两个性质：

是连通图

无环

一般来讲判断是否有环都在一个连通图上判断，如果这个图有多个连通分量，那就要对每个连通分量都判断一下是否有环。都没有环，那就是森林。只有一个连通分量还没有环，就是树，无根树。

无向图边的两端是对称的，无向图讲究连通这个概念，没有方向，没有拓扑，很像集合，所以非常适合用并查集来解决。
解决的方法：
想象一开始这个图只有顶点，没有边，我们来一条一条的添加边。
每遇到一条边，判断这边的两个端点是否在同一个集合里？集合的property:表示一个连通分量，里面的任意两点有且只有一条路径可达

在的话，表示有环：因为两个点在一个集合里就表示这两个点已经有一条路径了，现在再加一条路径，必然构成环。

不在的话，表示不构成环，我们应该合并这两个集合：因为加上这条边，两个集合就被连起来了，合并成了一个集合

注意

如果想要复杂度为O(V+E),必须用路径压缩。
并查集写法参考
注意union(p,q)方法：用find()找p,q的老大哥，合并的是p,q的老大哥。

代码

UnionFind Utility(非常intuitive，应该练习在5分钟内写完):

class UnionFind {
    private int[] father;
    private int count;
    public UnionFind(int n) {
        father = new int[n];
        count = n;
        for (int i = 0; i < n; i++){
            father[i] = i;
        }
    }
    public int count() {
        return this.count;
    }
    public int find(int p) {
        int root = father[p];
        while (root != father[root])
            root = father[root];
        //as long as we get here, root is the final dad
        while (p != root) {
            int tmp = father[p];
            father[p] = root;
            p = tmp;
        }
        return root;
    }
    public void union(int p, int q) {
        int fatherP = find(p);
        int fatherQ = find(q);
        if (fatherP != fatherQ) {
            father[fatherP] = fatherQ;
            count--;
        }
    }
}

主程序

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges){
            int p = edge[0];
            int q = edge[1];
            if (uf.find(p) == uf.find(q))
                return false;
            else
                uf.union(p,q);
        }
        return uf.count() == 1;
    }
}

DFS/BFS法 复杂度

O( V + E ) 时间 O(V) 空间

思路

无向图找环和有向图找环本质上完全不同。
有向图找环需要三种颜色。
无向图找环只需要两种颜色，就是访问过的和没访问的。

dfs过程中如果碰到访问过的节点(当然这个节点不能是来时的节点)，就是有环。

注意

Integer的比较问题

代码

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        HashSet visited = new HashSet();
        List> adjList = new ArrayList>();
        for (int i=0; i()); 
        for (int[] edge: edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }
        if (hasCycle(-1, 0, visited, adjList))  // has cycle?
            return false;   
        if (visited.size() != n) // is all connected?
            return false;   
        return true;
    }

    private boolean hasCycle(Integer pred, Integer vertex, HashSet visited, List> adjList) {
        visited.add(vertex);  // current vertex is being visited
        for (Integer succ: adjList.get(vertex)) {  // successors of current vertex
            if (!succ.equals(pred)) {  // exclude current vertex"s predecessor
                if (visited.contains(succ)) { 
                    return true; // back edge/loop detected!
                }  
                else  {
                    if (hasCycle(vertex, succ, visited, adjList)) { 
                        return true; 
                    }
                }
            }
        }
        return false;
    }
}

私有云 GPU服务器怎么判断一个域名是否cdn加速判断是否判断是否隐藏判断是否符合规划

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64795.html

[Leetcode] Graph Valid Tree 图与树

摘要：这样就将一个集合的节点归属到同一个集合号下了。最后如果并查集中只有一个集合，则说明可以构建树。 Graph Valid Tree 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 w...

luqiuwen 2019-08-14 12:36 评论0 收藏0
261. Graph Valid Tree

摘要：题目链接检查图的连通性及是否有环，可以，，从一个点出发看能不能遍历所有的点，同时来检查是否有环。还可以用检查是否有环，最后看的数量是否等于来判断是不是。 261. Graph Valid Tree 题目链接：https://leetcode.com/problems... 检查图的连通性及是否有环，可以dfs，bfs，从一个点出发看能不能遍历所有的点，同时visited来检查是否有环。...

Jinkey 2019-08-16 10:29 评论0 收藏0
[LeetCode] Graph Valid Tree [Union Find]

Problem 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. Example Given n = 5 and...

104828720 2019-08-14 15:10 评论0 收藏0
面试算法实践与国外大厂习题指南

摘要：面试算法实践与国外大厂习题指南翻译自维护的仓库，包含了在线练习算法概述与大厂习题实战等内容。面试算法实践与国外大厂习题指南在线练习在线面试编程数据结构链表即是由节点组成的线性集合，每个节点可以利用指针指向其他节点。面试算法实践与国外大厂习题指南翻译自 Kevin Naughton Jr. 维护的仓库 interviews，包含了在线练习、算法概述与大厂习题实战等内容。笔者发现正好和...

genedna 2019-08-14 17:46 评论0 收藏0
leetcode310. Minimum Height Trees

摘要：现在要求在这样一棵生成树中，找到生成树的高度最低的所有根节点。然后利用邻接表的相关属性来判断当前节点是否是叶节点。度数为一的顶点就是叶节点。这里使用异或的原因是对同一个值进行两次异或即可以回到最初值。题目 For an undirected graph with tree characteristics, we can choose any node as the root. The...

xiaoxiaozi 2019-08-16 13:46 评论0 收藏0