编译器、数据库与推荐系统：工程图数据检阅

编译器、数据库与推荐系统：工程图数据检阅

「依赖解析」「查询计划」「协同过滤」——编译器工程师、数据库内核工程师与推荐算法工程师的日常行话背后，站着的其实是同一批老朋友：构建系统把"谁依赖谁"画成有向图等拓扑排序定序；查询优化器把多表连接画成图搜最好的连接次序；推荐系统把用户与物品画成二分图做匹配与邻居扩散。凯旋检阅的最后一场设在工程后厨，本节把三套系统的图内核逐一拆开，检阅第 4、5、6、7 章兵法的生产环境成色，并在册尾划清经典图论与图神经网络的边界。

构建系统：依赖图上的拓扑序

从源码到可执行文件，中间隔着一条依赖链：目标文件依赖源文件、链接依赖目标文件、测试依赖链接产物。现代构建工具的核心是一张有向无环图——节点是构建目标，边是依赖关系；构建的执行次序就是拓扑排序（第 6 章），而"哪个目标需要重建"靠从变更源出发的可达性遍历（第 3 章深度优先）。

import networkx as nx
from collections import deque

def build_plan(dag, changed):
    """给定变更的源文件，算出最小重建清单（按拓扑序）"""
    need = set(changed)
    stack = list(changed)                    # 沿依赖方向正向扩散
    while stack:
        u = stack.pop()
        for v in dag.successors(u):          # 依赖 u 的下游目标
            if v not in need:
                need.add(v)
                stack.append(v)
    sub = dag.subgraph(need)
    return list(nx.topological_sort(sub))

build = nx.DiGraph()
build.add_edges_from([
    ("app.c","app.o"),("util.c","util.o"),("app.o","link"),
    ("util.o","link"),("link","test"),("readme.md","docs")])
print("util.c 变更后需重建:", build_plan(build, ["util.c"]))
​

输出会跳过与 util.c 无关的文档分支——增量构建的省时全靠可达性剪枝。第 6 章末尾提过的"循环依赖"处理在这里是生产事故级议题：两个模块互相引用时拓扑序失效，构建工具报出的正是第 4 章"回边"圈出的那批环顶点，工程师拿着报错去拆环（提取公共依赖、加接口层），本质是手工完成"缩点再排"的调度。

数据库：连接次序的图上博弈

一条查询要连接好几张表时，数据库内核面对一道组合难题：连接次序不同，中间结果的大小可以差出几个数量级。优化器把候选连接方案组织成连接图（表为顶点、连接条件为边），在图上搜索代价最小的连接树——这棵树的每一步"合并两个连通块"与第 6 章 Kruskal 的合并动作形似，只是代价函数换成了中间结果行数的估计。已有连接关系的两块优先合并（连接条件能压行数），没有关系的两块合并会产生笛卡尔积爆炸——图结构在这里直接编码了"可行性"。

import itertools

def join_order_search(tables, join_conditions, row_estimates):
    """穷举连接次序，按中间结果行数估计挑最优（教育版）"""
    def connected(blocks):                   # 块间是否有连接条件搭桥
        return any(frozenset((a, b)) in join_conditions
                   for a in blocks for b in blocks if a != b)
    best, best_cost = None, float("inf")
    for perm in itertools.permutations(tables):
        blocks, cost = [frozenset((t,)) for t in perm], 0
        for i in range(len(blocks) - 1):     # 依次合并相邻块
            a, b = blocks[0], blocks[1]
            pair_ok = any(frozenset((x, y)) in join_conditions
                          for x in a for y in b)
            rows = row_estimates[frozenset(a)] * row_estimates[frozenset(b)]
            rows = rows * (0.05 if pair_ok else 1.0)   # 有连接条件则大幅压行
            cost += rows
            blocks = [frozenset(a | b)] + blocks[2:]
        if cost < best_cost:
            best, best_cost = perm, cost
    return best, best_cost

