图算法：DFS、BFS、拓扑排序、最短路径

#数据结构 · #算法 · #图 · #DFS · #BFS · #拓扑排序 · #最短路径 · #Dijkstra · #A星

图是描述事物间关系的通用模型——网络拓扑、代码依赖、社交关系、路径规划都离不开图。本文聚焦有向图核心算法。

1. 图的表示

1.1 邻接矩阵 vs 邻接表

邻接矩阵:                    邻接表:
  A B C D                    A → [B, C]
A 0 1 1 0                    B → [D]
B 0 0 0 1                    C → [D]
C 0 0 0 1                    D → []
D 0 0 0 0

维度	邻接矩阵	邻接表
空间	O(V²)	O(V+E)
判断边 (u,v)	O(1)	O(degree(u))
遍历邻居	O(V)	O(degree(u))
适用	稠密图	稀疏图（最常用）
矩阵乘法优化	✅	❌

工程实践：绝大多数场景用邻接表。

2. 深度优先搜索（DFS）

2.1 递归实现

func dfs(graph map[int][]int, node int, visited map[int]bool) {
    visited[node] = true
    fmt.Println("visit", node)
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            dfs(graph, neighbor, visited)
        }
    }
}

时间复杂度 O(V + E)，空间复杂度 O(V)（递归栈深度）。

2.2 三色标记法（检测环 + 拓扑排序）

const (
    White = iota // 未访问
    Gray         // 正在访问（在递归栈中）
    Black        // 访问完成
)

func dfs_color(graph map[int][]int, node int, color []int) bool {
    color[node] = Gray
    for _, neighbor := range graph[node] {
        if color[neighbor] == Gray {
            return false  // 发现后向边 → 有环!
        }
        if color[neighbor] == White {
            if !dfs_color(graph, neighbor, color) {
                return false
            }
        }
    }
    color[node] = Black
    // 拓扑排序: 此时将 node 入栈（后序遍历）
    return true
}

2.3 应用场景

场景	说明
环检测	三色标记法，发现 Gray→Gray 的边
拓扑排序	Black 顺序的逆序
连通分量	无向图 DFS 遍历次数 = 连通分量数
强连通分量	Kosaraju/Tarjan 算法（有向图）
桥与割点	Tarjan 算法的 low-link 值

2.4 图找环——多种解法的完整对比

图中检测环是面试高频题，不同图类型有不同最优解法：

═══════════════════════════════════════════════════════════════
有向图找环 — 4 种方法对比
═══════════════════════════════════════════════════════════════

方法 1: DFS 三色标记法（最推荐）
  原理: 遍历时标记 White/Gray/Black
        发现 Gray→Gray 的边 = 后向边 = 有环
  时间: O(V+E)
  空间: O(V) (颜色数组 + 递归栈)
  优点: 可以同时做拓扑排序、找环路径
  缺点: 递归深度可能很大（深图需要显式栈）

方法 2: Kahn 算法（BFS + 入度）
  原理: 反复删除入度为 0 的节点
        如果最终还有节点剩余 → 有环
  时间: O(V+E)
  空间: O(V) (入度数组 + 队列)
  优点: 无递归，适合大图；同时得到拓扑排序
  缺点: 不能直接给出环的路径

方法 3: 并查集（仅适用于无向图）
  原理: 遍历每条边 (u,v)
        如果 u 和 v 已经在同一集合 → 有环
  时间: O(E × α(V)) ≈ O(E)
  空间: O(V)
  优点: 实现简单，适合动态加边
  缺点: 不适用于有向图！

方法 4: 拓扑排序失败检测
  原理: 尝试拓扑排序，如果无法排完所有节点 → 有环
  时间: O(V+E)
  空间: O(V)
  优点: 与方法 2 本质相同
  缺点: 同方法 2

