图数据结构总览

如果只看定义，“图数据结构总览”并不一定显得难。我当时真正卡住的是：树至少还有清晰的父子关系，图里的边可以任意连接，我一开始很难判断应该怎么存、遍历时又如何避免绕圈。这次整理没有刻意追求一次讲完所有技巧，而是把我最容易断掉的几个理解环节重新接上。

树适合表达层次，图适合表达一般关系。城市与道路、用户与关注、服务与依赖、课程与先修条件，都可以抽象为顶点和边。

它从哪里来

1736 年，欧拉研究柯尼斯堡七桥问题时把陆地抽象成点、桥抽象成边，这通常被视为图论的重要起点。现代图结构延续了同一种力量：忽略对象不相关的细节，只保留关系，就能统一描述道路、依赖、网络和社交连接。

先明确图的语义

图建模规则与算法选择地图

图：从方向、权重和问题目标选择遍历、最短路、拓扑排序或并查集

一张图至少要回答四个问题：

边是否有方向？
边是否有权重？
是否允许自环和重复边？
顶点与边的规模、密度怎样？

无向图中的关系对称；有向图中的 A -> B 不代表 B -> A。加权图的边带距离、成本或容量。DAG 是没有有向环的图，常用于依赖关系和拓扑排序。

图的关键术语

路径：从一个顶点沿边到另一个顶点的序列。
环：起点和终点相同的非空路径。
度：无向图中与顶点相连的边数。
入度/出度：有向图中进入或离开顶点的边数。
连通分量：无向图中彼此可达的最大顶点集合。
强连通分量：有向图中任意两点都互相可达的最大集合。
稠密度：边数相对最大可能边数的比例。

同一个业务名词可能有不同图语义。例如“关注”是有向边，“好友”通常是无向边，“转账”可能是带金额和时间的多重有向边。建模错误会让后续算法从根上失去意义。

两种基础表示

表示	空间	判断两点相邻	遍历某点邻居	适合
邻接矩阵	`O(V²)`	`O(1)`	`O(V)`	稠密图、小规模图
邻接表	`O(V+E)`	通常与度数相关	`O(deg(v))`	稀疏图、通用业务

矩阵简单直接，但一万个顶点就有一亿个槽位；真实关系通常很稀疏，邻接表更常见。若频繁判断边是否存在，可把每个顶点的邻居从 List 换成 Set，在空间和查找速度之间折中。

还有两种常见表示：

边列表：直接保存 (from, to, weight)，适合 Kruskal、批处理和文件交换。
关联矩阵：顶点与边形成矩阵，理论分析价值较高，通用业务中较少直接使用。

实际系统常同时维护邻接表和边表，一个用于在线遍历，一个用于批量计算或持久化，但要明确谁是权威数据，避免双写不一致。

除了空间复杂度，还应比较操作成本：

操作	邻接矩阵	邻接表
添加一条边	`O(1)`	列表通常 `O(1)`，去重可能更高
删除一条边	`O(1)`	`O(deg(v))` 或 Set 平均 `O(1)`
判断边存在	`O(1)`	`O(deg(v))` 或 Set 平均 `O(1)`
遍历全部邻居	`O(V)`	`O(deg(v))`
遍历整张图	`O(V²)`	`O(V+E)`

无向边在邻接表中通常要保存两次，但逻辑边数只能增加一次；删除时也必须同时删除两个方向。有向图若频繁查询前驱，可以同时维护出边表和入边表。这个冗余能加速查询，却会提高写入一致性要求。

遍历是后续算法的地基

广度优先搜索（BFS）使用队列，按层推进，在无权图中能得到最少边数路径；深度优先搜索（DFS）使用递归或栈，适合连通分量、环检测和拓扑相关问题。

BFS 按层推进和 DFS 沿路深入的对比图

图：BFS 使用队列保存同层前沿，DFS 使用栈或递归保存回退路径

遍历必须记录 visited。没有访问标记，含环图会无限重复；若在入队时和出队时标记的时机不同，还可能造成同一节点被重复加入队列。

图算法的路线

这本学习资料重点建立图的结构实现。完成后可继续扩展：

BFS / DFS 与连通分量。
拓扑排序与依赖检测。
Dijkstra、Bellman-Ford、Floyd 最短路径。
Prim、Kruskal 最小生成树。
强连通分量、桥与割点。

不要把算法名称当作孤立题目。选择算法前先看图是否有向、权重是否可能为负、需要单源还是多源答案、数据是否持续变化。

算法选择地图

