题目：310. 最小高度树
题目描述
文章来源：https://www.toymoban.com/news/detail-850232.html
代码与注释
func findMinHeightTrees(n int, edges [][]int) (ans []int) {
if n == 1 {
return []int{0}
}
g := make([][]int, n)
degree := make([]int, n) // 记录每个节点的度（之相连的边的数量）
for _, e := range edges { // 构建邻接表
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
degree[a]++
degree[b]++
}
q := []int{} // 通过队列存储度为 1 的节点（叶子节点）
for i, d := range degree {
if d == 1 {
q = append(q, i) // 存储所有叶子节点
}
}
for len(q) > 0 { // 把所有叶子节点剥离到最后一层，剩下的节点就可以作为最小高度树的根节点了
ans = []int{} // 清空 ans
for i := len(q); i > 0; i-- { // 把当前层的叶子节点都剥离
a := q[0] // 获取队列中的叶子节点
q = q[1:]
ans = append(ans, a)
for _, b := range g[a] { // 遍历 a 相邻的节点
degree[b]-- // 相邻节点的度-1
if degree[b] == 1 { // 新的叶子节点
q = append(q, b)
}
}
}
}
return ans // 最后剩下的节点就是最小高度树的根
}
主要学习如何记录每个节点的度文章来源地址https://www.toymoban.com/news/detail-850232.html
到了这里，关于【图论】拓补排序 - 邻接表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