═══════════════════════════════════════════════════════════════
链表找环 — Floyd 龟兔算法
═══════════════════════════════════════════════════════════════

  快慢指针:
    slow 每次走 1 步，fast 每次走 2 步
    如果有环 → fast 一定会追上 slow（在环内相遇）
    如果无环 → fast 先到达 nil

  找环入口:
    相遇后，将 slow 重置到 head
    slow 和 fast 都每次走 1 步
    再次相遇的位置 = 环入口

  数学证明:
    设 head 到环入口距离 = a
    环入口到相遇点距离 = b
    相遇点到环入口距离 = c (环长 = b + c)

    相遇时:
      slow 走了: a + b
      fast 走了: a + b + n(b+c)  (n 为 fast 在环内多绕的圈数)
      fast = 2 × slow → a + b + n(b+c) = 2(a+b)
      → a = n(b+c) - b = (n-1)(b+c) + c
      → a ≡ c (mod 环长)
      → 从 head 和相遇点同时走，走 a 步后在环入口相遇 ✅

  时间: O(n), 空间: O(1)

═══════════════════════════════════════════════════════════════
选择指南
═══════════════════════════════════════════════════════════════

  | 场景 | 推荐方法 | 原因 |
  |------|---------|------|
  | 有向图判环 | DFS 三色标记 | 最通用，可找环路径 |
  | 有向图拓扑排序+判环 | Kahn BFS | 无递归，适合大图 |
  | 无向图判环 | 并查集 | 实现最简单 |
  | 链表判环 | Floyd 快慢指针 | O(1) 空间 |
  | 动态加边判环 | 并查集 | 增量式，O(α(n)) |
  | 找所有环 | DFS + 回溯 | 需要记录路径 |
  | 找最小环 | BFS (无权) / Floyd (有权) | 不同权重不同方法 |

mermaid

flowchart LR
    subgraph DFS_T["DFS 遍历（栈/递归）"]
        direction TB
        A1((1)) --> B1((2)) --> D1((4))
        A1 --> C1((3)) --> E1((5))
        C1 --> F1((6))
    end

    subgraph BFS_T["BFS 遍历（队列）"]
        direction TB
        A2((1)) --> B2((2))
        A2 --> C2((3))
        B2 --> D2((4))
        B2 --> E2((5))
        C2 --> F2((6))
    end

    DFS_T -.- DFS_O["DFS 顺序: 1→2→4→3→5→6<br/>先深入, 再回溯<br/>适合: 全路径探索、环检测"]
    BFS_T -.- BFS_O["BFS 顺序: 1→2→3→4→5→6<br/>逐层扩展<br/>适合: 最短路径、层级遍历"]

    style DFS_O fill:#F44336,color:#fff
    style BFS_O fill:#2196F3,color:#fff

3. 广度优先搜索（BFS）

3.1 队列实现

func bfs(graph map[int][]int, start int) {
    visited := map[int]bool{start: true}
    queue := []int{start}

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        fmt.Println("visit", node)
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
}

时间复杂度 O(V + E)，空间复杂度 O(V)。

2.2 BFS vs DFS

维度	DFS	BFS
数据结构	栈（递归/显式）	队列
最短路径	❌	✅（无权图）
空间（树状图）	O(h) 树高度	O(w) 树宽度
适用	全路径探索、回溯	层级遍历、最短路径
内存（宽图）	更好	可能爆炸

2.3 应用

无权图最短路径（BFS 天然性质）
Web 爬虫（BFS 按深度逐层抓取）
社交网络"几度人脉"
Git 的 git bisect（二分查找的 BFS 变体）

4. 拓扑排序（Topological Sort）

4.1 定义

对有向无环图（DAG），给出一个线性序列，使得每条边 u→v 满足 u 在 v 之前。

4.2 Kahn 算法（BFS + 入度）

func kahn(graph map[int][]int, V int) []int {
    indegree := make([]int, V)
    for _, neighbors := range graph {
        for _, v := range neighbors {
            indegree[v]++
        }
    }

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

    result := []int{}
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        result = append(result, u)
        for _, v := range graph[u] {
            indegree[v]--
            if indegree[v] == 0 {
                queue = append(queue, v)
            }
        }
    }

    if len(result) != V {
        // 存在环！
        return nil
    }
    return result
}

4.3 DFS 后序遍历法

DFS Black 顺序的逆序 = 拓扑排序。好记："最先变 Black 的最后输出"。

