第六章 图、遍历与最短路径

---

1. 为什么图是数据结构课程的分水岭

线性结构处理的是一对一顺序，树结构处理的是层次关系，而图结构处理的是最一般的连接关系。到了图这一章，数据结构课程真正进入“复杂关系建模”的阶段。

图可以表示：

1. 城市与道路网络。
2. 社交关系。
3. 课程先修依赖。
4. 互联网拓扑。
5. 工作流和状态转移。

如果说树是“有约束的图”，那么图就是解除父子限制后的更一般模型。

2. 图的基本概念

图通常记作 G = (V, E)：

1. V 是顶点集合。
2. E 是边集合。

图可以进一步分为：

1. 无向图。
2. 有向图。
3. 带权图。
4. 稀疏图与稠密图。

3. 图的两种核心存储方式

3.1 邻接矩阵

用一个 n x n 矩阵表示顶点间是否有边。若图带权，则矩阵元素可存权重。

优点：

1. 判断两点是否直接相连是 O(1)。
2. 实现直观。

缺点：

1. 空间复杂度通常是 O(n^2)。
2. 对稀疏图非常浪费。

3.2 邻接表

每个顶点维护一个邻居列表。

优点：

1. 适合稀疏图。
2. 遍历边更高效。

缺点：

1. 判断任意两点是否相连通常不是 O(1)。

工程里大多数大规模图都更偏向邻接表。

4. Go 中的邻接表表示

最常见的教学表示是：

graph := map[int][]int{
    0: {1, 2},
    1: {2},
    2: {3},
    3: {},
}

如果是带权图，可以改成：

type Edge struct {
    To     int
    Weight int
}

graph := map[int][]Edge{
    0: {{To: 1, Weight: 4}, {To: 2, Weight: 1}},
}

5. 深度优先搜索 DFS

DFS 的核心思想是：沿一条路径尽量走深，走不下去再回退。这和栈的后进先出本质一致。

5.1 递归版 DFS

func DFS(graph map[int][]int, start int) []int {
    order := make([]int, 0)
    visited := make(map[int]bool)

    var dfs func(int)
    dfs = func(v int) {
        visited[v] = true
        order = append(order, v)
        for _, next := range graph[v] {
            if !visited[next] {
                dfs(next)
            }
        }
    }

    dfs(start)
    return order
}

DFS 的难点不在代码量，而在理解：

1. 为什么回退是自动发生的。
2. 为什么访问标记要尽早设置。
3. 为什么递归深度与图结构有关。

6. 广度优先搜索 BFS

BFS 的核心思想是按“层”推进，先访问距离起点更近的点。

func BFS(graph map[int][]int, start int) []int {
    order := make([]int, 0)
    visited := map[int]bool{start: true}
    q := []int{start}

    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        order = append(order, cur)
        for _, next := range graph[cur] {
            if visited[next] {
                continue
            }
            visited[next] = true
            q = append(q, next)
        }
    }
    return order
}

6.1 BFS 为什么能求无权图最短路

因为 BFS 按层推进，第一次到达某个节点时，所经过的边数就是最少的。

func ShortestPathUnweighted(graph map[int][]int, start int) map[int]int {
    dist := map[int]int{start: 0}
    q := []int{start}

    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        for _, next := range graph[cur] {
            if _, ok := dist[next]; ok {
                continue
            }
            dist[next] = dist[cur] + 1
            q = append(q, next)
        }
    }
    return dist
}

7. 拓扑排序：处理依赖关系

在有向无环图（DAG）中，拓扑排序能给出一种线性顺序，使得每条有向边 u -> v 都满足 u 在 v 前面。

典型场景：

1. 课程先修关系。
2. 编译任务依赖。
3. 工作流调度。

7.1 Kahn 算法

func TopoSort(graph map[int][]int, n int) []int {
    indegree := make([]int, n)
    for _, edges := range graph {
        for _, to := range edges {
            indegree[to]++
        }
    }

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

    order := make([]int, 0, n)
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        order = append(order, cur)
        for _, next := range graph[cur] {
            indegree[next]--
            if indegree[next] == 0 {
                q = append(q, next)
            }
        }
    }
    return order
}

若最终输出节点数少于总节点数，说明图中存在环。

8. 最短路径：从 BFS 到 Dijkstra

无权图最短路可以用 BFS，带非负权图最短路经典用 Dijkstra。它的核心思想是：每次从当前尚未确定的节点里，选出距离最小者进行扩展。

8.1 使用小根堆实现 Dijkstra

package graph

import (
    "container/heap"
    "math"
)

type Edge struct {
    To     int
    Weight int
}

type Item struct {
    Node int
    Dist int
}

type MinPQ []Item

func (pq MinPQ) Len() int            { return len(pq) }
func (pq MinPQ) Less(i, j int) bool  { return pq[i].Dist < pq[j].Dist }
func (pq MinPQ) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *MinPQ) Push(x any)         { *pq = append(*pq, x.(Item)) }
func (pq *MinPQ) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[:n-1]
    return item
}

func Dijkstra(graph map[int][]Edge, start int, n int) []int {
    dist := make([]int, n)
    for i := range dist {
        dist[i] = math.MaxInt
    }
    dist[start] = 0

    pq := &MinPQ{{Node: start, Dist: 0}}
    heap.Init(pq)

    for pq.Len() > 0 {
        item := heap.Pop(pq).(Item)
        if item.Dist > dist[item.Node] {
            continue
        }
        for _, e := range graph[item.Node] {
            nd := item.Dist + e.Weight
            if nd < dist[e.To] {
                dist[e.To] = nd
                heap.Push(pq, Item{Node: e.To, Dist: nd})
            }
        }
    }
    return dist
}

这个例子同时把图、堆、贪心思想串了起来，说明数据结构从来不是孤立知识点。

9. 并查集与图的连通性

除了 BFS/DFS，图的连通性问题还经常和并查集一起出现。对于“不断加入边，再问两点是否连通”这类问题，并查集往往比反复遍历更高效。

这说明图问题往往不是“只靠图结构本身”解决，而是要把前面学过的堆、队列、并查集一起调动起来。

10. 图这一章最容易犯的错误

1. 忘记 visited，导致死循环。
2. 把有向图和无向图的建边方式混在一起。
3. 稀疏图还强行用邻接矩阵，空间浪费严重。
4. 把 BFS 和 DFS 只当模板，不理解它们对应的搜索顺序。
5. 在有负权边的场景里误用 Dijkstra。

11. 本章小结

图结构之所以难，不是因为代码多，而是因为它把数据关系推广到了最一般情形。本章真正要掌握的是：

1. 图是连接关系最一般的抽象。
2. 邻接矩阵和邻接表分别适合不同密度场景。
3. DFS 对应“走深再回退”，BFS 对应“按层扩展”。
4. 最短路、拓扑排序、连通性，本质上都是在图上利用不同结构约束。

下一章会把视角从“关系表达”切回“有序处理”，进入查找、排序与选择问题。

12. 继续深入

图结构真正拉开难度差距的，往往不是 BFS 和 DFS 本身，而是它们如何与堆、并查集、动态规划结合：

1. 最小生成树里的 Kruskal 与 Prim。
2. 拓扑排序如何落到课程安排、构建系统、关键路径分析上。
3. DAG 上的动态规划为什么会比一般图简单得多。

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