宽列与图数据库：图遍历算法

可视化演示

展示系统处理流水线、实时性能指标曲线及多方案对比分析，包含数据流转、吞吐延迟监控与方案评估。

图的存储结构

拿到一张地铁图，你第一件事是看懂它怎么画的——站点用圆点表示，线路用线段连接。在计算机里，这张图也需要一种“画法”，也就是存储结构。最直观的方式有两种：邻接表和邻接矩阵。

邻接表就像你手机里的通讯录。每个联系人（节点）的名字后面，跟着一串他认识的人（邻居节点）。要查“张三认识谁”，直接翻到张三那一页就行，非常高效。邻接矩阵则像一张班级座位表——行和列都是全班同学的名字，如果第 i 行第 j 列打了个勾，就说明 i 认识 j。这张表查起来极快（看一眼行列交叉处就知道有没有关系），但如果班级有 1000 人，这张表就要有 100 万个格子，大多数格子还空着，浪费空间。

宽列数据库（如 HBase、Cassandra）天然适合存储邻接表——每一行以节点 ID 作为行键，列族里存储所有邻居节点。当图数据规模达到千万级节点时，邻接矩阵所需的存储空间是天文数字，而邻接表只存储真实存在的关系，空间效率高出几个数量级。

1. 节点表示：每个节点（地铁站）在宽列存储中对应一行数据。

$$\text{row\_key} = \text{node\_id}$$

2. 邻居列表：节点的所有出边（从该站出发能到达的站）存储在同一个列族中。

$$\text{column} = \text{neighbor\_id},\quad \text{value} = \text{edge\_weight}$$

3. 空间复杂度对比：邻接矩阵需要 \(V^2\) 个格子，邻接表只需要 \(V+E\) 个存储单元。

$$\text{Matrix: } O(V^2) \quad \text{vs} \quad \text{List: } O(V+E)$$

回到地铁图：现实中的地铁网络每条线路只连接相邻几站，没有哪条线会从“市中心站”直接连到所有其他站。这就是“稀疏图”——邻接表正是为这种场景量身定做的通讯录。而宽列存储把“通讯录”按行组织，让遍历算法在读取某个节点的全部邻居时，只需一次行读取，效率远高于传统关系型数据库的多次 JOIN 操作。

邻接表: {A: [B, C], B: [A, C, D], C: [A, B, E], ...}邻接矩阵:  A  B  C  D        A [0, 1, 1, 0]        B [1, 0, 1, 1]        C [1, 1, 0, 1]        D [0, 1, 1, 0]

广度优先搜索

想象你把一块石头扔进平静的湖面，涟漪从落水点开始，一圈一圈向外扩散。第一圈覆盖“一步就能到达”的区域，第二圈覆盖“两步才能到达”的区域。广度优先搜索（BFS）就是这种“水波式”的遍历：从起点出发，先访问所有直接邻居，再依次访问这些邻居的邻居，层层推进。

在计算机里，BFS 靠一个“队列”来维持遍历顺序。队列就像地铁站的候车通道——先进入的人先上车，先进先出（FIFO）。算法将起点放入队列，然后循环：从队首取出一个节点，访问它，把它的所有未访问邻居排到队尾。这个过程保证了你总是先处理“距离起点更近”的节点，再处理更远的节点。

回到湖面的涟漪——每一圈水波都代表了“从落水点出发，走 k 步能到达的所有位置”。BFS 在社交网络中的典型应用是“我认识的人里，谁和某个陌生人只隔了 3 层关系”？LinkedIn 的“二度人脉”推荐、Facebook 的“可能认识的人”，底层都是 BFS 在奔跑。它找到的路径，在“边的数量最少”这个意义下一定是最短的。

深度优先搜索

有一种探险家的遍历方式：选一条路，一路走到黑，撞了南墙才回头。深度优先搜索（DFS）就是这样的策略——它不满足于浅尝辄止，而是沿着一条路径不断深入，直到无法继续，然后回溯到最近的分岔口，换一条路继续深入。

DFS 的实现依赖“栈”结构——后进先出（LIFO），就像一叠盘子，你总是先拿走最上面那个。递归是 DFS 最自然的表达形式：进入一个节点，递归地访问它的第一个未访问邻居，等那一整条分支走完，再回到上一层继续。也可以用显式栈模拟递归，避免深度过大时栈溢出。

地铁比喻的另一种玩法：DFS 就像一个强迫症游客，拿到地图后坚持“每条支线都要走到底再回来”，虽然走的路径可能绕远，但能完整地探索每个角落。DFS 在工程中的典型应用是检测图中是否存在环（比如检测课程先修关系是否成死循环）、拓扑排序（安排课程学习顺序）、以及判断两个节点是否连通（迷宫求解）。它不需要维护距离信息，空间开销通常比 BFS 更小。

Dijkstra算法

地铁图上的线路长度各不相同，从 A 站到 B 站可能只要 2 分钟，到 C 站却要 15 分钟。如果只关心“经过几个站”，BFS 就够了；但现实中的“路径最短”往往指的是“总耗时最少”。Dijkstra 算法就是为这种带权重的图设计的寻路算法。

Dijkstra 的核心思想是“贪心”——每次都从当前已知的所有候选路径中，选择总距离最短的那一条进行扩展。算法维护一个“已确定最短距离”的集合，和一张“当前已知最短距离”的表。每次从未确定的节点中挑出距离最小的那个，把它标记为确定，然后更新它所有邻居的距离——如果经过这个节点到达邻居比之前的路径更短，就更新邻居的距离。