4.4 应用

Make/Bazel 构建系统：确定编译顺序
包管理器：解决依赖关系（apt、npm、cargo）
课程安排：先修课程 → 后续课程

// LeetCode 207: 课程表 — 判断是否能完成所有课程
// n 门课, prerequisites = [[1,0],[2,1]] → 1 依赖 0, 2 依赖 1
func canFinish(n int, prerequisites [][]int) bool {
    graph := make([][]int, n)
    indegree := make([]int, n)

    for _, p := range prerequisites {
        from, to := p[1], p[0]
        graph[from] = append(graph[from], to)
        indegree[to]++
    }

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

    visited := 0
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        visited++
        for _, v := range graph[u] {
            indegree[v]--
            if indegree[v] == 0 { queue = append(queue, v) }
        }
    }
    return visited == n // 是否能修完所有课
}

// LeetCode 210: 课程表 II — 返回修课顺序
func findOrder(n int, prerequisites [][]int) []int {
    // ... 同上 BFS 拓扑排序，返回 result 切片即可
    // 注意: 如果 len(result) != n → 有环 → 返回 []
}

text

拓扑排序解决的核心问题: 给定 N 个节点和 M 对依赖关系，是否存在一种遍历顺序既不违反依赖又能遍历所有节点？

应用场景:
  - 课程安排: prerequisites[i] = [a, b] → 想修 a 必须先修 b
  - 项目管理: Task B 依赖 Task A → 先排 A 再排 B
  - 符号解析: 链接器解决 .o 文件之间的符号依赖
  - 数据管道: Airflow DAG 中确定 Task 执行顺序

有环检测: visited != N → 存在环 → 不存在合法拓扑序

任务调度：Airflow/DAG 工作流
Terraform 资源依赖图

5. 最短路径

5.1 Dijkstra — 单源最短路径

适用：非负权图。

import "container/heap"

func dijkstra(graph [][]Edge, start int) []int {
    dist := make([]int, len(graph))
    for i := range dist { dist[i] = math.MaxInt32 }
    dist[start] = 0

    pq := &PriorityQueue{&Item{node: start, dist: 0}}
    heap.Init(pq)

    for pq.Len() > 0 {
        u := heap.Pop(pq).(*Item).node
        for _, edge := range graph[u] {
            if dist[u]+edge.w < dist[edge.v] {
                dist[edge.v] = dist[u] + edge.w
                heap.Push(pq, &Item{node: edge.v, dist: dist[edge.v]})
            }
        }
    }
    return dist
}

实现	时间复杂度
数组 + 扫描	O(V²) — 稠密图最优
二叉堆	O((V+E) log V)
斐波那契堆	O(E + V log V) — 理论最优

mermaid

sequenceDiagram
    participant PQ as 优先队列
    participant D as dist[] 距离数组
    participant G as 图

    Note over PQ,G: 从 A 到各点的最短路径 (边权标注)

    D->>D: dist[A]=0, 其他=∞
    PQ->>PQ: 初始: [A:0]

    rect rgb(240, 248, 255)
        PQ->>D: Pop A(dist=0)
        D->>G: 松弛 A→B(4): dist[B]=4
        D->>G: 松弛 A→C(2): dist[C]=2
        PQ->>PQ: 插入 B:4, C:2
    end

    rect rgb(255, 248, 240)
        PQ->>D: Pop C(dist=2, 最小)
        D->>G: 松弛 C→B(1): 2+1=3 < 4 ➜ dist[B]=3
        D->>G: 松弛 C→D(5): dist[D]=7
        PQ->>PQ: 更新 B:3, 插入 D:7
    end

    rect rgb(240, 255, 240)
        PQ->>D: Pop B(dist=3)
        D->>G: 松弛 B→D(2): 3+2=5 < 7 ➜ dist[D]=5
        PQ->>PQ: 更新 D:5
    end

    Note over D: 最终: A=0, B=3, C=2, D=5

Dijkstra 不能处理负权边：一旦节点被标记为"已处理"，dist 不再更新，而负权边可能产生更短路径。

5.2 Bellman-Ford — 处理负权边

