4.1 图论与组合计数

4.1 图论与组合计数

本节摘要：图是"事物 + 关系"的最小抽象，社交网络、依赖图、路由表都是它的化身。本节从图的表示与遍历讲起，实现广度优先搜索并分析其复杂度，走过最短路、生成树两个经典问题，再补上组合计数三件套（计数原理、容斥原理、鸽巢原理），最后用"六度分隔"与网络直径实验把理论接到真实数据上。

一张三十亿顶点的图

社交平台的好友关系是一张拥有几十亿顶点的图，搜索引擎的页面链接图更大。这些图大到无法画出来，但结构与算法完全同构于课本上的小图：顶点集合加边集合，仅此而已。抽象的胆量在于扔掉了所有与"关系"无关的信息——剩下来的东西才能规模化。表示法有两大家：邻接矩阵（查询快、空间大，适合稠密图）与邻接表（空间省，适合稀疏图），真实网络几乎都是稀疏的，邻接表是标配。

遍历：一切图算法的地基

深度优先（DFS）沿一条路走到黑再回溯，天然适合连通性检测与拓扑排序；广度优先（BFS）按距离圈层扩散，第一次到达即最短路（无权图）。实现 BFS 并在一个模拟社交网络里测"度分隔"：

from collections import deque

class Graph:
    def __init__(self):
        self.adj = {}                       # 邻接表：顶点 -> 邻居列表

    def add_edge(self, u, v):
        self.adj.setdefault(u, []).append(v)
        self.adj.setdefault(v, []).append(u)

def bfs_levels(graph, start):
    # BFS 返回：每个顶点到 start 的距离（圈层结构 = 六度分隔的计算内核）
    dist = {start: 0}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph.adj.get(u, []):
            if v not in dist:
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist

# 模拟一张小社交网络
g = Graph()
edges = [("A","B"),("A","C"),("B","D"),("C","E"),("D","F"),("E","F"),("F","G"),("G","H")]
for u, v in edges:
    g.add_edge(u, v)

d = bfs_levels(g, "A")
print(d)          # A:0, B/C:1, D/E:2, F:3, G:4, H:5 —— A 到 H 需要 5 步
# 复杂度：每个顶点入队一次、每条边查看两次，总计 顶点数加边数，线性
​

真实社交网络的实测结果是平均距离约 3 到 5 步——"六度分隔"的数学内核是随机图的直径增长极慢（对数级）。 Watts 与 Strogatz 后来揭示更微妙的结构：真实网络兼具高聚类与短路径（小世界模型），而 Erdős–Rényi 随机图只有短路径没有聚类。网络科学就此从图论分岔而出。

最短路、生成树：两条工业化流水线

带权图的最短路有两套武器：Dijkstra 算法处理非负权重（贪心地按距离圈层扩张，配合优先队列复杂度降到边数加顶点数乘对数），动态规划思想的 Floyd–Warshall 一次算出全部点对（顶点数三方，适合稠密小图）。最小生成树则是另一类问题：用最小总边权把所有顶点连通——电网布线、网络组网的模型，Kruskal 算法（按边权排序 + 并查集防环）十几行就能写完：

class DSU:
    # 并查集：Kruskal 的防环雷达
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # 路径减半
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False          # 已连通，加边必成环
        self.parent[ra] = rb
        return True

def kruskal(n, weighted_edges):
    total = 0
    dsu = DSU(n)
    for w, u, v in sorted(weighted_edges):   # 边权从小到大
        if dsu.union(u, v):
            total += w
    return total

# 四个节点之间的布线成本
edges = [(1, 0, 1), (4, 0, 2), (3, 1, 2), (2, 1, 3), (5, 2, 3)]
print(kruskal(4, edges))   # 输出 6：选边 1、2、3，连通全部节点且总成本最小
​

组合计数三件套

图算法问"怎么走"，组合数学问"有多少种走法"。乘法原理与加法原理是计数的与门和或门；容斥原理处理集合重叠的扣除（错排问题、素数筛的欧拉函数都靠它）；鸽巢原理（第 1 章见过）给出无需计数的存在性。组合爆炸是它们的共同签名——排列数以阶乘速度增长，20 个元素的全排列已超过 2 乘 10 的 18 次方，这正是第 1 章 SAT 问题困难性的组合根源，也是密码学安全的资源（下一节的 RSA 依赖大整数分解的指数级搜索空间）。

from math import comb, factorial

# 容斥原理实战：1 到 100 中能被 3 或 5 整除的数的个数
def div_or(a, b, n):
    return n // a + n // b - n // (a * b)   # 加上重叠被扣除的部分
print(div_or(3, 5, 100))    # 47：33 + 20 - 6，经典容斥

# 错排：n 个元素全部不在原位的排列数（递推 d(n) = n*d(n-1) + (-1)^n）
def derangement(n):
    d = [1, 0] + [0] * (n - 1)
    for k in range(2, n + 1):
        d[k] = k * d[k - 1] + (-1) ** k
    return d[n]
print(derangement(6))       # 265；错排比例随 n 趋于 e 分之一
​

邻接表与 BFS 圈层扩散示意

图算法与计数工具的分工地图

⚠️ 工程坑两则：其一，Python 递归实现 DFS 在深图上会撞默认递归深度上限，大规模任务改用显式栈；其二，负权边上的 Dijkstra 会给出错误答案，负权场景要用贝尔曼—福特算法。

本节要点回顾

• 图 = 关系的最小抽象，稀疏真实网络配邻接表，遍历复杂度是顶点加边数的线性级；
• BFS 天生算无权最短路，圈层结构正是"六度分隔"的计算内核；
• 最小生成树用贪心加并查集，十几行代码解决电网组网类问题；
• 组合三件套（计数原理、容斥、鸽巢）是复杂度分析与密码学的共同地基；
• 组合爆炸是困难问题的资源也是密码的护城河，衔接下一节的数论。

关系的结构讲完了，下一节进入数论：看素数如何从"数学玩具"变成守护全球金融的密码基石。