袋鼠知识库

主题

图结构进阶：最小生成树、拓扑应用与更高阶建模 ​

1. 图进阶真正难在哪里 ​

基础图论里，BFS、DFS、最短路已经足够解决很多问题；但一旦进入进阶阶段，难点会立刻转向“多种结构的联动”：

  1. 最小生成树会把图、堆、并查集放到同一个问题里。
  2. 拓扑排序会和依赖管理、动态规划、关键路径分析结合。
  3. 图不再只是“遍历一遍”，而是要围绕具体业务目标建立合适模型。

这就是为什么图被很多课程看作数据结构和算法之间最明显的交汇点。

2. 最小生成树的目标是什么 ​

对于一个连通无向带权图，最小生成树（MST, Minimum Spanning Tree）要选出 n-1 条边：

  1. 让所有顶点连通。
  2. 不产生环。
  3. 总权值最小。

它非常适合抽象：

  1. 通信网络最低铺设成本。
  2. 电网、道路、管线最小连通骨架。
  3. 聚类算法中的某些底层步骤。

3. Kruskal：按边从小到大选，配合并查集判环 ​

Kruskal 的思想很干净：

  1. 先按边权从小到大排序。
  2. 依次尝试加入当前最小边。
  3. 若这条边连接的两个点原本不连通，就选它。
  4. 若会成环，就跳过。

判断“会不会成环”的关键工具就是并查集。

3.1 Go 实现 Kruskal ​

go
package mst

import "sort"

type Edge struct {
    U int
    V int
    W int
}

type DSU struct {
    parent []int
    rank   []int
}

func NewDSU(n int) *DSU {
    p := make([]int, n)
    r := make([]int, n)
    for i := range p {
        p[i] = i
    }
    return &DSU{parent: p, rank: r}
}

func (d *DSU) Find(x int) int {
    if d.parent[x] != x {
        d.parent[x] = d.Find(d.parent[x])
    }
    return d.parent[x]
}

func (d *DSU) Union(a, b int) bool {
    ra, rb := d.Find(a), d.Find(b)
    if ra == rb {
        return false
    }
    if d.rank[ra] < d.rank[rb] {
        ra, rb = rb, ra
    }
    d.parent[rb] = ra
    if d.rank[ra] == d.rank[rb] {
        d.rank[ra]++
    }
    return true
}

func Kruskal(n int, edges []Edge) ([]Edge, int) {
    sort.Slice(edges, func(i, j int) bool {
        return edges[i].W < edges[j].W
    })

    dsu := NewDSU(n)
    mst := make([]Edge, 0, n-1)
    total := 0

    for _, e := range edges {
        if dsu.Union(e.U, e.V) {
            mst = append(mst, e)
            total += e.W
        }
    }
    return mst, total
}

3.2 Kruskal 的复杂度来自哪里 ​

  1. 排序边：O(m log m)
  2. 并查集操作：均摊近似常数

因此总成本通常主要由排序主导。

4. Prim：从一个点出发逐步向外扩展 ​

Prim 和 Kruskal 的视角不同。它不是先看全局最小边，而是：

  1. 从一个起点开始。
  2. 维护“已选顶点集合”和“未选顶点集合”之间的最小跨边。
  3. 每次把代价最小的新顶点纳入生成树。

它和 Dijkstra 在形式上很像，都常用小根堆实现，但目标不同：

  1. Dijkstra 最小化“起点到各点距离”。
  2. Prim 最小化“生成树总边权”。

4.1 Prim 适合什么场景 ​

若图以邻接表给出，而且你更自然地从“当前连通块向外扩张”去思考，Prim 非常顺手。若图边集单独列出，并查集好用，Kruskal 会更直接。

5. 最小生成树的本质不是模板，而是“贪心 + 无环约束” ​

无论 Kruskal 还是 Prim，最核心的思想都是：

  1. 每一步尽量选当前最优的边。
  2. 但必须保证整体不形成环。