问题	条件	常用算法
是否可达、连通分量	无权或不关心权重	BFS / DFS
最少经过几条边	无权图	BFS
单源最短路	非负权	Dijkstra
单源最短路	允许负权，无负环	Bellman-Ford
任意两点最短路	顶点较少	Floyd-Warshall
依赖排序	DAG	拓扑排序
无向图最小生成树	连通加权图	Prim / Kruskal
动态合并连通性	主要增加边	并查集

“最短”必须先定义：边数最少、距离最小、费用最低、时间最短，可能对应不同权重，甚至需要多目标优化。

图建模中的状态与时间

现实关系经常会过期、撤销或带版本。把所有历史边都放入一张静态图，会得到错误连通关系。可以按时间窗口构建快照，或让边带 validFrom/validTo 并在查询时过滤。

权限图还需要考虑方向和继承边界；服务依赖图要区分同步调用、异步事件和软依赖；知识图谱则需要给边设置关系类型，不能把“属于”“依赖”“相似”混成同一种边。

从需求到图模型

开始编码前，可以依次写出下面的模型契约：

顶点代表什么，业务主键是否稳定。
边的方向、类型、权重和唯一性规则。
自环、多重边、孤立点是否允许。
删除顶点时边是级联删除、软删除还是保留历史。
查询关注一跳、多跳、最短路、连通性还是聚合统计。
图是实时更新、定时快照还是离线批处理。

以课程系统为例，若边定义为 course -> prerequisite，拓扑排序时的入度含义必须与实现一致；如果代码却把方向理解成“先修课指向后续课程”，输出顺序会整体相反。图算法写对了，边语义仍可能错，所以契约测试应使用真实业务例子。

复杂度不只看 V 和 E

图算法通常用顶点数 V 和边数 E 表达复杂度，但生产数据还要关注度数分布。社交网络可能存在度数极高的超级节点，一次邻居展开就产生巨大结果；普通平均度无法反映这种热点。

常见保护包括限制遍历深度和返回数量、对高出度节点分页、为查询设置时间预算、避免把完整路径无限累积在内存中。多租户图还必须在每一步扩展都带租户或权限过滤，不能遍历完再过滤，否则既浪费资源也可能泄漏关系。

工程中的图

业务关系可以存入关系型数据库、图数据库或搜索索引。是否上图数据库不取决于“数据像图”，而取决于查询是否以多跳关系为核心、规模和延迟要求怎样、团队能否维护新的存储系统。很多一跳或两跳关系用普通表和索引已经足够。

关系型数据库通常用边表：

CREATE TABLE graph_edges (
  from_id BIGINT NOT NULL,
  to_id BIGINT NOT NULL,
  relation_type VARCHAR(50) NOT NULL,
  weight DECIMAL(18, 6) NULL,
  PRIMARY KEY (from_id, to_id, relation_type),
  KEY idx_graph_edges_to (to_id, relation_type)
);

从某点查一跳邻居很自然，多跳递归查询则要评估数据库能力和深度上限。图数据库的优势是关系遍历语言和多跳执行模型，代价是新的存储、备份、监控和一致性体系。

当边数据写入关系库、缓存和搜索索引时，应明确主存储与派生视图。常见做法是先提交权威边表，再通过事务消息或变更日志异步更新图查询视图；消费者需要幂等，延迟需要监控，重建过程需要可回放。直接在一个请求里无事务地双写多个存储，很容易留下永久不一致。

超大图无法放入单机内存时，可以按顶点分区，但跨分区边会带来网络开销。社区结构明显的图适合尽量把紧密连接的顶点放在同一分区；路由规则变化时还要考虑迁移和版本。离线算法则可以使用批处理框架，以迭代方式传播状态。

图算法的正确性测试

不要只测试一张连通无环小图。最小测试集应覆盖：

空图、单顶点、孤立点和多个连通分量。
自环、重复边、双向边以及有向环。
多条等长最短路径、零权边和极大权重。
拓扑排序遇到环时明确失败，而不是返回不完整结果。
Dijkstra 遇到负权时拒绝或切换算法。
删除顶点后不存在悬挂边，边数和度数统计正确。

遍历顺序若受 HashMap 迭代影响，测试不应盲目断言唯一序列；可以固定邻居排序，或断言结果集合和父子约束。算法“结果正确”与“输出稳定”是两个不同要求。

学习与验收清单

同一数据分别用矩阵和邻接表表示并比较空间。
用 BFS、DFS 遍历含环和不连通图。
对有向图实现入度统计与拓扑排序。
构造负权边，观察 Dijkstra 为什么不再可靠。
明确重复边、自环、删除顶点和非法 ID 的规则。
大图使用显式栈，避免递归深度失控。