扬中零壹网站建设,多功能创意产品设计,北京企业网站设计方案,希爱力文章目录1. 题目2. 解题2.1 暴力BFS2.2 聪明的BFS1. 题目
对于一个具有树特征的无向图#xff0c;我们可选择任何一个节点作为根。图因此可以成为树#xff0c;在所有可能的树中#xff0c;具有最小高度的树被称为最小高度树。给出这样的一个图#xff0c;写出一个函数找到…
文章目录1. 题目2. 解题2.1 暴力BFS2.2 聪明的BFS1. 题目
对于一个具有树特征的无向图我们可选择任何一个节点作为根。图因此可以成为树在所有可能的树中具有最小高度的树被称为最小高度树。给出这样的一个图写出一个函数找到所有的最小高度树并返回他们的根节点。
格式
该图包含 n 个节点标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表每一个边都是一对标签。
你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边 [0, 1]和 [1, 0] 是相同的因此不会同时出现在 edges 里。
示例 1:
输入: n 4, edges [[1, 0], [1, 2], [1, 3]]0|1/ \2 3 输出: [1]示例 2:
输入: n 6, edges [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]0 1 2\ | /3|4|5 输出: [3, 4]说明:根据树的定义树是一个无向图其中任何两个顶点只通过一条路径连接。 换句话说一个任何没有简单环路的连通图都是一棵树。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-height-trees 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 暴力BFS
从每个节点开始BFS记录高度选择最小的高度的起点即可节点很多的时候会超时
class Solution {unordered_mapint,unordered_setint g;vectorint vertex;queueint q;
public:vectorint findMinHeightTrees(int n, vectorvectorint edges) {for(auto e : edges){g[e[0]].insert(e[1]);g[e[1]].insert(e[0]);}bool visited[n];int minh INT_MAX, h;for(int i 0; i n; i){memset(visited, 0, sizeof(visited));h 0;visited[i] true;q.push(i);BFS(h,visited);if(h minh){minh h;vertex.clear();vertex.push_back(i);}else if(h minh)vertex.push_back(i);}return vertex;}void BFS(int h, bool* visited){int tp, size;while(!q.empty()){size q.size();while(size--){tp q.front();q.pop();for(const int id : g[tp]){if(!visited[id]){q.push(id);visited[id] true;}}}h;}}
};优化下
是最外围的节点是最外围的不用从他开始BFS高度肯定不是最小的见以下代码还是超时
class Solution {unordered_mapint,unordered_setint g;vectorint vertex;queueint q;vectorint lastLv;
public:vectorint findMinHeightTrees(int n, vectorvectorint edges) {for(auto e : edges){g[e[0]].insert(e[1]);g[e[1]].insert(e[0]);}bool visited[n];bool outSide[n];//是最外围的节点是最外围的不用从他开始BFS高度肯定不是最小的memset(outSide, 0, sizeof(outSide));int minh INT_MAX, h 0;for(int i 0; i n; i){if(minh 2 outSide[i])continue;memset(visited, 0, sizeof(visited));h 0;visited[i] true;q.push(i);BFS(h,visited,outSide);if(h minh){minh h;vertex.clear();vertex.push_back(i);}else if(h minh)vertex.push_back(i);}return vertex;}void BFS(int h, bool* visited, bool* outSide){int tp, size;while(!q.empty()){size q.size();lastLv.clear();while(size--){tp q.front();q.pop();for(const int id : g[tp]){if(!visited[id]){q.push(id);visited[id] true;lastLv.push_back(id);}}}h;}for(auto id : lastLv)outSide[id] true;}
};2.2 聪明的BFS
最低的高度树可能的root只有1个或者2个相当于把一个数组平分两半奇偶可能那么从图中最外围的节点开始找出入度为1把所有的出入度为1的节点push进入队列一层层的剥离节点到遍历的节点只剩下2个或者1时即找到答案
class Solution {
public:vectorint findMinHeightTrees(int n, vectorvectorint edges) {if(n 1)return {0};int i, tp, size;unordered_mapint,unordered_setint g;//图的邻接表vectorint vertex;queueint q;//队列for(auto e : edges){g[e[0]].insert(e[1]);//g[e[1]].insert(e[0]);}for(i 0; i n; i)if(g[i].size() 1)//出入度1,最外层的节点q.push(i);//进入队列while(n 2)//剩余节点大于2{size q.size();//在队列里的节点减去n - size;//剩余的节点个数nwhile(size--){tp q.front();//待删除的节点q.pop();for(const int id : g[tp]){g[id].erase(tp);if(g[id].size() 1)//id变成最外层了q.push(id);//进入队列待删}}}while(!q.empty()){vertex.push_back(q.front());q.pop();}return vertex;}
};