O(VE)，可以检测负权环（多跑一轮还有更新 → 有负环）。

5.3 Floyd-Warshall — 全源最短路径

// O(V³) 动态规划，三重循环
for k := 0; k < n; k++ {
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if dist[i][k]+dist[k][j] < dist[i][j] {
                dist[i][j] = dist[i][k] + dist[k][j]
            }
        }
    }
}

5.4 A* — 带启发式的最短路径

Dijkstra + 启发函数 h(n)（估计到终点的距离）。游戏寻路、地图导航的核心算法。

5.5 算法选择指南

场景	算法	复杂度
非负权，单源	Dijkstra	O(E log V)
有负权边	Bellman-Ford	O(VE)
全源	Floyd-Warshall	O(V³)
无权图	BFS	O(V+E)
DAG	拓扑排序 DP	O(V+E)
有启发信息	A*	O(E) 实际

6. 最小生成树（MST）

6.1 Kruskal — 边排序 + 并查集

// 1. 所有边按权重排序
// 2. 从小到大取边，如果不形成环（并查集判断），则加入 MST
// O(E log E)，适合稀疏图

6.2 Prim — 类似 Dijkstra

// 1. 从任意节点开始
// 2. 用优先队列维护"当前 MST 到外部节点的最短边"
// O(E log V)，适合稠密图

应用：网络布线、电路设计、聚类分析。

7. 各语言图的实现对比

语言	内置图支持	备注
Go	❌	需自建，可用 `map[Node][]Edge`
C++	❌（但有 Boost.Graph）	`vector<vector<int>>`
Python	❌（但有 networkx）	`dict` + `list`
Rust	❌（但有 petgraph）	`HashMap<Node, Vec<Edge>>`
Java	❌（但有 JGraphT）

7.1 现实系统中的图

系统	图的表达	算法
Git	DAG（commit 形成有向无环图）	拓扑排序、`git bisect`
Make/Bazel	DAG（构建依赖）	拓扑排序并行调度
Terraform	DAG（资源依赖）	拓扑排序 + 并行 apply
Kubernetes Scheduler	加权有向图（节点- Pod 亲和性）	约束满足 + 打分
Nginx Upstream	加权有向图（后端健康检查）	Dijkstra 变体（加权轮询）

8. 强连通分量（SCC）— 有向图的骨架

强连通分量：有向图中，任意两个节点互相可达的最大子图。

应用:
  - 静态分析中的循环检测（循环 = SCC）
  - 社交网络中的社区发现
  - 编译器中的死代码消除

8.1 Kosaraju 算法（两次 DFS）

1. 对原图做 DFS，记录节点的完成时间（Black 顺序）
2. 反转所有边（转置图）
3. 按完成时间逆序，在转置图上做 DFS
   → 每次 DFS 访问到的节点构成一个 SCC

复杂度: O(V+E)，两次 DFS
直觉: 在转置图上，SCC 之间的边方向反转 →
      从"没有出边的 SCC"开始探索 → 不会跨越 SCC

8.2 Tarjan 算法（单次 DFS）

比 Kosaraju 更高效：一次 DFS + 维护 dfn（发现时间）和 low（能回溯到的最早 dfn）。

func tarjan(graph [][]int, u int, dfn, low []int, stack []int, onStack []bool, time *int, sccs *[][]int) {
    dfn[u], low[u] = *time, *time
    *time++
    stack = append(stack, u)
    onStack[u] = true

    for _, v := range graph[u] {
        if dfn[v] == 0 { // 未访问
            tarjan(graph, v, dfn, low, stack, onStack, time, sccs)
            low[u] = min(low[u], low[v])
        } else if onStack[v] { // 在栈中 → 后向边
            low[u] = min(low[u], dfn[v])
        }
    }

    // u 是 SCC 的根
    if low[u] == dfn[u] {
        scc := []int{}
        for {
            v := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            onStack[v] = false
            scc = append(scc, v)
            if v == u { break }
        }
        *sccs = append(*sccs, scc)
    }
}

9. 最大流（Max Flow）

9.1 Ford-Fulkerson 方法

