Graph Valid Tree

Leave a comment

November 30, 2016 by oneOokay

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.


给一个无向图,判断该无向图是不是树. 成为树的条件:

  • 所有的点必须都是连接的
  • 不能存在环

corner cases:

  • 当n=1而edges为空的时候,单独的一个点也算是树
  • 当n > 1且edges为空的时候,并不是一个树

三种方法:DFS, BFS和Union Find

DFS:

  1. 用一个ArrayList[]数组来存两点之间的连接关系:
    •  ArrayList[i]表示从点i出发直接到达的点的集合.
    • 对于该ArrayList[]需要首先对每一个ArrayList进行初始化
    • 因为是无向图,所以在遍历edges的时候,对于edges[i]中的每对pair,都要放到ArrayList里面两次:
    • 一次以第一个数edges[i][0]为起点(终点为edges[i][1])
    • 第二次以第二个数edges[i][1]为起点(终点为edges[i][0])
  2. 一个boolean[] 来存访问过的(也就是存在于连通图中的)点:只要能够访问,就说明是该点与其他的已经访问过的点是联通的.
  3. detectCycle 判断无向图中是否存在环.这是一个DFS method.
    • 传入ArrayList[]: 用来找到路径;
    • int vertex代表当前正在访问的节点;
    • boolean[]:来判断是否有环:如果当前访问的点visited == true了,就有环;
    • 一个int parent来记录当前点的parent,就知道是从哪里走来的.当parent == vertex的时候,跳过.这样用来避免在两个联通节点之间进行无限死循环.
    • 注意这个在主函数中只需要call一次,传入第一个点即可,不需要在主函数里面for loop:因为给定任何一个点,都能够找到包含该点的一个连通图.
  4. 判断是否是一个联通图: 遍历boolean[] visited:
    • 如果所有点 visited[i] == true,说明是一个连通图.说明从主函数的一个点(传入detectCycle的那个点)所包含的连接的通路是包含了所有点的一个通路.那么就是一个连通图.
    • 如果存在visited[i] == false:说明不是一个连通图,该点与主函数传入的那个点所形成的一个通路是不相连的.
    public boolean validTree(int n, int[][] edges) {
//注意这里当edges.length == 0的时候不能直接返回true.
//corner case: 图为n个点,不存在连通边(edges == null or empty or length == 0
        ArrayList[] graph = new ArrayList[n];
        for (int i = 0; i < n; i ++){
            graph[i] = new ArrayList();
        } 
        for (int i = 0; i < edges.length; i ++){
            graph[edges[i][0]].add(edges[i][1]);
            graph[edges[i][1]].add(edges[i][0]);
        }
        boolean[] visited = new boolean[n];
        if (!detectCycle(graph, visited, 0, -1)) return false;
        
        for (int i = 0; i < n; i ++){
            if (!visited[i]) return false;
        }
        return true;
    }
    
    private boolean detectCycle(ArrayList[] graph, boolean[] visited, int vertex, int parent){
        if (visited[vertex]) return false; 
        visited[vertex] = true;
        ArrayList neighbors = graph[vertex];
        for (int i = 0; i < neighbors.size(); i ++){
            int v = neighbors.get(i);
            if (v == parent) continue;
            if (!detectCycle(graph, visited, v, vertex)) return false;
        } 
        return true;
    }

BFS:

  1. 同DFS1.
  2. 用Queue来帮助遍历:初始:把一个点(一般放0)放入到queue里面.
    • 判断是否有环: 每从queue里面poll出来一个点cur,判断该点是否存在于set中.
      • 若存在:则表示有环
      • 若不存在:把当前点cur加入到set中
    • 对于graph[cur]中的每一个点v
      • 如果不存在于set中,把v加入set里面: 并且!!!从graph[v]中移除掉cur.
        • 注意移除方法:ArrayList list: list.remove(cur): cur是int,所以这个是移除index== cur的元素.
        • 所以正确移除元素的话需要list.remove(new Integer(cur))
        • 如果是Set移除:set没有remove(int index)的方法,所以可以直接传入cur,int 会自动转为Integer.
      • 如果v存在于set中,那么return false. (这一步可以省略因为经过上面你的处理,这种情况不会存在.
  3. 用一个Set来存包含某一个点的一个条通路.
    • 判断是否是连通图:在处理完queue之后最终对Set的size()进行判断.
      • 如果等于所有点的数量,表示整体是一个连通图;
      • 否则表示存在另外的点和边与当前set里面的通路是分开的.
public boolean validTree(int n, int[][] edges) {
        ArrayList[] graph = new ArrayList[n];
        for (int i = 0; i < n; i ++){
            graph[i] = new ArrayList();
        } 
        for (int i = 0; i < edges.length; i ++){
            graph[edges[i][0]].add(edges[i][1]);
            graph[edges[i][1]].add(edges[i][0]);
        }
        Set set = new HashSet<>();
        Queue queue = new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()){
            int cur = queue.poll();
            if (set.contains(cur)) return false;
            set.add(cur);
            ArrayList neighbours = graph[cur];
            for (int i = 0; i < neighbours.size(); i ++){
                int v = neighbours.get(i);
                if (!set.contains(v)){
                    queue.offer(v);
                    graph[v].remove(new Integer(cur));
                }else return false;
            }
        }
        return set.size() == n;
    }

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: