310. Minimum Height Trees

Leetcode Breath-first Search Graph

For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format

The graph contains $n$ nodes which are labeled from 0 to $n - 1$. You will be given the number $n$ and a list of undirected edges (each edge is a pair of labels).

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.

Example 1 :

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

Output: [1]

Example 2 :

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

Note:

• According to the definition of tree on Wikipedia: “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.”
• The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

分析

这道题目有两类解法。第一种方法是，观察得到以树中的最长路径的中点为根构建的树的高度是最小的。那么问题就变成如何寻找树中的最长路径(longest path of a tree)。其中一种简便的方法就是，使用两次bfs，第一次bfs以任意点出发$p_0$，寻找到最远的点$v$，第二次bfs以寻找到的最远点$v$出发，寻找到距离该点距离最远的点$w$。路径$v-w$就是树中的最长路径。可以简单证明如下：第一次bfs寻找到的点一定为最长路径的一个端点，利用反证法，如果存在另一点$p$为第一次bfs的最远点，那么$|p-p_0| > |v-w|$，显然与最长路径定义矛盾。既然第一次bfs寻找到了最长路径一个端点，第二次bfs就肯定是另一个端点。

private int[] bfs(Map<Integer, List<Integer>> graph, int[] edgeTo, int s) {
    int[] distTo = new int[edgeTo.length];
    boolean[] mark = new boolean[edgeTo.length];
    Queue<Integer> q = new ArrayDeque<>();
    q.offer(s);
    mark[s] = true;
    distTo[s] = 0;
    while (!q.isEmpty()) {
        int v = q.poll();
        for (int w : graph.get(v)) {
            if (!mark[w]) {
                mark[w] = true;
                distTo[w] = distTo[v] + 1;
                edgeTo[w] = v;
                q.offer(w);
            }
        }
    }

    int longestPath = 0, longestDist = -1;
    for (int i = 0; i < distTo.length; i++) {
        if (distTo[i] > longestDist) {
            longestDist = distTo[i];
            longestPath = i;
        }
    }

    return new int[]{longestDist, longestPath};
}

public List<Integer> findMinHeightTrees(int N, int[][] edges) {
    // construct graph
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int i = 0; i < N; i++)
        graph.put(i, new ArrayList<>());
    for (int i = 0; i < edges.length; i++) {
        int v = edges[i][0], w = edges[i][1];
        graph.get(v).add(w);    // v->w
        graph.get(w).add(v);    // w->v
    }

    // two bfs to find longest path v-w
    int[] edgeTo = new int[N];
    int v = bfs(graph, edgeTo, 0)[1];
    int tmp[] = bfs(graph, edgeTo, v);
    int w = tmp[1], longestDist = tmp[0];

    // find roots (mid-points) of longest path v-w
    List<Integer> roots = new ArrayList<>();
    int mid = w;
    for (int i = 0; i < longestDist / 2; i++)
        mid = edgeTo[mid];
    roots.add(mid);
    if (longestDist % 2 == 1) // two middle points
        roots.add(edgeTo[mid]);
    return roots;
}

而第二种方法非常巧妙了，改自BFS拓扑排序。非常类似“剥洋葱”法BFS：从叶子节点剥向根节点。可以这么设想：最简单的图是什么？ a path graph，连成一条直线的图，那么怎么寻找该图的根节点？使用两个指针，一个指向尾部end, 一个指向首部front, 然后依次向中间移动。对于一个任意无向图，这样的path graph有很多，那么指针的前后向中间移动，可以抽象成一个外面的面向中间收缩，也就是剥洋葱了。

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<List<Integer>>();
    List<Integer> roots = new ArrayList<Integer>();

    // special case: one vertex
    if (n == 1) { roots.add(0); return roots; }

    // degree of every vertex
    int[] degree = new int[n];
    for(int i = 0; i< n; i++) graph.add(new ArrayList<Integer>());

    // initialize degree and graph
    for(int i=0; i<edges.length; i++) {
        int v = edges[i][0], w = edges[i][1];
        graph.get(v).add(w);
        graph.get(w).add(v);
        degree[v]++;
        degree[w]++;
    }        

    // add leaves
    Queue<Integer> leaves = new ArrayDeque<Integer>();
    for(int i = 0; i< n; i++) 
        if (degree[i] == 1) leaves.offer(i);

    while (!leaves.isEmpty()) { //剥一层叶子
        roots = new ArrayList<Integer>();   // 根就是最后一层叶子
        int leave_size = leaves.size();  // 这层叶子大小，把这层叶子剥掉
        for(int i = 0; i < leave_size; i++){
            int leaf = leaves.poll();  
            roots.add(leaf);        // 加入叶子
            degree[leaf]--;         // 叶子的度减去1
            for (int next : graph.get(leaf)) {  // 遍历连接叶子的节点
                if (degree[next] == 0) continue;   // 原本就是叶子，i.e.外层
                if (degree[next] == 2) leaves.offer(next); // 把这个节点变成叶子
                degree[next]--;
            }
        }       
    }
    return roots;
}