力扣(LeetCode)310

题目地址：

https://leetcode-cn.com/probl...

题目描述：

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

格式

该图包含 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<Integer> 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<Integer,Integer>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<Integer> ans = new ArrayList(n);
           for(Map.Entry<Integer,Integer> entry:map.entrySet())
               if(entry.getValue() == min)ans.add(entry.getKey());
        
        
        return ans;
    }
    
    
}