【图论】拓补排序 – 邻接表

文章目录

• 题目：310. 最小高度树
• • 题目描述
  • 代码与注释

题目：310. 最小高度树

题目描述

代码与注释

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 // 最后剩下的节点就是最小高度树的根
}

主要学习如何记录每个节点的度