目录

拓扑排序与 BFS 剥除

拓扑排序（Topological Sort）的核心机制是基于节点“度”的迭代剥除（Degree-driven Pruning）。这一思想不仅能用于有向图依赖排序，还能推广到无向树的中心查找问题。

核心思想

D2 Diagram
qtopie.github.io

有向图：Kahn 算法（判环与拓扑排序）

在有向图中，利用拓扑排序检测环：若最终访问的节点数少于总节点数，说明图中存在环。

数据结构

概念变量作用
邻接表adjList [][]int记录节点指向的后继节点
入度数组indegree []int记录节点的未完成前置依赖数
队列queue []int存放当前入度为 0 的可访问节点

算法步骤

  1. 构建邻接表并统计各节点的入度 indegree。
  2. 将所有 indegree == 0 的节点入队。
  3. BFS 遍历：弹出队首节点 p，将其后继节点的入度减 1；若后继节点入度降为 0，则入队。
  4. 统计访问节点数 visitedCnt。若 visitedCnt < n，判定有环。

代码实现 (Go)

func canFinish(numCourses int, prerequisites [][]int) bool {
	adjList := make([][]int, numCourses)
	indegree := make([]int, numCourses)

	for _, p := range prerequisites {
		src, dest := p[1], p[0]
		adjList[src] = append(adjList[src], dest)
		indegree[dest]++
	}

	queue := make([]int, 0)
	for i := 0; i < numCourses; i++ {
		if indegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	visitedCnt := 0
	for len(queue) > 0 {
		p := queue[0]
		queue = queue[1:]
		visitedCnt++

		for _, c := range adjList[p] {
			indegree[c]--
			if indegree[c] == 0 {
				queue = append(queue, c)
			}
		}
	}

	return visitedCnt >= numCourses
}

环的判定原理

在有向环中，每个节点的入度均大于 0 且依赖环内其他节点，入度无法归零，因此无法入队，最终导致 visitedCnt < n。

无向树：剥洋葱算法（找树中心 / 最小高度树）

对于无向树，最小高度树（Minimum Height Trees, MHT）的根节点即为树的中心（最多有 1 或 2 个）。

数据结构

概念变量作用
邻接表adjList [][]int记录节点的相连邻居
度数组degree []int记录节点的边数（相连邻居数）
队列leaves []int存放当前轮次所有的叶子节点（degree == 1）

原理解析：分支长度与分层收敛

从树的质心点看各个方向的分支长度：

D2 Diagram
qtopie.github.io

分支长度定义为：$\text{分支长度} = \text{maxDepth}(\text{child}) + 1$。

从 a 出发的方向分支长度说明
往 b 方向$\text{maxDepth}(b) + 1 = 2$b 的最大深度为 1（挂有 e）
往 c 方向$\text{maxDepth}(c) + 1 = 1$c 是叶子节点（深度 0）
往 d 方向$\text{maxDepth}(d) + 1 = 1$d 是叶子节点（深度 0）

以 a 为根的树高度即最长分支：$\max(2, 1, 1) = 2$。

收敛推论：外层叶子节点距离质心的轮次取决于分支深度。必须按轮次**同步剥除（Level-order）**当前所有叶子，才能使收敛界面以相同速度向内缩减，直到剩余节点数 $\le 2$。

算法步骤

  1. 构建无向邻接表并计算每个节点的度 degree。
  2. 将所有 degree == 1 的叶子节点入队 leaves。
  3. 分层剥离：若剩余节点数 remaining > 2，按层将当前 leaves 全部出队，更新其邻居的度；邻居度变 1 则放入 newLeaves。
  4. 重复直至 remaining <= 2，剩余节点即为中心。

代码实现 (Go)

func findMinHeightTrees(n int, edges [][]int) []int {
	if n == 1 {
		return []int{0}
	}

	adjList := make([][]int, n)
	degree := make([]int, n)

	for _, edge := range edges {
		u, v := edge[0], edge[1]
		adjList[u] = append(adjList[u], v)
		adjList[v] = append(adjList[v], u)
		degree[u]++
		degree[v]++
	}

	leaves := make([]int, 0)
	for i := 0; i < n; i++ {
		if degree[i] == 1 {
			leaves = append(leaves, i)
		}
	}

	remaining := n
	for remaining > 2 {
		newLeaves := make([]int, 0)
		remaining -= len(leaves)

		for _, leaf := range leaves {
			degree[leaf] = 0
			for _, nbr := range adjList[leaf] {
				if degree[nbr] > 0 {
					degree[nbr]--
					if degree[nbr] == 1 {
						newLeaves = append(newLeaves, nbr)
					}
				}
			}
		}

		leaves = newLeaves
	}

	return leaves
}

BFS 入队机制对比

对比标准 BFS 与条件剥除 BFS 的入队条件：

范式对比

维度Kahn 算法（有向图判环）剥洋葱算法（无向树找中心）
核心指标入度 (indegree)度 (degree)
处理对象有向图无向树
边界节点入度为 0 的节点度为 1 的叶子节点
边更新机制单向更新后继入度双向更新邻居的度
队列处理方式逐个处理即可必须分层处理 (Level-order)
终止条件队列为空 (visitedCnt < n)剩余节点数 remaining <= 2

参考题目