残差网络 + 增广路径:
1. 初始化所有边的流量为 0
2. 在残差网络中找一条从 s 到 t 的路径（增广路径）
3. 找到路径的瓶颈容量 → 沿路径增加流量
4. 更新残差网络（正向减容量，反向加容量）
5. 重复直到没有增广路径

核心洞见: 反向边允许"撤销"之前的流量分配

9.2 各实现的复杂度

算法	复杂度	增广路径找法	特点
Ford-Fulkerson	$O (E \cdot f_{m a x})$	DFS	容量为整数时终止
Edmonds-Karp	$O (V E^{2})$	BFS（最短增广路）	保证多项式时间
Dinic	$O (V^{2} E)$ （一般图） $O (E \sqrt{V})$ （二分图）	BFS分层 + DFS多路增广	实际最快
Push-Relabel	$O (V^{2} E)$	-	理论与工程均优

9.3 最大流 = 最小割

最大流最小割定理：网络中从 s 到 t 的最大流 = 最小割的容量。

应用：网络可靠性分析、图像分割（Graph Cut）、棒球淘汰问题。

10. A* 搜索深入

10.1 启发式函数的设计

A* 的性能完全取决于启发函数 $h (n)$ 的质量：

f(n) = g(n) + h(n)
  g(n) = 从起点到 n 的实际代价
  h(n) = 从 n 到终点的估计代价（启发式）

关键约束: h(n) 必须 ≤ 实际代价（admissible，可容许）
        → 保证 A* 找到最优解
        → 且 h 越大（越接近真实代价），A* 扩展的节点越少

10.2 常见启发式函数

场景	启发式	是否 admissible
网格地图	曼哈顿距离	✅（无对角线移动时）
网格地图	欧几里得距离	✅
网格地图	切比雪夫距离	✅（8 方向移动）
15 数码	曼哈顿距离和	✅
导航	直线距离	✅

10.3 Dijkstra 与 A* 的关系

Dijkstra: f(n) = g(n)         (h(n) = 0)
A*:       f(n) = g(n) + h(n)  (h(n) 引导搜索方向)

当 h(n) = 0: A* 退化为 Dijkstra
当 h(n) 完美时: A* 只沿最优路径扩展 → O(路径长度)
当 h(n) 过大时(不可容许): A* 变成贪心 → 可能错过最优

11. 经典问题的多种解法对比

11.1 TopK 问题——从 N 个元素中找最大的 K 个

═══════════════════════════════════════════════════════════════
5 种解法的完整对比 (N=1亿, K=100)
═══════════════════════════════════════════════════════════════

方法 1: 全排序
  算法: sort(arr); return arr[N-K:]
  时间: O(N log N) = 1亿 × 27 ≈ 27 亿次比较
  空间: O(N) 或 O(log N)
  优点: 实现最简单
  缺点: 做了大量无用功（只需要 K 个，却排了全部）
  适用: K ≈ N 时（需要大部分有序结果）

方法 2: 大小为 K 的最小堆 ⭐ 最推荐
  算法: 维护 K 个元素的最小堆，遍历所有元素
        新元素 > 堆顶 → 替换堆顶 + heapify
  时间: O(N log K) = 1亿 × 7 ≈ 7 亿次操作
  空间: O(K) = 100 个元素
  优点: 支持流式数据、空间极小、实现简单
  缺点: 结果无序（需要额外排序）
  适用: K << N、数据流式到达、内存受限 ✅

方法 3: 快速选择 (Quickselect)
  算法: 类似快排，但只递归包含第 K 大的那一侧
  时间: O(N) 平均, O(N²) 最坏
  空间: O(N)（需要全部数据在内存中）
  优点: 平均最快（线性时间）
  缺点: 不支持流式、最坏 O(N²)、修改原数组
  适用: 数据全在内存、不需要有序结果

方法 4: BFPRT (中位数的中位数)
  算法: 确定性选择第 K 大，最坏 O(N)
  时间: O(N) 最坏保证
  空间: O(N)
  优点: 理论最优
  缺点: 常数因子大（~5N），实际比 Quickselect 慢
  适用: 需要最坏情况保证的理论场景

