数据结构与算法

数据结构与算法

数据结构与算法是计算机科学的核心基础。数据结构解决「数据怎么组织」，算法解决「问题怎么解决」，二者结合决定了程序的效率与正确性。

本教程内容

模块	内容
基础概念	复杂度分析、线性结构、哈希表
经典算法	分治、贪心、动态规划
排序	插入/希尔/归并/快排及其变种
堆	堆存储、上浮下沉、堆排序、索引堆
树	二分搜索树、遍历、删除
并查集	查找、合并、优化、路径压缩
图	表示、DFS/BFS、寻路、最短路径

为什么重要

• 面试必考：大厂技术面试的核心环节
• 写出高效代码：同样的功能，数据结构选对性能差百倍
• 理解底层：数据库索引（树）、缓存（哈希表）、网络（图）

数据结构与算法简介

认识数据结构与算法的基本概念，建立全局认知框架。

数据结构

数据结构是数据的组织方式。选择合适的数据结构决定操作效率：

结构	特点	典型场景
数组	连续内存、按下标 O(1) 访问	静态列表、矩阵
链表	动态插入删除快	LRU 缓存、撤销栈
栈	后进先出 (LIFO)	函数调用、括号匹配
队列	先进先出 (FIFO)	任务调度、BFS
哈希表	O(1) 增删查	缓存、去重、索引
树	层级关系、有序	文件系统、数据库索引
图	节点与边的关系	社交网络、地图导航

算法

算法是解决问题的步骤描述。好的算法特征：

• 正确性：所有输入都能给出正确结果
• 高效性：时间、空间复杂度可控
• 可读性：逻辑清晰易维护

一个简单示例

# 线性查找 vs 二分查找(有序数组)
def linear_search(arr, target):
    for i, v in enumerate(arr):
        if v == target:
            return i
    return -1

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

算法基础与分析方法

掌握时间复杂度与空间复杂度分析，学会评估算法优劣。

时间复杂度 (Big-O)

描述算法运行时间随输入规模 n 的增长趋势（忽略常数与低阶项）：

复杂度	含义	示例
O(1)	常数时间	数组按下标访问
O(log n)	对数时间	二分查找
O(n)	线性时间	遍历数组
O(n log n)	线性对数	归并/快排
O(n²)	平方时间	冒泡、嵌套循环
O(2ⁿ)	指数时间	暴力枚举子集

分析步骤

def sum_all(arr):
    total = 0              # O(1)
    for v in arr:          # n 次
        total += v         # 每次 O(1)
    return total
# 总复杂度: O(n)

def nested(arr):
    n = len(arr)
    for i in range(n):        # n 次
        for j in range(n):    # n 次
            print(i, j)       # O(1)
# 总复杂度: O(n²)

常见复杂度对比

n=1000 时大致操作次数:
O(log n)  ~10     ✅ 极快
O(n)      ~1000   ✅ 快
O(n log n)~10000  👍 可接受
O(n²)     ~10⁶    ⚠️ 慢
O(2ⁿ)     ~10³⁰⁰  ❌ 不可行

空间复杂度

def clone(arr):
    return arr[:]        # 额外 O(n) 空间

def inplace(arr):
    arr.reverse()        # O(1) 额外空间
    return arr

线性数据结构

线性数据结构：数组、链表、栈、队列——元素按线性顺序排列，是其他结构的基础。

数组 (Array)

arr = [3, 1, 4, 1, 5]
arr[0]        # O(1) 访问
arr.append(9) # 均摊 O(1) 尾部插入
# 中间插入/删除 O(n)(需移动元素)

链表 (Linked List)

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, val):   # O(1) 头部插入
        node = Node(val)
        node.next = self.head
        self.head = node

    def traverse(self):
        cur = self.head
        while cur:
            print(cur.val, end=" ")
            cur = cur.next

栈 (Stack, LIFO)

stack = []
stack.append(1)    # push
stack.append(2)
stack.pop()        # 弹出 2 (后进先出)

# 应用: 括号匹配
def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack

队列 (Queue, FIFO)

from collections import deque
q = deque()
q.append(1)      # enqueue
q.append(2)
q.popleft()      # 弹出 1 (先进先出)

# 应用: BFS 层级遍历

哈希表

哈希表（Hash Table）通过哈希函数把键映射到存储位置，实现 O(1) 平均复杂度的增删查。

原理

键 → 哈希函数 → 数组下标 → 存储值

例: hash("apple") = 3 → table[3] = "苹果"
例: hash("banana") = 7 → table[7] = "香蕉"

Python 内置

# dict / set 就是哈希表
d = {}
d["name"] = "张三"     # O(1) 插入
d.get("name")          # O(1) 查找
"name" in d            # O(1) 判断存在
del d["name"]          # O(1) 删除

# set: 去重
nums = [1, 2, 2, 3, 3, 3]
unique = set(nums)     # {1, 2, 3}

哈希冲突与解决

不同键哈希到同一位置称为冲突，常见解决方式：

方法	思路
链地址法	每个位置存链表，冲突元素挂后面
开放寻址	冲突时找下一个空位
再哈希	用另一个哈希函数重新计算

应用：两数之和

def two_sum(nums, target):
    """找到两个数下标使其和等于 target"""
    seen = {}                  # 值 → 下标
    for i, v in enumerate(nums):
        need = target - v
        if need in seen:       # O(1) 查找
            return [seen[need], i]
        seen[v] = i
    return []
# 时间复杂度 O(n), 空间 O(n)

树形结构

树（Tree）是层级化的非线性结构：一个根节点、若干子树，模拟「一对多」的关系。

基本概念

        根(1)
       /         (2)    (3)
    /  \        (4)  (5)    (6)

- 节点: 1~6
- 根: 1 (无父节点)
- 叶子: 4,5,6 (无子节点)
- 父/子: 1 是 2,3 的父; 2,3 是 1 的子
- 兄弟: 2,3
- 高度: 从根到最远叶子的边数
- 深度: 从根到该节点的边数

二叉树定义

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

常见树类型

类型	特点
二叉树	每个节点最多 2 个子节点
二分搜索树 (BST)	左小右大，查找 O(log n)
平衡树 (AVL/红黑树)	自动保持平衡
堆 (Heap)	父大于子（大顶堆）
B 树/B+树	多路搜索树，数据库索引

树的遍历框架

def preorder(root):       # 前序: 根左右
    if not root: return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

def inorder(root):        # 中序: 左根右
    if not root: return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

def postorder(root):      # 后序: 左右根
    if not root: return
    postorder(root.left)
    postorder(root.right)
    print(root.val)

图论结构

图（Graph）由节点（Vertex）和边（Edge）组成，表达「多对多」的关系，是网络类问题的通用模型。

基本概念

概念	说明
有向图	边有方向 (A→B ≠ B→A)
无向图	边无方向 (A—B)
带权图	边上有权重（距离/成本）
连通分量	互相可达的节点集合
度	节点相连的边数（有向分入度/出度）

表示方式

# 邻接矩阵 (n×n, 适合稠密图)
#      A B C
#  A  [0 1 1]
#  B  [1 0 0]
#  C  [1 0 0]
matrix = [[0,1,1],[1,0,0],[1,0,0]]

# 邻接表 (适合稀疏图, 常用)
graph = {
    "A": ["B", "C"],
    "B": ["A"],
    "C": ["A"],
}

图遍历

def dfs(graph, node, visited=None):
    """深度优先遍历"""
    if visited is None: visited = set()
    visited.add(node)
    print(node, end=" ")
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)

def bfs(graph, start):
    """广度优先遍历"""
    from collections import deque
    visited, q = {start}, deque([start])
    while q:
        node = q.popleft()
        print(node, end=" ")
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                q.append(nxt)

图的应用

• 社交网络：好友关系（无向图）
• 导航：最短路径（带权有向图）
• 任务调度：依赖关系（有向无环图）
• 网络拓扑：路由器连接

分治算法

分治（Divide and Conquer）：把大问题拆成小问题，递归解决后合并结果。归并排序、快速排序都是分治思想。

三步骤

1. 分解(Divide): 把问题分成规模更小的子问题
2. 解决(Conquer): 递归解决子问题(到最小规模直接解决)
3. 合并(Combine): 合并子问题的解得到原问题的解

示例：归并排序

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    # 分解
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # 合并
    return merge(left, right)

def merge(a, b):
    i = j = 0
    res = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    res.extend(a[i:])
    res.extend(b[j:])
    return res

# 复杂度: 时间 O(n log n), 空间 O(n)

示例：最大子数组和