把你上班的通勤路线想成一次 Dijkstra：地铁每段的行驶时间是边的权重，换乘等待时间也是权重。Google Maps 的路线规划、Uber 的派单调度、物流公司的配送路径优化，背后都有 Dijkstra 或其变体（如 A* 算法）在运行。它和 BFS 的区别在于——BFS 假设每条路一样长，而 Dijkstra 尊重每条路的“真实代价”。

PageRank中心性

前面几种算法回答的是“怎么走”的问题，而 PageRank 回答的是“谁最重要”的问题。想象一个社交网络里，判断一个人是否重要，光看粉丝数不够——如果你有 1000 个粉丝但都是僵尸号，和一个有 100 个粉丝但都是行业大 V 的人相比，后者在网络上更有影响力。PageRank 正是捕捉这种“被重要的人关注，所以你也很重要”的递归逻辑。

PageRank 的数学模型来自“随机游走”：假设一个用户随机点击链接，从当前网页跳到下一个网页。经过足够多次跳转后，用户停留在每个网页上的概率，就是该网页的 PageRank 值。这个值越高，说明网页被访问的概率越大，也就越“重要”。计算方式是迭代的：每一轮，每个节点把自己当前的权重平均分给所有出边邻居，同时接收所有入边邻居分来的权重。

回到城市的比喻：PageRank 是在回答“哪些地铁站是真正的交通枢纽”。一个站即使连接线路不多，但如果它是核心换乘站（像北京西直门），它的重要性会通过“被其他重要站点连接”而放大。Google 当年靠 PageRank 在搜索质量上碾压对手，今天它被广泛应用于社交网络的影响力分析（找到意见领袖）、反欺诈（发现异常密集的资金往来节点）、以及知识图谱中的实体重要性排序。

分布式遍历挑战

当图数据增长到十亿节点、百亿边时，单台机器的内存已经无法容纳整张图。怎么办？把图切碎，分布到几十台甚至上千台机器上。但“切碎”本身带来一个棘手的问题：原本相邻的节点，现在住在不同的机器上。

数据分片主要有两种策略：按节点 ID 哈希分片（把 A 的邻居 B 分到另一台机器），或者按社区/子图分片（尽量把联系紧密的节点放在同一台机器）。前者负载均衡，但遍历时需要频繁跨机器通信——每访问一个邻居，如果它不在本地，就要发一次网络请求。后者能减少通信，但可能造成某些机器负载过高。

这就像你要画一张全国地铁图——但每个城市的地图分别由不同的人保管。要回答“从北京到上海坐地铁怎么走”，你得不断打电话向上海那边的同事确认“下一站在你那儿吗？”每打一次电话就有一秒延迟，路线越长、涉及城市越多，电话费越贵。这正是 GraphLab、Pregel 等分布式图计算框架试图解决的问题：通过批量同步（BSP 模型）和减少通信轮次来摊薄开销，让“打电话”的次数尽量少。

AI 应用场景

Python 演示

import heapqfrom collections import deque  class GraphTraversal:    """图遍历算法演示: BFS, DFS, Dijkstra"""     def __init__(self):        # 邻接表存储: {node: [(neighbor, weight), ...]}        self.graph = {            'A': [('B', 4), ('C', 2)],            'B': [('A', 4), ('C', 1), ('D', 5)],            'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],            'D': [('B', 5), ('C', 8), ('E', 2)],            'E': [('C', 10), ('D', 2)]        }     def bfs(self, start):        """广度优先搜索: 水波式层层扩散, 计算最短跳数"""        dist = {node: float('inf') for node in self.graph}        dist[start] = 0        queue = deque([start])        while queue:            node = queue.popleft()            for neighbor, _ in self.graph[node]:                if dist[neighbor] == float('inf'):                    dist[neighbor] = dist[node] + 1                    queue.append(neighbor)        return dist     def dfs(self, start, visited=None):        """深度优先搜索: 一条路走到黑, 递归实现"""        if visited is None:            visited = set()        visited.add(start)        for neighbor, _ in self.graph[start]:            if neighbor not in visited:                self.dfs(neighbor, visited)        return visited     def dijkstra(self, start):        """Dijkstra最短路径: 贪心策略, 优先队列实现"""        dist = {node: float('inf') for node in self.graph}        dist[start] = 0        pq = [(0, start)]        while pq:            cur_dist, node = heapq.heappop(pq)            if cur_dist > dist[node]:                continue            for neighbor, weight in self.graph[node]:                new_dist = cur_dist + weight                if new_dist < dist[neighbor]:                    dist[neighbor] = new_dist                    heapq.heappush(pq, (new_dist, neighbor))        return dist  if __name__ == '__main__':    gt = GraphTraversal()    print('BFS from A:', gt.bfs('A'))    print('DFS from A:', gt.dfs('A'))    print('Dijkstra from A:', gt.dijkstra('A'))

1. self.graph = {'A': [('B', 4), ...]}用字典实现邻接表，键是节点名，值是 （邻居，权重） 列表。
2. queue = deque([start])BFS 使用双端队列作为先进先出的“候车通道”。
3. dist[neighbor] = dist[node] + 1BFS 中每经过一条边，跳数加 1，第一次到达即最短跳数。
4. visited.add(start)DFS 递归前先标记已访问，防止死循环。
5. heapq.heappop(pq)Dijkstra 用优先队列每次取出当前距离最小的节点，这是贪心策略的体现。
6. if new_dist < dist[neighbor]松弛操作：发现更短路径就更新记录。

常见误区

面试题