方法 5: 桶排序/计数排序
  算法: 如果值域有限（如 0-1000），直接计数
  时间: O(N + Range)
  空间: O(Range)
  优点: 线性时间，常数极小
  缺点: 只适用于整数且范围已知
  适用: 年龄统计、分数排名等

═══════════════════════════════════════════════════════════════
选择决策树
═══════════════════════════════════════════════════════════════

  数据能全部放内存吗？
  ├── 否 → 最小堆 (O(K) 空间，流式处理)
  └── 是 → K/N 的比例？
       ├── K << N (如 K=100, N=1亿) → 最小堆
       ├── K ≈ N/2 (如找中位数) → 快速选择
       └── 需要有序结果？
            ├── 是 → 最小堆 + 堆排序输出
            └── 否 → 快速选择（最快）

分布式 TopK (数据分布在多台机器):
  1. 每台机器本地求 TopK → 得到 M 组 K 个元素
  2. 合并 M×K 个元素 → 再求全局 TopK
  3. 合并用 K 路归并（最小堆维护 M 个指针）
  时间: O(N/M × log K) + O(MK × log K)

11.2 最短路径问题——多种算法的场景选择

═══════════════════════════════════════════════════════════════
6 种最短路径算法的完整对比
═══════════════════════════════════════════════════════════════

  | 算法 | 时间复杂度 | 适用条件 | 核心思想 | 典型应用 |
  |------|-----------|---------|---------|---------|
  | BFS | O(V+E) | 无权图 | 逐层扩展 | 社交网络几度人脉 |
  | Dijkstra | O((V+E)logV) | 非负权 | 贪心+松弛 | 地图导航 |
  | Bellman-Ford | O(VE) | 有负权 | 全边松弛V-1轮 | 汇率套利检测 |
  | SPFA | O(kE) 平均 | 有负权 | BF的队列优化 | 竞赛常用 |
  | Floyd-Warshall | O(V³) | 全源 | DP | 小图全对最短路 |
  | A* | O(E) 实际 | 有启发式 | Dijkstra+启发 | 游戏寻路 |

  选择指南:
    无权图 → BFS (最简单最快)
    有权非负 → Dijkstra (标准答案)
    有负权边 → Bellman-Ford (可检测负环)
    全源最短路 → Floyd (V<500) 或 V次Dijkstra (V>500)
    有启发信息 → A* (实际扩展节点最少)
    稀疏图 → Dijkstra + 二叉堆
    稠密图 → Dijkstra + 数组 或 Floyd

11.3 字符串匹配——多种算法的场景选择

  | 算法 | 时间复杂度 | 预处理 | 适用场景 |
  |------|-----------|--------|---------|
  | 暴力匹配 | O(nm) | 无 | 短文本、简单场景 |
  | KMP | O(n+m) | O(m) | 单模式串精确匹配 |
  | Rabin-Karp | O(n+m) 期望 | O(m) | 多模式串、抄袭检测 |
  | Boyer-Moore | O(n/m) 最好 | O(m+σ) | 长模式串、文本编辑器 |
  | Aho-Corasick | O(n+m+z) | O(m) | 多模式串同时匹配 |
  | 后缀数组/树 | O(n) 构建 | O(n) | 重复子串、最长公共子串 |

  选择指南:
    单模式串 + 短文本 → 暴力 (实现简单，常数小)
    单模式串 + 长文本 → KMP 或 Boyer-Moore
    多模式串 → Aho-Corasick (如敏感词过滤)
    需要多次查询 → 后缀数组 (预处理后 O(m log n) 查询)
    模糊匹配 → 编辑距离 DP

12. 岛屿数量 (LeetCode 200) — 图遍历经典题

二维网格中 '1' 代表陆地，'0' 代表水域，计算岛屿数量（连通的 '1' 组成一个岛屿）。

// DFS 解法: 遇到 '1' 就递归沉没整个岛屿
func numIslands(grid [][]byte) int {
    if len(grid) == 0 { return 0 }
    rows, cols := len(grid), len(grid[0])
    count := 0

    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0' {
            return
        }
        grid[r][c] = '0'  // 沉没: 标记为已访问
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == '1' {
                count++
                dfs(r, c)  // 沉没整个岛屿
            }
        }
    }
    return count
}