def max_subarray(arr):
    """分治法求最大连续子数组和"""
    def helper(lo, hi):
        if lo == hi:          # 单个元素
            return arr[lo]
        mid = (lo + hi) // 2
        # 三种情况取最大: 全左 / 全右 / 跨中点
        left = helper(lo, mid)
        right = helper(mid+1, hi)

        # 跨中点的最大和
        lmax, s = float("-inf"), 0
        for i in range(mid, lo-1, -1):
            s += arr[i]; lmax = max(lmax, s)
        rmax, s = float("-inf"), 0
        for i in range(mid+1, hi+1):
            s += arr[i]; rmax = max(rmax, s)
        return max(left, right, lmax + rmax)

    return helper(0, len(arr)-1)

适用特征

• 问题可以递归分解为同构子问题
• 子问题相互独立（无重复子问题，否则用动态规划）
• 子问题的解可以高效合并

贪心算法

贪心算法（Greedy）：每一步都选择当前看起来最优的方案，希望通过局部最优得到全局最优。并非所有问题都适用，但适用时极其高效。

贪心策略步骤

1. 定义「贪心选择」: 每步选什么
2. 证明贪心选择是安全的(局部最优→全局最优)
3. 递归/迭代地做贪心选择, 缩减问题规模

经典示例：找零钱

def coin_change_greedy(amount, coins=(25, 10, 5, 1)):
    """美分制找零(面额满足贪心性质)"""
    result = {}
    for c in coins:
        result[c] = amount // c
        amount %= c
    return result

# 注意: 面额 {1,3,4} 时贪心对 amount=6 得 4+1+1 (3枚)
# 但最优是 3+3 (2枚) → 贪心不适用!

示例：活动选择（区间调度）

def max_activities(activities):
    """最多能参加的活动数(活动为(开始,结束))"""
    # 贪心: 每次选结束最早且与已选不冲突的活动
    activities.sort(key=lambda x: x[1])   # 按结束时间排序
    count, last_end = 0, 0
    for start, end in activities:
        if start >= last_end:
            count += 1
            last_end = end
    return count

print(max_activities([(1,3),(2,5),(3,6),(5,7),(6,8)]))  # 3

示例：跳跃游戏

def can_jump(nums):
    """能否从下标0跳到末尾(每步最多跳 nums[i])"""
    max_reach = 0
    for i, step in enumerate(nums):
        if i > max_reach:      # 到不了当前位置
            return False
        max_reach = max(max_reach, i + step)
    return True

print(can_jump([2,3,1,1,4]))  # True
print(can_jump([3,2,1,0,4]))  # False

何时用贪心

适用	特征
✅ 适用	活动选择、区间覆盖、最小生成树、哈夫曼编码、部分背包
❌ 不适用	0-1 背包、硬币问题(非规范面额)、旅行商

动态规划

动态规划（Dynamic Programming, DP）：把问题拆成重叠子问题，存储子问题的解避免重复计算，常用于最优化问题。

核心要素

1. 状态定义: dp[i] 表示什么
2. 状态转移: dp[i] 由哪些子状态推出(递推式)
3. 初始化:   边界条件
4. 遍历顺序: 确保计算 dp[i] 时子状态已就绪

示例：斐波那契（记忆化 vs 迭代）

# 朴素递归: O(2^n) 大量重复计算
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)

# 迭代 DP: O(n)
def fib_dp(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib_dp(50))   # 12586269025 (瞬间)

示例：爬楼梯

def climb_stairs(n):
    """每次爬1或2阶, 到第n阶有多少种方法"""
    if n <= 2: return n
    a, b = 1, 2            # dp[1], dp[2]
    for _ in range(3, n+1):
        a, b = b, a + b    # 滚动数组: dp[i]=dp[i-1]+dp[i-2]
    return b

示例：0-1 背包

def knapsack(weights, values, capacity):
    """0-1背包: 选物品使总价值最大, 总重量≤capacity"""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i-1], values[i-1]
        for c in range(capacity + 1):
            if w > c:
                dp[i][c] = dp[i-1][c]      # 不选
            else:
                dp[i][c] = max(dp[i-1][c],
                               dp[i-1][c-w] + v)   # 选
    return dp[n][capacity]

print(knapsack([2,3,4,5], [3,4,5,6], 8))  # 10

DP vs 分治 vs 贪心

算法	子问题关系	选择策略
分治	独立	递归拆分合并
贪心	独立(每步最优)	局部最优选择
DP	重叠	存储子解避免重复

高级树结构

高级树结构：AVL 树、红黑树、B 树/B+树、Trie——在基础树上加入平衡或特殊约束以优化特定操作。

AVL 树（严格平衡）

# 每个节点记录平衡因子(左右子树高度差 ∈ {-1,0,1})
# 插入/删除后, 若 |平衡因子| > 1 则旋转:
#   LL → 右旋, RR → 左旋
#   LR → 先左旋再右旋, RL → 先右旋再左旋
# 查找 O(log n), 插入/删除 O(log n) 但旋转次数多

红黑树（近似平衡）

规则:
1. 节点非红即黑
2. 根是黑
3. 红节点的子节点都是黑(不连续红)
4. 每个节点到叶子的路径黑节点数相同

特点: 插入/删除最多 O(1) 旋转,
     平衡略松但统计性能更优
应用: Java TreeMap/HashMap, Linux 进程调度, Python 无(用 dict)

B 树 / B+树（多路）

B树: 一个节点存多个键, 多子节点(不是二叉)
     → 减少磁盘 IO(一次读一页)
B+树: 数据只在叶子, 内部节点只存索引
     → 叶子链表连接, 适合范围查询
应用: MySQL InnoDB 索引, 文件系统

Trie（前缀树）

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True

# 应用: 输入法联想、拼写检查、IP 路由

高级图算法

高级图算法：最小生成树、最短路径、拓扑排序——解决工程中的网络优化与依赖问题。

最小生成树 (MST)

# Prim 算法: 从一点出发, 每次加入最近的未选点
import heapq

def prim(graph, start=0):
    """graph: 邻接表 [(邻居, 权重)], 返回总权重"""
    n = len(graph)
    visited = [False] * n
    pq = [(0, start)]        # (权重, 节点)
    total = 0
    while pq:
        w, u = heapq.heappop(pq)
        if visited[u]: continue
        visited[u] = True
        total += w
        for v, w2 in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (w2, v))
    return total

# 应用: 通信网络布线、电路设计

最短路径：Dijkstra

def dijkstra(graph, start):
    """单源最短路径(边权非负)"""
    n = len(graph)
    dist = [float("inf")] * n
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# 应用: 地图导航、网络路由
# 边权含负 → 用 Bellman-Ford; 多源 → Floyd

拓扑排序（有向无环图）

def topo_sort(graph):
    """课程表问题: 依赖顺序。返回拓扑序或空(有环)"""
    from collections import deque
    n = len(graph)
    indeg = [0] * n
    for u in range(n):
        for v in graph[u]:
            indeg[v] += 1

    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []   # 空=有环

# 应用: 编译依赖、任务调度、课程先修

其他高级算法

算法	问题
Floyd-Warshall	所有点对最短路径
Bellman-Ford	含负权边的最短路径
Kruskal	MST(并查集实现)
Tarjan	强连通分量

排序算法

排序算法总览：对比各算法的时间/空间复杂度与稳定性，为后续逐个深入学习建立框架。

排序算法对比

算法	最好	平均	最坏	空间	稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	✅
希尔排序	O(n^1.3)	~O(n^1.5)	O(n²)	O(1)	❌
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	✅
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	❌
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	❌

稳定性含义

稳定: 相等元素排序后保持原相对顺序
例如按价格排序后, 同价商品仍按原顺序排列
- 插入/归并: 稳定 (相等时不交换)
- 快排/堆排: 不稳定 (可能交换相等元素)

如何选择

场景	推荐
基本有序的小数组	插入排序（近乎 O(n)）
大数据量、需稳定	归并排序
大数据量、内存敏感	堆排序（O(1) 空间）
通用默认	快速排序（工程实现常用）

Python 内置

arr.sort()                    # 原地排序(稳定, Timsort)
sorted(arr)                   # 返回新列表
arr.sort(reverse=True)        # 降序
arr.sort(key=lambda x: x[1])  # 按第二个元素排序
# Python 默认的 Timsort = 归并+插入的混合, O(n log n)

插入排序

插入排序（Insertion Sort）：像打扑克牌一样，把每个元素插入到前面已排序序列的正确位置。

算法思想

