[Leetcode] Graph Valid Tree 判斷一個圖是否為樹

xbynet 發布于2019-08-14 14:04 / 888人閱讀

摘要：只有一個連通分量還沒有環，就是樹，無根樹。無向圖邊的兩端是對稱的，無向圖講究連通這個概念，沒有方向，沒有拓撲，很像集合，所以非常適合用并查集來解決。并查集寫法參考注意方法用找的老大哥，合并的是的老大哥。

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加速判斷是否判斷是否隱藏判斷是否符合規劃

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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