// BFS 解法: 队列替代递归，避免栈溢出
func numIslandsBFS(grid [][]byte) int {
    if len(grid) == 0 { return 0 }
    rows, cols := len(grid), len(grid[0])
    count := 0
    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == '1' {
                count++
                grid[r][c] = '0'
                queue := [][2]int{{r, c}}
                for len(queue) > 0 {
                    cur := queue[0]
                    queue = queue[1:]
                    for _, d := range dirs {
                        nr, nc := cur[0]+d[0], cur[1]+d[1]
                        if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1' {
                            grid[nr][nc] = '0'
                            queue = append(queue, [2]int{nr, nc})
                        }
                    }
                }
            }
        }
    }
    return count
}

// 并查集解法: 适用于超大网格或动态统计
func numIslandsUnionFind(grid [][]byte) int {
    if len(grid) == 0 { return 0 }
    rows, cols := len(grid), len(grid[0])
    uf := NewUnionFind(rows * cols)
    count := 0

    dirs := [][2]int{{0,1}, {1,0}}  // 只向右和向下合并避免重复
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == '1' {
                count++
                idx := r*cols + c
                for _, d := range dirs {
                    nr, nc := r+d[0], c+d[1]
                    if nr < rows && nc < cols && grid[nr][nc] == '1' {
                        if uf.Union(idx, nr*cols+nc) {
                            count--  // 两个岛屿合并了
                        }
                    }
                }
            }
        }
    }
    return count
}

解法	时间	空间	适用场景
DFS	O(mn)	O(mn) → 递归栈	网格不大 (≤ 10^4)
BFS	O(mn)	O(min(m,n)) → 队列	防递归栈溢出
并查集	O(mn·α(n))	O(mn)	动态添加岛屿、需要统计变化

图算法：DFS、BFS、拓扑排序、最短路径 ​

1. 图的表示 ​

1.1 邻接矩阵 vs 邻接表 ​

2. 深度优先搜索（DFS） ​

2.1 递归实现 ​

2.2 三色标记法（检测环 + 拓扑排序） ​

2.3 应用场景 ​

2.4 图找环——多种解法的完整对比 ​

3. 广度优先搜索（BFS） ​

3.1 队列实现 ​

2.2 BFS vs DFS ​

2.3 应用 ​

4. 拓扑排序（Topological Sort） ​

4.1 定义 ​

4.2 Kahn 算法（BFS + 入度） ​

4.3 DFS 后序遍历法 ​

4.4 应用 ​

5. 最短路径 ​

5.1 Dijkstra — 单源最短路径 ​

5.2 Bellman-Ford — 处理负权边 ​

5.3 Floyd-Warshall — 全源最短路径 ​

5.4 A* — 带启发式的最短路径 ​

5.5 算法选择指南 ​

6. 最小生成树（MST） ​

6.1 Kruskal — 边排序 + 并查集 ​

6.2 Prim — 类似 Dijkstra ​

7. 各语言图的实现对比 ​

7.1 现实系统中的图 ​

8. 强连通分量（SCC）— 有向图的骨架 ​

8.1 Kosaraju 算法（两次 DFS） ​

8.2 Tarjan 算法（单次 DFS） ​

9. 最大流（Max Flow） ​

9.1 Ford-Fulkerson 方法 ​

9.2 各实现的复杂度 ​

9.3 最大流 = 最小割 ​

10. A* 搜索深入 ​

10.1 启发式函数的设计 ​

10.2 常见启发式函数 ​

10.3 Dijkstra 与 A* 的关系 ​

11. 经典问题的多种解法对比 ​

11.1 TopK 问题——从 N 个元素中找最大的 K 个 ​

11.2 最短路径问题——多种算法的场景选择 ​

11.3 字符串匹配——多种算法的场景选择 ​

12. 岛屿数量 (LeetCode 200) — 图遍历经典题 ​

参考 ​

💬 文章评论