初始: [5, 2, 4, 6, 1]
 第1轮: 把2插到5前 → [2, 5, 4, 6, 1]
 第2轮: 把4插到5前 → [2, 4, 5, 6, 1]
 第3轮: 6已就位 → [2, 4, 5, 6, 1]
 第4轮: 把1插到最前 → [1, 2, 4, 5, 6]

实现

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]           # 待插入元素
        j = i - 1
        while j >= 0 and arr[j] > key:   # 向前找位置
            arr[j + 1] = arr[j]           # 后移
            j -= 1
        arr[j + 1] = key       # 插入
    return arr

print(insertion_sort([5, 2, 4, 6, 1]))  # [1,2,4,5,6]

复杂度分析

情况	复杂度	说明
最好（已有序）	O(n)	内层 while 不执行
平均	O(n²)	每个元素平均后移一半
最坏（逆序）	O(n²)	每个元素都移到最前

优化：减少交换

def insertion_sort_opt(arr):
    # 用「整体后移」代替逐次交换, 减少赋值次数
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

特点

• 稳定：相等元素不交换
• 原地：O(1) 额外空间
• 自适应：数据越有序越快
• 适合小数组或近乎有序的数组（如 Timsort 用它的优化版）

希尔排序

希尔排序（Shell Sort）：插入排序的改进——先按大间隔分组插入，逐步缩小间隔，最后间隔为 1 时就是普通插入排序。

算法思想

间隔序列(常用): n/2, n/4, ..., 1

例: [9, 8, 7, 6, 5, 4, 3, 2, 1], n=9
间隔4: 分组 (9,5,1) (8,4) (7,3) (6,2) 组内插入排序
间隔2: 分组 (9,7,5,3,1) (8,6,4,2) 组内插入排序
间隔1: 全数组插入排序(此时已接近有序, 很快)

「先粗排后细排」→ 减少元素移动总距离

实现

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        # 对每个间隔分组做插入排序
        for i in range(gap, n):
            key = arr[i]
            j = i
            while j >= gap and arr[j - gap] > key:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = key
        gap //= 2
    return arr

print(shell_sort([9, 8, 7, 6, 5, 4, 3, 2, 1]))

间隔序列选择

间隔序列	复杂度
n/2, n/4, ..., 1	O(n²)
2^k - 1 (Hibbard)	O(n^1.5)
3^k - 1 / 2 (Sedgewick)	O(n^4/3)~O(n^7/6)

特点

• 不稳定（间隔分组打乱相对顺序）
• 原地排序，O(1) 空间
• 比简单插入排序快，但弱于 O(n log n) 算法
• 适合中等规模数据

归并排序

归并排序（Merge Sort）：分治思想的经典应用——把数组对半拆分到最小，再两两有序合并。

算法流程

[5,2,4,6,1,3]
    /        [5,2,4]    [6,1,3]
  /   \      /   [5] [2,4]  [6] [1,3]
     / \        /    [2] [4]    [1] [3]
     \ /        \ /
   [2,4]      [1,3]
    \           /
 [2,4,5]    [1,3,6]
       \      /
   [1,2,3,4,5,6]

实现

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # 递归左半
    right = merge_sort(arr[mid:])   # 递归右半
    return merge(left, right)       # 合并

def merge(a, b):
    i = j = 0
    res = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:        # 等号保证稳定
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    res.extend(a[i:])
    res.extend(b[j:])
    return res

原地归并（节省空间）

def merge_inplace(arr, lo, mid, hi):
    """把 arr[lo:mid] 与 arr[mid:hi] 合并"""
    left = arr[lo:mid]
    right = arr[mid:hi]
    i = j = 0
    k = lo
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]; i += 1
        else:
            arr[k] = right[j]; j += 1
        k += 1
    while i < len(left):
        arr[k] = left[i]; i += 1; k += 1
    while j < len(right):
        arr[k] = right[j]; j += 1; k += 1

复杂度与特点

• 时间：O(n log n)（稳定，最好最坏都是）
• 空间：O(n)（需辅助数组）
• 稳定：合并时相等元素取左边
• 适合链表排序（无需随机访问）

归并思想的应用

# 逆序对计数
def count_inversions(arr):
    """利用归并过程统计逆序对数量"""
    if len(arr) <= 1: return arr, 0
    mid = len(arr) // 2
    left, inv1 = count_inversions(arr[:mid])
    right, inv2 = count_inversions(arr[mid:])
    merged, inv3 = [], 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j])
            inv3 += len(left) - i     # 关键
            j += 1
    merged += left[i:] + right[j:]
    return merged, inv1 + inv2 + inv3

随机化快速排序

快速排序（Quick Sort）：选一个基准（pivot），把小于它的放左边、大于的放右边，然后递归两边。**随机化**选取基准避免最坏情况。

基本思想

选基准 pivot(如最后一个元素)
分区: [< pivot] [pivot] [> pivot]
递归排序左右两区

例: [3,1,4,1,5,9,2], pivot=2
分区后: [1,1] [2] [3,4,5,9]
递归: [1,1] → [1,1]; [3,4,5,9] → 继续

随机化快排实现

import random

def quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo >= hi: return arr

    # 随机选基准, 与最后一个交换 → 期望 O(n log n)
    pi = random.randint(lo, hi)
    arr[pi], arr[hi] = arr[hi], arr[pi]

    pivot = arr[hi]
    i = lo                      # 已分区的小于基准部分的边界
    for j in range(lo, hi):
        if arr[j] < pivot:      # 严格小于 → 稳定?不, 快排本就不稳定
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]   # 基准归位

    quick_sort(arr, lo, i - 1)  # 递归左
    quick_sort(arr, i + 1, hi)  # 递归右
    return arr

print(quick_sort([3, 1, 4, 1, 5, 9, 2]))

为什么随机化

固定选第一个/最后一个为基准时:
- 已有序数组 → 每次分区极度不均 → O(n²) ❌
随机选基准 → 期望平均 O(n log n) ✅
几乎不可能每次都选中极值

复杂度

情况	复杂度
平均（随机化）	O(n log n)
最好（每次正好对半）	O(n log n)
最坏（每次都选中极值）	O(n²)（概率极低）
空间	O(log n)（递归栈）

应用：快速选择（第 k 大）

def quick_select(arr, k):
    """找第 k 小元素 (k 从 0 开始), 平均 O(n)"""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        pi = random.randint(lo, hi)
        arr[pi], arr[hi] = arr[hi], arr[pi]
        pivot = arr[hi]
        i = lo
        for j in range(lo, hi):
            if arr[j] < pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[hi] = arr[hi], arr[i]
        if i == k: return arr[i]
        elif i < k: lo = i + 1
        else: hi = i - 1

print(quick_select([3,1,4,1,5,9,2], 2))   # 第3小=2

双路快速排序

双路快速排序（Two-Way Quick Sort）：针对大量重复元素优化的分区方式——左右两个指针同时扫描，把相等的元素均匀分到两边。

问题：大量重复元素

普通分区 [pivot]:
 数组 [1,1,1,1,1,2] 选 pivot=1 时:
 所有 1 都进"小于或等于"区 → 分区严重失衡 → O(n²)

双路分区: 把等于 pivot 的元素分到两边 → 平衡

双路分区实现

import random

