261. Graph Valid Tree

Jinkey 發(fā)布于2019-08-16 10:29 / 981人閱讀

摘要：題目鏈接檢查圖的連通性及是否有環(huán)，可以，，從一個(gè)點(diǎn)出發(fā)看能不能遍歷所有的點(diǎn)，同時(shí)來(lái)檢查是否有環(huán)。還可以用檢查是否有環(huán)，最后看的數(shù)量是否等于來(lái)判斷是不是。

261. Graph Valid Tree

題目鏈接：https://leetcode.com/problems...

檢查圖的連通性及是否有環(huán)，可以dfs，bfs，從一個(gè)點(diǎn)出發(fā)看能不能遍歷所有的點(diǎn)，同時(shí)visited來(lái)檢查是否有環(huán)。還可以用union find檢查是否有環(huán)，最后看edge的數(shù)量是否等于n-1來(lái)判斷是不是spinning tree。

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if(edges.length != n - 1) return false;
        
        map = new int[n];
        Arrays.fill(map, -1);
        // union find
        for(int[] edge : edges) {
            int root1 = find(edge[0]);
            int root2 = find(edge[1]);
            // if connected before, there is a cycle
            if(root1 == root2) return false;
            // union
            map[root1] = root2;
        }
        return true;
    }
    int[] map;
    
    private int find(int child) {
        while(map[child] != -1) child = map[child];
        return child;
    }
}

dfs注意要保留parent指針，這樣防止出現(xiàn)u->v之后又返回查一遍

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // build graph
        build(edges, n);
        // store visited node
        Set visited = new HashSet();
        // dfs from 0, to check if visited all nodes and if cycle
        if(dfs(visited, 0, -1)) return false;
        return visited.size() == n;
    }
    
    // adjacent list to represent graph
    List> graph;
    private void build(int[][] edges, int n) {
        graph = new ArrayList();
        for(int i = 0; i < n; i++) graph.add(new HashSet());
        for(int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
    }
    
    private boolean dfs(Set visited, int u, int parent) {
        // has cycle
        if(visited.contains(u)) return true;
        visited.add(u);
        for(int v : graph.get(u)) {
            if(v == parent) continue;
            if(dfs(visited, v, u)) return true;
        }
        return false;
    }
}

bfs同樣要要注意避免走重復(fù)路經(jīng)的問(wèn)題，遍歷過(guò)的點(diǎn)就刪掉。

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // build graph
        build(edges, n);
        // store visited node
        Set visited = new HashSet();
        // bfs from 0, to check if visited all nodes and if cycle
        return bfs(visited, n);
    }
    
    // adjacent list to represent graph
    List> graph;
    private void build(int[][] edges, int n) {
        graph = new ArrayList();
        for(int i = 0; i < n; i++) graph.add(new HashSet());
        for(int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
    }
    
    private boolean bfs(Set visited, int n) {
        Queue q = new LinkedList();
        q.offer(0);
        while(!q.isEmpty()) {
            int u = q.poll();
            if(visited.contains(u)) return false;
            visited.add(u);
            for(int v : graph.get(u)) {
                q.offer(v);
                // remove parent, avoid duplicate
                graph.get(v).remove(u);
            }
        }
        
        return visited.size() == n;
    }
}