Graph Valid Tree

• Median
• keyword: Data structure, Graph, Union-Find, dummy node
• 类似: Graph, missing range

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: a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree

idea:

• 其实hint已经说完了解法: 即Connected Compoennt 和 hasCycle. 即先判断是否有环, 并且每个点都能reachable.

• 之前做alien dictionary的时候也有hasCycle的判断. 这里我使用Algs4里面的经典写法: DFS. 其中判断: `如果某个node的adj已经visit过, 并且该adj不是parent(*)的话, 则说明是cycle了.

  • 注意这里有个catch: 并不是recursion call都要return, 而是true的话直接return, false的话还要接着walk down the tree!

  • 代码如下

    public boolean hasCycle(List<List<Integer>> G, int u, boolean[] visited, int parent) {
      visited[u] = true;
      for (int v : G.adj(u)) {
          if (!visited(v)) {
              if (hasCycle(G, v, visited, u) == true) {
                  return true;  // catch. 只有发现cycle了才要return, 否则继续搜索.    
              }
          }
          else {
              if (v != parent) {
                  return true;
              }
          }
      }
      return false;
    }
    

• algs4里面是对每一个node进行一次hasCycle判断. 而这里并不需要, 因为这里的node确定了: 是0~n-1的数. 而且要保证所有点都连起来. 于是可以对0求cycle即可. 那么0的parent是谁呢? 我一开始并不知道啊?!?!

  • 这里再次体现了构造的重要性: 可以看看missing range的low-1/upper+1
    • hasCycle(G, 0, visited, 0);: algs4
    • hasCycle(G, 0, visited, -1);: discuss

• 代码如下

  public boolean validTree(int n, int[][] edges) {
    List<List<Integer>> G = new ArrayList<>();
    return dfs(n, edges, G);
  }


  public boolean dfs(int n, int[][] edges, List<List<Integer>> G) {
    for (int i = 0; i < n; ++i) {
      G.add(i, new ArrayList<>());
    }
    for (int i = 0; i < edges.length; ++i) {
      int u = edges[i][0], v = edges[i][1];
      G.get(u).add(v);
      G.get(v).add(u);
    }

    boolean[] visited = new boolean[n];

    if (hasCycle(G, 0, visited, 0)) {  // parent是0/-1都可以. 为什么呢?
      return false;
    }

    for (int i = 0; i < n; ++i) {
      if (visited[i] != true) {
        return false;
      }
    }

    return true;
  }