def quick_sort_2way(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo >= hi: return arr

    pi = random.randint(lo, hi)
    arr[pi], arr[lo] = arr[lo], arr[pi]   # pivot 放最左
    pivot = arr[lo]

    i, j = lo + 1, hi        # 左右指针
    while True:
        # 左指针右移, 找 >= pivot 的元素
        while i <= hi and arr[i] < pivot:
            i += 1
        # 右指针左移, 找 <= pivot 的元素
        while j >= lo + 1 and arr[j] > pivot:
            j -= 1
        if i > j: break       # 交错则停止
        arr[i], arr[j] = arr[j], arr[i]   # 交换
        i += 1; j -= 1

    arr[lo], arr[j] = arr[j], arr[lo]     # pivot 归位
    quick_sort_2way(arr, lo, j - 1)
    quick_sort_2way(arr, j + 1, hi)
    return arr

# 关键: 条件用 < 和 > (等于的元素两边都收) → 平衡

对比

分区方式	重复元素	性能
单路	全部堆到一边	退化 O(n²)
双路	均匀分两边	O(n log n)
三路(下章)	单独成区	O(n)(全相同时)

正确性要点

1. pivot 先放最左, 最后与 arr[j] 交换(j 是 <=pivot 区边界)
2. 双指针: 左找大、右找小, 相遇交换
3. 循环条件是 while True + break(i > j), 
   保证 j 最终指向 <=pivot 的位置
4. 等于 pivot 的元素被<左右两个方向>吸收 → 平衡

三路排序算法

三路快速排序（Three-Way Quick Sort）：把数组分成 小于 / 等于 / 大于 三个区，等于 pivot 的元素一次性归位，不再递归。

分区结果

[ < pivot ] [ == pivot ] [ > pivot ]
     ↑递归       无需递归       ↑递归

对全相同数组: 一次分区就完成, O(n) ✅

实现

import random

def quick_sort_3way(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo >= hi: return arr

    pi = random.randint(lo, hi)
    arr[pi], arr[lo] = arr[lo], arr[pi]
    pivot = arr[lo]

    lt = lo        # arr[lo+1..lt] < pivot
    i = lo + 1     # 扫描指针
    gt = hi        # arr[gt..hi] > pivot

    while i <= gt:
        if arr[i] < pivot:
            arr[lt+1], arr[i] = arr[i], arr[lt+1]
            lt += 1; i += 1
        elif arr[i] > pivot:
            arr[gt], arr[i] = arr[i], arr[gt]
            gt -= 1          # i 不动(换来的元素未检查)
        else:
            i += 1

    arr[lo], arr[lt] = arr[lt], arr[lo]   # pivot 区归位

    quick_sort_3way(arr, lo, lt - 1)      # 递归 <区
    quick_sort_3way(arr, gt + 1, hi)      # 递归 >区
    return arr

print(quick_sort_3way([3,1,4,1,5,9,2,1,3,1]))

三指针的含义

指针	维护区间
lt	[lo..lt] 全部 < pivot
i	[lt+1..i-1] 全部 == pivot（扫描区）
gt	[gt..hi] 全部 > pivot

复杂度

情况	复杂度
全相同	O(n)（一次分区完成）
平均	O(n log n)
空间	O(log n) 递归栈

应用：荷兰国旗问题

def dutch_flag(arr):
    """只含 0/1/2, 排序(本质是三路分区思想)"""
    lo, i, hi = 0, 0, len(arr) - 1
    while i <= hi:
        if arr[i] == 0:
            arr[lo], arr[i] = arr[i], arr[lo]
            lo += 1; i += 1
        elif arr[i] == 2:
            arr[hi], arr[i] = arr[i], arr[hi]
            hi -= 1
        else:
            i += 1
    return arr

print(dutch_flag([2,0,1,2,1,0,0,2]))  # [0,0,0,1,1,2,2,2]

排序算法衍生问题

排序不只是「排好序」——利用排序后的性质可解决大量衍生问题：第 k 大、找重复、区间合并、计数排序思想等。

1. 第 k 大 / 第 k 小

def kth_largest(nums, k):
    """基于快排分区, 平均 O(n)"""
    return quick_select(nums, len(nums) - k)  # 复用上章

# 或直接排序 O(n log n) (数据量小也够用)
def kth_largest_simple(nums, k):
    return sorted(nums, reverse=True)[k-1]

2. 找重复元素

def find_duplicates(nums):
    """排序后相邻相等即重复"""
    nums.sort()
    res = []
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1] and (not res or res[-1] != nums[i]):
            res.append(nums[i])
    return res

# 哈希法 O(n) 空间 O(n)
def find_duplicates_hash(nums):
    seen, res = set(), set()
    for v in nums:
        if v in seen: res.add(v)
        seen.add(v)
    return list(res)

3. 合并区间

def merge_intervals(intervals):
    """合并重叠区间"""
    if not intervals: return []
    intervals.sort(key=lambda x: x[0])   # 按起点排序
    merged = [intervals[0]]
    for s, e in intervals[1:]:
        last_s, last_e = merged[-1]
        if s <= last_e:                  # 重叠
            merged[-1][1] = max(last_e, e)
        else:
            merged.append([s, e])
    return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]

4. 计数排序（非比较排序）

def counting_sort(arr, max_val):
    """适合取值范围的整数, O(n+k)"""
    count = [0] * (max_val + 1)
    for v in arr:
        count[v] += 1
    res = []
    for v, c in enumerate(count):
        res.extend([v] * c)
    return res

print(counting_sort([3,1,2,3,1,0,2], 3))  # [0,1,1,2,2,3,3]

5. 找多数元素

def majority_element(nums):
    """出现次数 > n/2 的元素(排序后中间位置必是它)"""
    nums.sort()
    return nums[len(nums) // 2]
# 更优: Boyer-Moore 投票 O(n) O(1), 不用排序

堆的基本存储

堆（Heap）是一棵完全二叉树，用数组存储，满足堆序性质：大顶堆父 ≥ 子，小顶堆父 ≤ 子。堆是实现优先队列、堆排序的基础。

数组存储完全二叉树

        62
       /       41    30
    / \   /   28  16 22  13
  /  19  17

数组: [62, 41, 30, 28, 16, 22, 13, 19, 17]
下标:   0   1   2   3   4   5   6   7   8

规律(下标 i):
- 左孩子: 2*i + 1
- 右孩子: 2*i + 2
- 父节点: (i-1) // 2
- 最后一个非叶节点: n//2 - 1

堆的实现骨架

class MaxHeap:
    def __init__(self):
        self.data = []          # 数组存储

    def __len__(self):
        return len(self.data)

    def peek(self):
        """看堆顶(最大值), O(1)"""
        return self.data[0] if self.data else None

    @staticmethod
    def _parent(i): return (i - 1) // 2
    @staticmethod
    def _left(i):   return 2 * i + 1
    @staticmethod
    def _right(i):  return 2 * i + 2

性质

• 堆不是完全有序的树，只保证「父 ≥ 子」
• 堆顶是最大/最小元素
• 插入、删除堆顶都是 O(log n)（树高）
• 建堆（heapify）O(n)

Python 内置堆

import heapq

# 小顶堆
heap = []
heapq.heappush(heap, 3)   # 插入 O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappop(heap)       # 弹出最小 1

# 大顶堆: 存负数
heapq.heappush(heap, -x)  # 取时再取负
# heapq.nlargest(k, arr) / nsmallest(k, arr)

堆的 shift up

shift up（上浮）：向堆中插入新元素时，把它放到末尾后不断与父节点比较，上浮到正确位置，保持堆序。

插入过程

大顶堆插入 50:
[62, 41, 30, 28, 16, 22, 13, 19, 17] + 50(末尾)
[62, 41, 30, 28, 16, 22, 13, 19, 17, 50]
                 ↑ 50 与父 16 比, 50>16 → 交换
[62, 41, 30, 28, 50, 22, 13, 19, 17, 16]
                 ↑ 50 与父 41 比, 50>41 → 交换
[62, 50, 30, 28, 41, 22, 13, 19, 17, 16]
                 ↑ 50 与父 62 比, 50<62 → 停止 ✅

实现

class MaxHeap:
    # ... 省略父/子下标与 data

    def insert(self, value):
        """插入元素并上浮, O(log n)"""
        self.data.append(value)
        self._shift_up(len(self.data) - 1)

    def _shift_up(self, i):
        """元素从位置 i 上浮到合适位置"""
        while i > 0:
            parent = (i - 1) // 2
            if self.data[i] <= self.data[parent]:
                break                    # 已满足堆序
            self.data[i], self.data[parent] =                 self.data[parent], self.data[i]
            i = parent                   # 继续向上

测试

h = MaxHeap()
for v in [62, 41, 30, 28, 16, 22, 13]:
    h.insert(v)
h.insert(50)                # 插入大值
print(h.peek())             # 62 (堆顶仍是最大)
print(h.data)               # [62, 50, 30, 28, 41, 22, 13, 16, 17]?

复杂度

• 插入：O(log n)（树高 = log n 次比较交换）
• 空间：O(1) 额外（原地在数组末尾操作）

堆的 shift down

shift down（下沉）：从堆中删除堆顶时，用最后一个元素填补堆顶，然后不断下沉到正确位置。

删除堆顶过程

[62, 41, 30, 28, 16, 22, 13, 19, 17]
 ① 保存堆顶 62(返回)
 ② 最后一个元素 17 移到堆顶
 [17, 41, 30, 28, 16, 22, 13, 19]
 ③ 下沉: 17 与较大子 41 比, 41>17 → 交换
 [41, 17, 30, 28, 16, 22, 13, 19]
 ④ 17 与较大子 28 比, 28>17 → 交换
 [41, 28, 30, 17, 16, 22, 13, 19]
 ⑤ 17 与较大子 22 比, 22>17 → 交换
 [41, 28, 30, 22, 16, 17, 13, 19]
 ⑥ 17 与较大子 19 比, 19>17 → 交换
 [41, 28, 30, 22, 16, 19, 13, 17] ✅

实现

class MaxHeap:
    def pop(self):
        """弹出并返回堆顶(最大值), O(log n)"""
        if not self.data:
            return None
        top = self.data[0]
        last = self.data.pop()          # 取最后一个
        if self.data:
            self.data[0] = last         # 放到堆顶
            self._shift_down(0)         # 下沉
        return top

    def _shift_down(self, i):
        """元素从位置 i 下沉到合适位置"""
        n = len(self.data)
        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            largest = i
            # 找三个节点中最大者
            if left < n and self.data[left] > self.data[largest]:
                largest = left
            if right < n and self.data[right] > self.data[largest]:
                largest = right
            if largest == i:
                break                   # 已就位
            self.data[i], self.data[largest] =                 self.data[largest], self.data[i]
            i = largest                 # 继续下沉

测试

h = MaxHeap()
for v in [62, 41, 30, 28, 16, 22, 13, 19, 17]:
    h.insert(v)
print(h.pop())   # 62
print(h.pop())   # 41
print(h.peek())  # 30

关键点

• 下沉时与较大的孩子交换（大顶堆）
• 边界：left < n 判断孩子是否存在
• while True + break 模式清晰

基础堆排序

堆排序（Heap Sort）：利用堆「堆顶是最值」的性质——反复弹出堆顶，得到有序序列。**基础版**需要额外 O(n) 空间。

算法流程

① 把所有元素插入堆
② 依次弹出堆顶 → 得到升序(小顶堆)或降序(大顶堆)
例(小顶堆):
heap = 建堆([5,3,8,1])
pop → 1, pop → 3, pop → 5, pop → 8
结果: [1,3,5,8] ✅

基础实现（O(n) 空间）

import heapq

def heap_sort(arr):
    """基础版: 借助辅助堆"""
    heap = []
    for v in arr:
        heapq.heappush(heap, v)    # 建堆 O(n log n)
    return [heapq.heappop(heap) for _ in range(len(arr))]

print(heap_sort([5, 3, 8, 1, 9]))  # [1,3,5,8,9]

空间优化方向

问题: 用了额外数组存放结果 → O(n) 空间
下章: 原地堆排序 → O(1) 额外空间
步骤:
① 把原数组 heapify 成大顶堆(原地)
② 反复: 堆顶(最大)与末尾交换, 堆大小-1, 下沉
③ 结束: 数组升序 ✅

复杂度

指标	值
时间	O(n log n)（建堆 + n 次 O(log n) 弹出）
空间（基础版）	O(n)
稳定	❌ 不稳定

Python 一行版

import heapq
heapq.heapify(arr)      # 原地建堆(小顶)
sorted_arr = [heapq.heappop(arr) for _ in range(len(arr))]

优化堆排序

原地堆排序：把「弹出堆顶」改为「堆顶与末尾交换」，堆的大小减 1，仅 O(1) 额外空间。

核心思想

大顶堆 [62, 41, 30, 28, 16, 22, 13, 19, 17]
① 堆顶与末尾交换: [17, 41, 30, ..., 62]
   62 已就位(末尾=最大)
② 堆大小-1, 对前 8 个元素下沉
③ 重复 ① ② → 数组尾部逐渐累积最大元素 → 升序

每次交换+下沉 O(log n), 共 n 次 → O(n log n)

实现

def heapify(arr, n, i):
    """以 i 为根的下沉(使其成为合法子堆)"""
    largest = i
    left, right = 2*i+1, 2*i+2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)   # 递归下沉

