leetcode 310. Minimum Height Trees 图的构建+最小高度树+DFS深度优先遍历+拓扑排序

古城微笑少年丶 2022-06-07 00:59 118阅读 0赞

For a 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:

Given n = 4, edges = \[\[1, 0\], \[1, 2\], \[1, 3\]\]

0
        |
        1
       / \
      2   3

return \[1\]

Example 2:

Given n = 6, edges = \[\[0, 3\], \[1, 3\], \[2, 3\], \[4, 3\], \[5, 4\]\]

0  1  2
      \ | /
        3
        |
        4
        |
        5

return \[3, 4\]

Note:

(1) 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.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

这道题最直接的方法就是遍历所有的节点构成来的树，然后得到最低的树，图的存储可以按照矩阵存储，或者使用Hash存储前边和后边，然后DFS遍历即可，但是超时了。 后来网上看到了一个做法，使用拓扑排序的做法，挺不错的，直接上代码吧！

**这道题需要注意的是要学会以HashSet存储图的边。**

代码如下：

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    
    
    /*
     * 求给定图中，能形成树的最矮的树。
     * 第一直觉就是BFS，跟Topological Sorting的Kahn方法很类似，
     * 利用无向图每个点的degree来计算。但是却后继无力，
     * */
    class Solution 
    {
        public List<Integer> findMinHeightTrees(int n, int[][] edges)
        {
            List<Integer> leaves = new ArrayList<>();
            if(n <= 1) 
            {
                leaves.add(0);
                return  leaves;
            }
    
            Map<Integer, Set<Integer>> graph = new HashMap<>();         
            for(int i = 0; i < n; i++) 
                graph.put(i, new HashSet<Integer>());
            for(int[] edge : edges) 
            {
                graph.get(edge[0]).add(edge[1]);
                graph.get(edge[1]).add(edge[0]);
            }
    
            for(int i = 0; i < n; i++) 
            {
                if(graph.get(i).size() == 1)
                    leaves.add(i);
            }
            while(n > 2) 
            {
                n -= leaves.size();
                List<Integer> newLeaves = new ArrayList<>();
                for(int leaf : leaves) 
                {
                    for(int newLeaf : graph.get(leaf)) 
                    {
                        graph.get(leaf).remove(newLeaf);
                        graph.get(newLeaf).remove(leaf);
                        if(graph.get(newLeaf).size() == 1) 
                            newLeaves.add(newLeaf);
                    }
                }
                leaves = newLeaves;
            }
            return leaves;
        }   
    
    
        /*
         * 
         * 我使用的是矩阵作为图的存储，
         * DFS 超时
         * */
        public List<Integer> findMinHeightTrees11(int n, int[][] edges) 
        {
            List<Integer> res=new ArrayList<>();
            if(n<=0 || edges==null)
                return res;
            else if(n<=1)
            {
                res.add(0);
                return res;
            }
    
            boolean[][] mat=new boolean[n][n];
            for(int[] index : edges)
                mat[index[0]][index[1]]=mat[index[1]][index[0]]=true;
    
            int[] height=new int[n];
            boolean[] visit=new boolean[n];
            int min=Integer.MAX_VALUE;
    
            for(int i=0;i<n;i++)
            {
                height[i]=getHeight(mat,visit,i);
                min=Math.min(min,height[i]);
            }
    
            for(int i=0;i<n;i++)
            {
                if(height[i]==min)
                    res.add(i);
            }
            return res;
        }
    
        public int getHeight(boolean[][] mat, boolean[] visit,int root)
        {
            if(visit[root]==false)
            {
                visit[root]=true;
                int maxHeight=0;
                for(int i=0;i<mat.length;i++)
                {
                    if(i!=root && mat[root][i])
                        maxHeight=Math.max(maxHeight, getHeight(mat, visit, i)+1);  
                }       
                visit[root]=false;
                return maxHeight;
            }else 
                return 0;
        }
    }

下面是C++的做法，最简单和最直接的方法就是直接对每一个结点做DFS深度优先遍历，求解每一个数的高度，然后比较得到最小值，这样做的肯定会超时，后来在网上发现了一道使用BFS广度优先的做法，方法很棒，类似拓扑排序的做法，很棒的做法

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) 
        {
            if (n == 1)
                return vector<int>(1, 0);
    
            map<int, set<int>> mat;
            for (auto i : edges)
            {
                mat[i.first].insert(i.second);
                mat[i.second].insert(i.first);
            }
    
            vector<int> leaves;
            for (auto i : mat)
            {
                if (i.second.size() == 1)
                    leaves.push_back(i.first);
            }
    
            while (n > 2)
            {
                n -= leaves.size();
                vector<int> one;
                for (auto from : leaves)
                {
                    auto next = mat[from];
                    for (auto to : next)
                    {
                        mat[from].erase(to);
                        mat[to].erase(from);
                        if (mat[to].size() == 1)
                            one.push_back(to);
                    }
                }
                leaves = one;
            }
            return leaves;
        }
    };