这类问题之所以能贪心，是因为最小生成树满足割性质与环性质。教学上至少要知道：它不是“碰巧能贪心”，而是有严格理论支撑。

6. 拓扑排序不只是排顺序，而是依赖系统的骨架 ​

拓扑排序适用于 DAG。很多人只把它记成“入度为 0 入队”，但它真正的价值在于：
它把依赖关系转成了可执行顺序。

典型应用：

  1. 课程安排。
  2. 编译依赖。
  3. 工作流引擎。
  4. 任务编排系统。
  5. 数据处理流水线。

7. 课程安排问题：判断能否修完全部课程 ​

假设 u -> v 表示学 v 之前必须先学 u。如果图里有环，就说明出现互相依赖，课程无法全部完成。

go
func CanFinish(numCourses int, prereq [][2]int) bool {
    graph := make([][]int, numCourses)
    indegree := make([]int, numCourses)

    for _, p := range prereq {
        pre, course := p[0], p[1]
        graph[pre] = append(graph[pre], course)
        indegree[course]++
    }

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

    count := 0
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        count++
        for _, next := range graph[cur] {
            indegree[next]--
            if indegree[next] == 0 {
                q = append(q, next)
            }
        }
    }
    return count == numCourses
}

这段代码不是在“背图算法”，而是在回答业务问题：依赖系统里是否存在死锁式环路。

8. DAG 上的动态规划：为什么拓扑序这么重要 ​

一旦图是 DAG，很多原本在一般图里很难做的动态规划就会变得清晰，因为拓扑序保证了“前驱状态先于后继状态被处理”。

例如求 DAG 中从起点到各点的最长路径：

go
func LongestPathDAG(graph map[int][]Edge, topo []int, start int, n int) []int {
    const negInf = -1 << 60
    dist := make([]int, n)
    for i := range dist {
        dist[i] = negInf
    }
    dist[start] = 0

    for _, u := range topo {
        if dist[u] == negInf {
            continue
        }
        for _, e := range graph[u] {
            if dist[u]+e.Weight > dist[e.To] {
                dist[e.To] = dist[u] + e.Weight
            }
        }
    }
    return dist
}

这就是很多工程场景中的“关键路径”原型。

9. 拓扑排序在工程中的几个高频落点 ​

9.1 构建系统 ​

编译一个大型项目时，某些模块必须先生成，另一些才能继续。拓扑排序决定构建顺序，环则意味着设计有问题。

9.2 工作流调度 ​

任务 A 完成后才能启动任务 B、C；B 和 C 都完成后才启动 D。这样的流程图天然就是 DAG。

9.3 数据血缘分析 ​

报表、数据仓库、ETL 链路中的上下游关系，也常用 DAG 建模。

10. 更高阶建模：同一个问题未必只有一种图模型 ​

图进阶真正体现水平的地方在于建模。举例：

  1. 课程安排可建成课程点 + 先修边。
  2. 路网最短路可建成路口点 + 道路边。
  3. 任务调度可建成任务点 + 依赖边。
  4. 物流中转可建成状态点 + 转移边。

同一现实问题，节点是什么、边是什么、权重代表什么，都会影响后续能否用 BFS、Dijkstra、MST 或拓扑 DP 高效求解。

11. 最小生成树与最短路径不要混 ​

这是非常高频的误区。

  1. 最小生成树追求的是“让整个图连起来，总成本最小”。
  2. 最短路径追求的是“从某个起点到某个终点或所有点的距离最小”。

一棵最小生成树上，起点到终点的路径不一定是原图最短路径；反过来，所有最短路径边也不一定能组成最小生成树。

12. 图进阶这一页的真正收获 ​

这页最核心的不是又多学了几个模板，而是：

  1. 你开始同时调动堆、并查集、拓扑序、动态规划。
  2. 你开始意识到“图算法本质上是建模 + 结构 + 约束”的组合。
  3. 你能区分不同目标函数下应当选择哪类图算法。

如果这些点建立起来，图这一块就已经进入真正的进阶层。