def heap_sort_inplace(arr):
    n = len(arr)
    # ① 建堆: 从最后一个非叶节点开始下沉
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # ② 反复把堆顶与末尾交换
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]   # 最大放末尾
        heapify(arr, i, 0)                # 缩小堆重新下沉
    return arr

print(heap_sort_inplace([5,3,8,1,9,2]))  # [1,2,3,5,8,9]

建堆为什么是 O(n)

从最后一个非叶节点(n//2-1)倒着下沉:
- 底层节点多但下沉距离短
- 高层节点下沉距离长但数量少
总工作量 ≈ n (不是 n log n)

复杂度

指标	值
建堆	O(n)
排序	n × O(log n) = O(n log n)
空间	O(1)（原地，仅递归栈）
稳定	❌

索引堆及其优化

索引堆（Index Heap）：堆元素不是数据本身，而是数据的下标。可任意修改、删除元素，且不移动数据本体——适合动态优先队列（如 Dijkstra 优化）。

为什么需要索引堆

普通堆的问题:
- 修改某个元素的值 → 需先找到它(可能要遍历 O(n))
- 元素移动频繁 → 数据本身被搬来搬去(大对象代价高)

索引堆: 堆数组存"下标", 数据本体不动
→ 想改 data[i] → 直接改, 再按索引堆的 index 调整

结构

data:  [62, 41, 30, 28, 16, 22, 13]
index: [0,  1,  2,  3,  4,  5,  6]   # 堆里存的是这些下标
# 堆序比较的是 data[index[i]]

实现（索引堆）

class IndexMaxHeap:
    def __init__(self, data):
        self.data = data            # 原始数据(下标访问)
        self.index = list(range(len(data)))  # 堆数组存下标
        # 建堆(按 data[index[i]] 比较)
        for i in range(len(self.index)//2 - 1, -1, -1):
            self._shift_down(i)

    def _shift_up(self, i):
        while i > 0:
            p = (i - 1) // 2
            if self.data[self.index[i]] <= self.data[self.index[p]]:
                break
            self.index[i], self.index[p] = self.index[p], self.index[i]
            i = p

    def _shift_down(self, i):
        n = len(self.index)
        while True:
            l, r, largest = 2*i+1, 2*i+2, i
            if l < n and self.data[self.index[l]] > self.data[self.index[largest]]:
                largest = l
            if r < n and self.data[self.index[r]] > self.data[self.index[largest]]:
                largest = r
            if largest == i: break
            self.index[i], self.index[largest] = self.index[largest], self.index[i]
            i = largest

    def pop_max(self):
        """弹出最大值对应的原始下标"""
        if not self.index: return None
        top = self.index[0]
        last = self.index.pop()
        if self.index:
            self.index[0] = last
            self._shift_down(0)
        return top

应用：Dijkstra 的堆优化

# 经典做法: heapq 存 (dist, node) 即可,
# 索引堆的价值在大数据/频繁改值的自定义场景。
# 概念理解为主: 「堆里存下标, 比较用数据值」

二分搜索树

二分搜索树（Binary Search Tree, BST）：二叉树 + 有序性质——左子树所有值 < 根 < 右子树所有值。支持 O(log n) 的查找/插入/删除。

BST 性质

        41
       /       22    65
    /  \   /   15   28 53  70

规则: 每个节点, 左子树所有值 < 节点值 < 右子树所有值
中序遍历 → 有序序列: 15,22,28,41,53,65,70

节点与树

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

查找

    def contains(self, val):
        """是否包含 val, O(log n)"""
        cur = self.root
        while cur:
            if val == cur.val: return True
            elif val < cur.val: cur = cur.left
            else: cur = cur.right
        return False

插入

    def insert(self, val):
        self.root = self._insert(self.root, val)
        self.size += 1

    def _insert(self, node, val):
        if node is None:
            return Node(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        # 相等: 忽略(或计数)
        return node

最小/最大

    def minimum(self):
        """最左节点"""
        cur = self.root
        while cur and cur.left:
            cur = cur.left
        return cur.val if cur else None

    def maximum(self):
        cur = self.root
        while cur and cur.right:
            cur = cur.right
        return cur.val if cur else None

复杂度与退化

情况	查找/插入
平衡 BST	O(log n)
退化为链表（有序插入）	O(n) ❌

二分搜索树节点的插入

深入 BST 插入：递归与非递归实现，理解「返回值接收新子树」的递归技巧。

递归插入

class Node:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

def insert(node, val):
    """返回插入后的(子)树根。若 val 已存在则不插入。"""
    if node is None:
        return Node(val)
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    # val == node.val: 已存在, 不操作
    return node

递归中的关键点

insert(node.left, val) 的返回值要赋给 node.left
→ 因为新节点是在子树里创建的, 必须接回父节点
→ 「递归函数返回子树根」是树类递归的通用模式

非递归插入

def insert_iter(root, val):
    new = Node(val)
    if root is None:
        return new
    cur = root
    while True:
        if val < cur.val:
            if cur.left is None:
                cur.left = new
                break
            cur = cur.left
        elif val > cur.val:
            if cur.right is None:
                cur.right = new
                break
            cur = cur.right
        else:
            break          # 已存在
    return root

构建示例树

root = None
for v in [41, 22, 65, 15, 28, 53, 70]:
    root = insert(root, v)

# 结构:
#        41
#       /  #     22    65
#    / \   / #  15  28 53  70

测试

def inorder(node, res):
    if node:
        inorder(node.left, res)
        res.append(node.val)
        inorder(node.right, res)

res = []
inorder(root, res)
print(res)   # [15, 22, 28, 41, 53, 65, 70] 有序 ✅

二分搜索树节点的查找

BST 查找：按值比较，一路向下，每次排除一半——与二分查找异曲同工。

递归查找

def find(node, val):
    """返回包含 val 的节点, 没有返回 None"""
    if node is None or node.val == val:
        return node
    if val < node.val:
        return find(node.left, val)
    return find(node.right, val)

node = find(root, 28)
print(node.val if node else None)   # 28

非递归查找

def find_iter(node, val):
    while node and node.val != val:
        if val < node.val:
            node = node.left
        else:
            node = node.right
    return node

查找 floor / ceil

def floor(node, val):
    """不大于 val 的最大节点值"""
    if node is None: return None
    if node.val == val: return node.val
    if val < node.val:
        return floor(node.left, val)
    # val > node.val: 答案在右子树或就是 node
    res = floor(node.right, val)
    return res if res is not None else node.val

查找前驱 / 后继

# 前驱: 中序遍历中 val 的前一个
# 后继: 中序遍历中 val 的后一个
# 技巧: 中序遍历一遍, 找相邻元素

def predecessor(node, val):
    """小于 val 的最大值(简化: 基于 floor+严格小于)"""
    res = floor(node, val)
    return res if res != val else _floor_less(node, val)

# 完整实现通常配合删除/旋转使用, 理解概念为主

复杂度

树形态	查找
平衡	O(log n)
退化为链表	O(n)

二分搜索树深度优先遍历

深度优先遍历（DFS）：前序、中序、后序三种顺序，核心都是「递归访问根与子树」，区别在于根何时被访问。

三种顺序

        41
       /       22    65
    / \   /   15  28 53  70

前序(根左右):   41, 22, 15, 28, 65, 53, 70
中序(左根右):   15, 22, 28, 41, 53, 65, 70  ← 有序!
后序(左右根):   15, 28, 22, 53, 70, 65, 41

递归实现

def preorder(node):
    if node is None: return
    print(node.val, end=" ")     # 根
    preorder(node.left)          # 左
    preorder(node.right)         # 右

def inorder(node):
    if node is None: return
    inorder(node.left)           # 左
    print(node.val, end=" ")     # 根
    inorder(node.right)          # 右

def postorder(node):
    if node is None: return
    postorder(node.left)         # 左
    postorder(node.right)        # 右
    print(node.val, end=" ")     # 根

非递归前序（栈）

def preorder_iter(root):
    if root is None: return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.val, end=" ")
        # 先压右再压左 → 左先出
        if node.right: stack.append(node.right)
        if node.left:  stack.append(node.left)

非递归中序（栈）

def inorder_iter(root):
    stack, cur = [], root
    while stack or cur:
        while cur:                    # 一路向左
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()             # 弹出(根)
        print(cur.val, end=" ")
        cur = cur.right               # 转向右子树

应用

顺序	典型用途
前序	复制树、序列化、打印结构
中序	有序输出（BST）、BST 验证
后序	释放树、计算子树大小（先子后父）

二分搜索树层序遍历

层序遍历（BFS，广度优先）：按层从上到下、从左到右访问节点，用队列实现。

遍历顺序

        41
       /       22    65
    / \   /   15  28 53  70

层序: 41, 22, 65, 15, 28, 53, 70

队列实现

from collections import deque

def level_order(root):
    """层序遍历, 返回列表"""
    if root is None: return []
    res = []
    q = deque([root])
    while q:
        node = q.popleft()
        res.append(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return res

逐层输出（每层一行）

def level_order_layers(root):
    """按层分组输出: [[41], [22,65], [15,28,53,70]]"""
    if root is None: return []
    res, q = [], deque([root])
    while q:
        layer = []
        for _ in range(len(q)):     # 本层全部处理完
            node = q.popleft()
            layer.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        res.append(layer)
    return res

应用：树的最大深度

def max_depth(root):
    """BFS 统计层数 = 最大深度"""
    if root is None: return 0
    depth, q = 0, deque([root])
    while q:
        depth += 1
        for _ in range(len(q)):
            node = q.popleft()
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
    return depth

# 递归版: return 1 + max(max_depth(l), max_depth(r))

DFS vs BFS

维度	DFS（栈/递归）	BFS（队列）
路径	纵深探索	逐层扩散
空间	O(树高)	O(最大层宽)
适合	路径问题、回溯	最短路径、按层处理

二分搜索树节点删除

BST 节点删除是最复杂的操作，按「被删节点有几个孩子」分三种情况处理。

三种情况

① 无孩子(叶子): 直接删除, 父指针置空
② 一个孩子: 用孩子顶替
③ 两个孩子: 用「后继」(右子树最小) 或「前驱」(左子树最大) 顶替
   → 保持 BST 性质

删 28(叶子)     删 22(一个孩子15)    删 41(两个孩子, 用后继53)
  41                41                  53
 /  \              /  \                /  22   65           15   65             22   65
 \   / \              / \            / \   /  28 53 70           53  70          15 28 53?  70

实现

def remove(node, val):
    """从子树删除 val, 返回新子树根"""
    if node is None:
        return None
    if val < node.val:
        node.left = remove(node.left, val)
    elif val > node.val:
        node.right = remove(node.right, val)
    else:                          # 找到要删的节点
        # 情况①: 无左孩子(含叶子)
        if node.left is None:
            return node.right      # 右孩子(或None)顶替
        # 情况①': 无右孩子
        if node.right is None:
            return node.left
        # 情况③: 两个孩子 → 用右子树最小(后继)顶替
        successor = node.right
        while successor.left:      # 找右子树最小值
            successor = successor.left
        node.val = successor.val   # 值替换
        node.right = remove(node.right, successor.val)  # 删掉后继
    return node

删除最小值辅助函数

def remove_min(node):
    """删除子树最小节点, 返回新根"""
    if node.left is None:
        return node.right
    node.left = remove_min(node.left)
    return node

def min_node(node):
    while node.left:
        node = node.left
    return node

验证

root = remove(root, 41)
res = []
inorder(root, res)
print(res)   # [15, 22, 28, 53, 65, 70] 仍有序 ✅

二分搜索树的特性

总结 BST 的核心特性与局限性，理解它与其他树结构的取舍。

BST 核心特性

特性	说明
有序性	左 < 根 < 右，中序遍历升序
高效查找	平衡时 O(log n)
动态插入删除	O(log n)，无需移动大量元素
支持 floor/ceil/rank	有序结构天然支持范围查询

验证 BST 合法性

def is_valid_bst(root, lo=float("-inf"), hi=float("inf")):
    """判断是否合法 BST"""
    if root is None: return True
    if not (lo < root.val < hi):
        return False
    return (is_valid_bst(root.left, lo, root.val)
            and is_valid_bst(root.right, root.val, hi))

# 中序法: 中序遍历应严格递增
def is_valid_bst_inorder(root):
    res = []
    inorder(root, res)
    return all(res[i] < res[i+1] for i in range(len(res)-1))

局限性：退化

有序插入: 1,2,3,4,5,6,7
→ 每个节点只有右孩子 → 退化成链表!
        1
                   2
                       3
             ...
查找 O(n) ❌

解决: 平衡树(AVL/红黑树)自动调整高度

BST 的衍生应用

# 1. 验证二叉搜索树
# 2. 第 k 小元素: 中序遍历第 k 个
def kth_smallest(root, k):
    res = []
    inorder(root, res)
    return res[k-1]

# 3. 转化为有序数组 / 有序数组构建平衡BST
def sorted_to_bst(arr):
    if not arr: return None
    mid = len(arr) // 2
    node = Node(arr[mid])
    node.left = sorted_to_bst(arr[:mid])
    node.right = sorted_to_bst(arr[mid+1:])
    return node

选择指南

需求	结构
纯查找/插入	哈希表（O(1)）
有序遍历/范围查询	平衡 BST（AVL/红黑）
取最值	堆
磁盘存储	B+树

并查集基础

并查集（Union-Find / Disjoint Set）：高效处理「连通性」问题——判断两个元素是否属于同一集合、合并两个集合。

核心操作

find(x):  找到 x 所在集合的代表(根)
union(x,y): 把 x、y 所在集合合并
is_connected(x,y): find(x) == find(y)

应用:
- 网络连通性
- 社交网络「是否好友圈」
- 最小生成树 Kruskal
- 迷宫生成

最简实现（数组）

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # parent[i] = i 的父节点
        self.count = n                 # 集合数

    def find(self, x):
        """找根(代表元素)"""
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        """合并 x、y 所在集合"""
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return
        self.parent[rx] = ry           # rx 的父设为 ry
        self.count -= 1

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(5)              # 0~4 各自独立
uf.union(0, 1)
uf.union(2, 3)
print(uf.is_connected(0, 1))   # True
print(uf.is_connected(0, 2))   # False
print(uf.count)                # 3

为什么是树

并查集用「树」表示集合:
- 根 = 集合代表
- parent[i] 指向父节点, 根的父是自己
- find = 沿 parent 向上走到根

优化空间(后续章节):
① 快速查找 → 基于根合并避免退化
② 按 size/rank 合并 → 树矮
③ 路径压缩 → 几乎 O(1)

并查集快速查找

Quick Find：让 find 达到 O(1)——用「数组直接存所属集合代表」的方式，但 union 变慢为 O(n)。

思路

quick find: id[i] 直接存 i 所属集合的"代表"
find(x) → 直接返回 id[x] (O(1))
union(x,y) → 把 y 集合的所有元素 id 改成 x 的代表 (O(n))

例:
初始 id = [0,1,2,3,4]
union(0,1): id = [0,0,2,3,4]   # 1 并入 0 的集合
union(1,2): id = [0,0,0,3,4]   # 2 并入 0, 同时改1(已同组)
union(3,4): id = [0,0,0,3,3]

实现

class QuickFind:
    def __init__(self, n):
        self.id = list(range(n))
        self.count = n

    def find(self, x):
        return self.id[x]          # O(1)

    def is_connected(self, x, y):
        return self.id[x] == self.id[y]

    def union(self, x, y):
        """把 y 所在集合并入 x 所在集合, O(n)"""
        rx, ry = self.id[x], self.id[y]
        if rx == ry: return
        for i in range(len(self.id)):
            if self.id[i] == ry:
                self.id[i] = rx
        self.count -= 1

复杂度

操作	Quick Find	Quick Union(下章)
find	O(1) ✅	O(树高)
union	O(n) ❌	O(树高)
n 次操作	O(n²)	最坏 O(n²)

何时用 Quick Find

✅ 查找极频繁、合并极少
❌ 大量合并 → union 太慢(要扫全数组)
❌ 不适用于动态大规模数据

并查集快速合并

Quick Union：用父指针树表示集合，union 只需改一个指针（O(树高)），find 沿树向上找根。

思路

parent[i]: i 的父节点, 根的父是自己
find(x): 沿 parent 向上走到根
union(x,y): 把 x 的根 指向 y 的根 (改一个指针)

初始: [0,1,2,3,4]
union(0,1): parent[0]=1 → [1,1,2,3,4]
union(2,3): parent[2]=3 → [1,1,3,3,4]
union(1,3): parent[1]=3(根) → [1,3,3,3,4]
    结构: 3 → 1 → 0  和  3 → 2

实现

class QuickUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.count = n

    def find(self, x):
        """沿父链找到根, O(树高)"""
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        """x 的根指向 y 的根, O(树高)"""
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return
        self.parent[rx] = ry
        self.count -= 1

最坏退化

连续 union(0,1), union(1,2), union(2,3):
parent[0]=1, parent[1]=2, parent[2]=3
→ 树退化成链: 3→2→1→0
find(0) 要走 O(n) ❌

解决: 按 size / rank 合并(下两章) → 树保持矮

复杂度对比

操作	Quick Find	Quick Union
find	O(1)	O(树高) ≤ O(n)
union	O(n)	O(树高) ≤ O(n)

并查集 size 的优化

合并时把元素少的树并入元素多的树（按 size 合并），避免树退化，保持 O(log n) 树高。

问题

Quick Union 无脑把 rx 指向 ry:
union(0,1), union(0,2), union(0,3)...  → 链状树
为什么: 每次 x 的根被挂到 y 下面, 让大树的根变成小树的孩子

size 优化: 谁的元素多谁当根 → 树保持矮胖

实现

class UnionFindSize:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n       # 以 i 为根的集合大小
        self.count = n

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return
        # 小的并入大的
        if self.size[rx] < self.size[ry]:
            self.parent[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.parent[ry] = rx
            self.size[rx] += self.size[ry]
        self.count -= 1

为什么有效

按 size 合并后:
- 节点所在树的高度 ≤ log2(集合大小)
- 因为: 每当某节点深度+1, 所在集合至少翻倍
  (它所在的小树被并入 ≥ 自身大小的树)
→ find / union: O(log n) ✅

验证

uf = UnionFindSize(8)
for i in range(1, 8):
    uf.union(0, i)      # 0 一直并入/被并入
# 树高很小(约 log n), find(7) 很快

演进路线

Quick Union        → 最坏 O(n)      ❌
+ size 合并        → O(log n)       ✅
+ 路径压缩(下章)   → 几乎 O(1)      🚀

并查集 rank 的优化

按 rank（树高）合并：把高度低的树并入高度高的树。比 size 更贴合「树高」这个优化目标。

rank vs size

size:  按节点数量合并(元素多的当根)
rank:  按树的高度合并(高的当根)

场景对比:
大树浅(元素多但矮) vs 小树深(元素少但高)
→ rank 合并会把矮的并入高的 → 总高度不增加
→ size 合并可能把高树挂到矮树下 → 高度增加

实现

class UnionFindRank:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n       # 树的高度(大致)
        self.count = n

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry      # 矮的挂高的
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx      # 相等: 随便挂
            self.rank[rx] += 1        # 高度+1
        self.count -= 1

高度变化规则

合并时:
- 高度不同: 矮树挂高树下, 总高不变
- 高度相同: 任选一个当根, 其高度 +1

例:
  树A(高2)  树B(高1)
  A ∪ B →  B 挂到 A 下 → 高度仍 2
  树A(高2)  树B(高2)
  A ∪ B →  A 当根, 高度变 3

复杂度

按 rank 合并: find/union O(log n)
+ 路径压缩(下章): 均摊 ≈ O(1) (反阿克曼函数 α(n))

size vs rank 对比

维度	size	rank
合并依据	节点数	树高
最坏树高	O(log n)	O(log n)
实现	略简单	略复杂(注意高度相等+1)

并查集路径压缩

路径压缩（Path Compression）：find 过程中把沿途节点直接挂到根下，让树变得更矮，均摊复杂度接近 O(1)。

思想

find(4) 沿 4→3→2→1→0 找到根 0:
路径压缩后: 4,3,2,1 全部直接指向 0

     0              0
    /|               /|   1 5       →      1 2 3 4 ...
  /  |              5 ...
 2   6
 /
3
/
4

下次 find(4): 一步直达 ✅

递归路径压缩（最简单）

class UnionFindPC:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        """递归找根, 同时把所有祖先挂到根下"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.parent[rx] = ry

迭代路径压缩（半压缩）

    def find_iter(self, x):
        """两遍法: 先找根, 再回程压缩"""
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        # 第二遍: 沿途全部指向根
        while self.parent[x] != x:
            nxt = self.parent[x]
            self.parent[x] = root
            x = nxt
        return root

完整优化版（rank + 路径压缩）

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        self.count -= 1

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

复杂度

n 次操作均摊: O(n · α(n))
α = 反阿克曼函数, 对任何实际规模都 ≤ 4
→ 可以认为「常数时间」

图论基础和表示

系统学习图的表示：邻接矩阵与邻接表，理解各自适用场景，为图算法打基础。

图的定义

图 G = (V, E)
V: 节点集合, E: 边集合
边可以带方向(有向图)、带权重(带权图)

    0 --- 1
    | \   |
    |  \  |
    3 --- 2
    无向图 4 节点 5 条边

邻接矩阵

# n×n 矩阵, matrix[i][j] = 1 表示 i→j 有边
matrix = [
    [0, 1, 1, 1],   # 0 连 1,2,3
    [1, 0, 1, 0],   # 1 连 0,2
    [1, 1, 0, 1],   # 2 连 0,1,3
    [1, 0, 1, 0],   # 3 连 0,2
]

# 判断 i,j 是否相连: O(1)
def is_adjacent(matrix, i, j):
    return matrix[i][j] != 0

# 获取所有邻居: O(n)(要扫一行)

邻接表

# 每个节点存一个邻居列表
adj = [
    [1, 2, 3],   # 0 的邻居
    [0, 2],      # 1 的邻居
    [0, 1, 3],   # 2 的邻居
    [0, 2],      # 3 的邻居
]

# 获取邻居: O(度数)
def neighbors(adj, i):
    return adj[i]

# 带权图: 存 (邻居, 权重)
weighted = [
    [(1, 5), (2, 3)],
    [(0, 5), (2, 2)],
    [(0, 3), (1, 2)],
]

对比

维度	邻接矩阵	邻接表
空间	O(n²)	O(n + e)
判断相连	O(1) ✅	O(度数)
遍历邻居	O(n)	O(度数) ✅
适合	稠密图	稀疏图(常见) ✅

图类的封装

class Graph:
    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u, v):
        self.adj[u].append(v)
        if not self.directed:
            self.adj[v].append(u)

    def degree(self, u):
        return len(self.adj[u])

g = Graph(4)
g.add_edge(0, 1); g.add_edge(0, 2); g.add_edge(1, 2)
g.add_edge(0, 3); g.add_edge(2, 3)

相邻节点迭代器

相邻节点迭代器（Adjacency Iterator）：封装「遍历某节点的所有邻居」的逻辑，让图算法代码更清晰统一。

为什么需要迭代器

图算法(DFS/BFS/Dijkstra)都要"遍历邻居":
- 邻接表: 直接 for v in adj[u]
- 邻接矩阵: for v in range(n): if matrix[u][v]
→ 把"遍历邻居"封装成接口, 图结构变了算法不用改

Python 实现（生成器）

class Graph:
    def __init__(self, n, directed=False, use_matrix=False):
        self.n = n
        self.directed = directed
        self.use_matrix = use_matrix
        if use_matrix:
            self.matrix = [[0]*n for _ in range(n)]
        else:
            self.adj = [[] for _ in range(n)]

    def add_edge(self, u, v):
        if self.use_matrix:
            self.matrix[u][v] = 1
            if not self.directed:
                self.matrix[v][u] = 1
        else:
            self.adj[u].append(v)
            if not self.directed:
                self.adj[v].append(u)

    def neighbors(self, u):
        """相邻节点迭代器: 统一接口"""
        if self.use_matrix:
            for v in range(self.n):
                if self.matrix[u][v]:
                    yield v
        else:
            for v in self.adj[u]:
                yield v

使用迭代器写通用算法

def dfs(g, start, visited):
    """不关心图内部结构, 只用 neighbors()"""
    visited.add(start)
    print(start, end=" ")
    for v in g.neighbors(start):
        if v not in visited:
            dfs(g, v, visited)

# 邻接表版与邻接矩阵版都能跑
g1 = Graph(4, use_matrix=False)
g2 = Graph(4, use_matrix=True)
for e in [(0,1),(0,2),(1,2),(0,3),(2,3)]:
    g1.add_edge(*e); g2.add_edge(*e)

dfs(g1, 0, set())   # 0 1 2 3
print()
dfs(g2, 0, set())   # 0 1 2 3 (同样结果!)

带权图的邻居迭代器

    def weighted_neighbors(self, u):
        """返回 (邻居, 权重)"""
        for v, w in self.adj[u]:
            yield v, w

深度优先遍历与连通分量

DFS（深度优先遍历）在图上的应用：访问所有可达节点，并顺手求出连通分量。

DFS 遍历图

def dfs(g, start, visited):
    visited[start] = True
    print(start, end=" ")
    for v in g.neighbors(start):
        if not visited[v]:
            dfs(g, v, visited)

n = 4
g = Graph(n)
for e in [(0,1),(0,2),(1,2),(0,3),(2,3)]:
    g.add_edge(*e)

visited = [False] * n
dfs(g, 0, visited)   # 0 1 2 3

连通分量

连通分量 = 互相可达的最大节点集合
例: 图有两个不连通的子图:
  子图A: {0,1,2}, 子图B: {3,4}
  → 连通分量: [{0,1,2}, {3,4}], 共 2 个

应用: 判断网络是否连通、找孤立点、朋友圈划分

求连通分量

def connected_components(g):
    n = g.n
    visited = [False] * n
    components = []
    for i in range(n):               # 遍历所有节点
        if not visited[i]:
            comp = []
            stack = [i]
            visited[i] = True
            while stack:             # 迭代 DFS
                u = stack.pop()
                comp.append(u)
                for v in g.neighbors(u):
                    if not visited[v]:
                        visited[v] = True
                        stack.append(v)
            components.append(comp)
    return components

# 构造两个不连通部分
g2 = Graph(5)
for e in [(0,1),(1,2),(3,4)]:
    g2.add_edge(*e)
print(connected_components(g2))
# [[0, 2, 1], [4, 3]]  → 2 个连通分量

DFS 变体

用途	做法
可达性判断	从 start DFS，看 target 是否 visited
环检测	DFS 时遇到「已在栈中」的边
拓扑排序	后序 DFS 的反转
二分图判定	DFS 染色，相邻不同色

寻路算法

寻路（Path Finding）：在图中找到从起点到终点的路径。DFS 可寻路但不保证最短，BFS 在无权图中保证最短路径。

DFS 寻路

def dfs_find_path(g, start, target):
    """用 DFS 找一条路径(不保证最短)"""
    n = g.n
    visited = [False] * n
    path = []

    def dfs(u):
        visited[u] = True
        path.append(u)
        if u == target:
            return True
        for v in g.neighbors(u):
            if not visited[v]:
                if dfs(v):
                    return True
        path.pop()           # 回溯
        return False

    dfs(start)
    return path if path and path[-1] == target else []

# 递归回溯是「找路径」的模板

记录父节点寻路（更通用）

def find_path(g, start, target):
    """DFS/BFS 记录 parent, 从 target 回溯路径"""
    n = g.n
    visited = [False] * n
    parent = [-1] * n
    stack = [start]
    visited[start] = True
    while stack and not visited[target]:
        u = stack.pop()
        for v in g.neighbors(u):
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                stack.append(v)
    # 回溯构建路径
    path = []
    if visited[target]:
        cur = target
        while cur != -1:
            path.append(cur)
            cur = parent[cur]
        path.reverse()
    return path

无权图最短路径（BFS）

def bfs_shortest(g, start, target):
    """BFS 首次到达 = 最短路径(无权图)"""
    from collections import deque
    n = g.n
    visited = [False] * n
    parent = [-1] * n
    q = deque([start])
    visited[start] = True
    while q:
        u = q.popleft()
        if u == target:
            break
        for v in g.neighbors(u):
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                q.append(v)
    # 回溯
    path, cur = [], target
    if visited[target]:
        while cur != -1:
            path.append(cur)
            cur = parent[cur]
        path.reverse()
    return path

# 为什么 BFS 最短: 逐层扩散, 首次到达即最浅层

广度优先遍历与最短路径

BFS（广度优先遍历）的完整应用：层级遍历、无权图最短路径、多源 BFS。

BFS 遍历

from collections import deque

def bfs(g, start):
    """BFS 遍历整个连通部分"""
    n = g.n
    visited = [False] * n
    visited[start] = True
    q = deque([start])
    while q:
        u = q.popleft()
        print(u, end=" ")
        for v in g.neighbors(u):
            if not visited[v]:
                visited[v] = True
                q.append(v)

BFS 求最短路径（含距离）

def bfs_shortest_dist(g, start):
    """返回每个节点到 start 的最短距离(无权图)"""
    n = g.n
    dist = [-1] * n          # -1 = 不可达
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in g.neighbors(u):
            if dist[v] == -1:       # 未访问
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

# 例: 0--1--2--3
#     dist = [0, 1, 2, 3]

网格地图 BFS（迷宫最短步数）

def maze_shortest(maze, start, end):
    """网格迷宫最短路径(0可走1是墙)"""
    rows, cols = len(maze), len(maze[0])
    dirs = [(0,1),(1,0),(0,-1),(-1,0)]
    dist = [[-1]*cols for _ in range(rows)]
    sr, sc = start
    dist[sr][sc] = 0
    q = deque([(sr, sc)])
    while q:
        r, c = q.popleft()
        if (r, c) == end:
            return dist[r][c]
        for dr, dc in dirs:
            nr, nc = r+dr, c+dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and maze[nr][nc] == 0 and dist[nr][nc] == -1):
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return -1   # 不可达

多源 BFS（多个起点同时扩散）

def multi_source_bfs(g, sources):
    """从多个源同时 BFS(如多个城市同时扩张)"""
    n = g.n
    dist = [-1] * n
    q = deque()
    for s in sources:
        dist[s] = 0
        q.append(s)
    while q:
        u = q.popleft()
        for v in g.neighbors(u):
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist