题目地址：

题目描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。

解答：

这一题就是求最短路径，不过求的是每一个点到任意一点的最短路径。我们可以使用弗洛伊德算法来求解。可惜的是该算法的复杂度是O(N三次方)。不过还有别的方法来求最短路径，宽度优先搜索，对于权值相同的图，可以用宽度优先搜索来求解某一点到任意一点的最短路径。宽度优先是O(N)的复杂度。求解N个点的，于是就可以把复杂度变为O(N二次方)。注意：下面的代码是隐含使用宽度优先搜索，没有使用队列。java ac代码：

class Solution {    public List
    
      findMinHeightTrees(int n, int[][] edges) {            int[][] matrix = new int[n][n];        int max = Integer.MAX_VALUE;         for(int i = 0;i < n;i++)            for(int j = 0;j < n;j++)                matrix[i][j] = max;                 for(int i = 0;i < edges.length;i++){            int begin = edges[i][0];            int end = edges[i][1];              matrix[begin][end] = 1;            matrix[end][begin] = 1;            for(int j = 0;j < n;j++)                if(matrix[begin][j] == max&&matrix[end][j] != max)                    matrix[begin][j] = matrix[j][begin] = 1+matrix[end][j];                else if(matrix[end][j] == max&&matrix[begin][j] != max)                    matrix[end][j] = matrix[j][end] = 1+matrix[begin][j];                             }                 for(int i = 0;i < n;i++)            matrix[i][i] = 0;                                                                HashMap
     
      map = new HashMap(1<<10);           int min = max;            for(int i = 0;i < n;i++){               int temp = -1;               for(int j = 0;j < n;j++)               temp = Math.max(temp,matrix[i][j]);               map.put(i,temp);              min = Math.min(temp,min);            }           List
      
        ans = new ArrayList(n);           for(Map.Entry
       
         entry:map.entrySet())               if(entry.getValue() == min)ans.add(entry.getKey());                        return ans;    }        }