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. 用一个List<List<Integer>> list来存两点之间的连接关系:
    •  第i个list表示从点i出发直接到达的点的集合.
    • 对于该list需要首先要一共加入n个empty list
    • 因为是无向图,所以在遍历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来帮助遍历:
    • 把什么放到queue里面?边 edge int[]还是点?放哪个点?
      • 把点放到queue里面,从一个点开始,按照之前生成的List<List<Integer>>来进行遍历. 其实放那个点都行,但是以后就都放0好了.
    • 怎么遍历?因为无向图,对于每一条边,两个点都加到了对方的list里面.这样在遍历的时候,如果不做一些什么的话,从0到1,把1放到queue里面,当对1visite的时候,就又会碰到0. 如果区别是真的环还是正常的visite.
      • 方法1.一个set,visit 完一个点0放到set里面,同时把与0相接的点的list里面的0给去掉,这样之后0就不会再被访问到了(如果没有环) 
      •  初始:把一个点(一般放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. (这一步可以省略因为经过上面你的处理,这种情况不会存在.
      • 用一个Set来存包含某一个点的一个条通路.
      • 判断是否是连通图:在处理完queue之后最终对Set的size()进行判断.
        • 如果等于所有点的数量,表示整体是一个连通图;
        • 否则表示存在另外的点和边与当前set里面的通路是分开的.
    • 方法2. 一个int[] visited array.
    • 当值==0, 该点没有被visit过;
    • 值==1,第一次visit到,该点现在在queue里面,将会被poll出来;
    • 值==2,visit完毕, 把当前的点的neighbors都加到queue里面去了.
    • 把0加入queue, visit[0] = 1,因为现在0在queue里面.
    • queue poll出来,对它的每一个neighbors进行判断.(注意这里并不需要对poll出来的这个进行判断)
    • 如果neighbor 的visited == 1的话,return.说明有环.
    • 如果neighbor的visited == 0, 把它更新为1
    • 如果neighbor的visited == 2, 忽略.
    • 结束while loop对visited array进行loop判断.如果存在某个点visited == 0,说明他没有被visit,是一个独立的点.不能形成树.

这题有点很奇怪的地方: ArrayList[]过不了. 所以还是用List<List<Integer>>好了.

public boolean validTree(int n, int[][] edges) {
 if (n == 0) return true;
 List<List<Integer>> nodes = new ArrayList<>();
 for(int i = 0; i < n; i ++)
 nodes.add(new ArrayList<Integer>());
 for (int[] edge : edges){
 nodes.get(edge[0]).add(edge[1]);
 nodes.get(edge[1]).add(edge[0]);
 }
 
 Queue<Integer> queue = new LinkedList<>();
 Set<Integer> set = new HashSet<>();
 queue.offer(0);
 while(!queue.isEmpty()){
 int cur = queue.poll();
 if(set.contains(cur)) return false;
 set.add(cur);
 for(int next : nodes.get(cur)){
 if (set.contains(next)) return false;
 nodes.get(next).remove(new Integer(cur));
 queue.offer(next); } }
 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: