生活随笔
收集整理的这篇文章主要介绍了
LeetCode 310. 最小高度树（图 聪明的BFS，从外向内包围）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
文章目录
1. 题目
对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。
格式
该图包含 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_map
<int,unordered_set
<int>> g
;vector
<int> vertex
;queue
<int> q
;
public:vector
<int> findMinHeightTrees(int n
, vector
<vector
<int>>& 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_map
<int,unordered_set
<int>> g
;vector
<int> vertex
;queue
<int> q
;vector
<int> lastLv
;
public:vector
<int> findMinHeightTrees(int n
, vector
<vector
<int>>& edges
) {for(auto& e
: edges
){g
[e
[0]].insert(e
[1]);g
[e
[1]].insert(e
[0]);}bool visited
[n
];bool outSide
[n
];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:vector
<int> findMinHeightTrees(int n
, vector
<vector
<int>>& edges
) {if(n
== 1)return {0};int i
, tp
, size
;unordered_map
<int,unordered_set
<int>> g
;vector
<int> vertex
;queue
<int> 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)q
.push(i
);while(n
> 2){size
= q
.size();n
-= size
;while(size
--){tp
= q
.front();q
.pop();for(const int& id
: g
[tp
]){g
[id
].erase(tp
);if(g
[id
].size() == 1)q
.push(id
);}}}while(!q
.empty()){vertex
.push_back(q
.front());q
.pop();}return vertex
;}
};
总结
以上是生活随笔为你收集整理的LeetCode 310. 最小高度树（图 聪明的BFS，从外向内包围）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