tables = ["用户表", "订单表", "商品表", "商家表"]
conds = {frozenset(("用户表","订单表")), frozenset(("订单表","商品表")),
         frozenset(("商品表","商家表"))}
rows = {frozenset((t,)): r for t, r in zip(tables, [8, 60, 300, 20])}
order, cost = join_order_search(tables, conds, rows)
print("推荐连接次序:", " → ".join(order), "| 估计代价:", cost)
​

穷举在表数稍多时爆炸（排列数的阶乘增长），真实优化器用动态规划（表数中等）与贪心剪枝（表数巨大）分层应对——第 5 章 Floyd 的"限制逐步放宽"与第 6 章的贪心思维在数据库内核里合流。索引选择、连接算法（嵌套循环、哈希连接、排序合并）的选择同属图上的代价博弈，那是数据库内核开发的整门手艺，此处点到为止。

推荐系统：匹配、扩散与图学习的边界

推荐是图最浓的战场。用户与物品构成天然二分图，购买、点击、评分是带权的横跨边。经典算法里图论浓度极高：协同过滤的邻居扩散本质是第 3 章的遍历——"与你相似的人还买了什么"是两跳路径的计数与加权；好友召回是社交图上的邻域扩散；供需匹配（打车派单、广告位分配）是第 7 章的带权二分匹配在毫秒级竞拍环境里的化身。

import networkx as nx
from collections import deque

def two_hop_recall(B, user):
    """两跳协同过滤：用户→物品→相似用户→候选物品"""
    hop2 = set()
    for item in B[user]:                     # 用户买过的物品
        for other in B[item]:                # 买过同物品的人
            if other != user:
                for cand in B[other]:        # 他们买过的物品
                    if cand not in B[user]:
                        hop2.add(cand)
    return sorted(hop2)

B = nx.Graph()
B.add_nodes_from(["小明","小红","小刚","小雅"], bipartite=0)
B.add_nodes_from(["科幻小说","机械键盘","桌游","咖啡豆"], bipartite=1)
B.add_edges_from([("小明","科幻小说"),("小明","机械键盘"),
                  ("小红","科幻小说"),("小红","桌游"),
                  ("小刚","机械键盘"),("小刚","咖啡豆"),
                  ("小雅","桌游"),("小雅","咖啡豆")])
print("为小明召回:", two_hop_recall(B, "小明"))
​

两跳遍历为小明召回了桌游与咖啡豆——同好们的选择顺着二分图扩散过来。真实系统在此之上叠加倒排索引、近似最近邻与重排模型，但"邻域扩散"的骨架百年不动。

边界也要在此说透。近年推荐与内容理解大量转向图神经网络——把顶点嵌入向量空间，让深度网络在图上学习表示。那是一整个独立的世界观（消息传递、谱方法、过平滑问题），本册刻意停在了它的门口：经典图论交付的是精确可证的算法（最短路就是最短、匹配就是最大），图学习交付的是从数据里拟合的数值模式。两者的关系是地基与楼层——深度模型读图、采样邻居、构造损失时，调用的仍是本册的遍历、采样与匹配原语。想上楼的读者，请移步站内的图神经网络专题册；想挖网络统计模型的读者，网络科学专题册同样在册单上。

⚠️ 常见坑：把图数据库的"图查询"与图算法混为一谈。前者是模式匹配的查询语言（找路径、找邻居、找子图形态），后者是本册的算法分析（最短、最大、最优）——工具链相邻，思维模式不同，选型时先分清要的是"找到"还是"算出"。

💡 关键直觉：工程后厨的图无处不在，因为"依赖"与"关系"是工程的空气——编译器排依赖、数据库排连接、推荐器排配对，做的都是同一件事：把关系网压成次序或配对。图论是关系世界的通用语法。

检阅收官。从哥尼斯堡的河岸出发，穿过行军、勘定、急行军、架桥、补给、攻坚与归档，远征队在全册末尾把兵法悉数点验——凡有关系处，皆可成图；凡成图处，皆有兵法。