title: 图结构与遍历 tags:

module
data-structure-and-algorithm
graph
joplin type: module source_type: reconstructed created: 2026-04-22 updated: 2026-04-22 ---

图结构与遍历

[!abstract] 这一模块处理比树更一般的关系结构。图的难点不在定义，而在“如何存、如何遍历、如何理解顶点之间的复杂连接”。

模块结论

[[图]] 适合表达多对多连接关系，是树结构的推广。
邻接矩阵和邻接表分别强调“查询方便”和“存边节省”。
BFS 和 DFS 本质上是两种不同的扩展路径策略，分别依赖 [[队列]] 和 [[栈]] / 递归思维。

一、图的基本组成

顶点
边
有向图 / 无向图
带权图 / 无权图

为什么图比树更一般

树没有回路，且层次关系更明确。
图可以存在回路、交叉连接和更复杂的路径关系。

二、图的存储结构

邻接矩阵

用二维数组表示边关系。
优点是判断两点是否直接相连很直观。
缺点是在稀疏图里浪费空间。

邻接表

每个顶点维护自己的边表。
优点是适合稀疏图，按边存储更节省空间。
缺点是判断任意两点是否直接相连不如邻接矩阵直观。

三、广度优先搜索 BFS

按“距离起点一层一层扩展”的方式遍历。
核心辅助结构是队列。
常用于最短路径层次扩展、连通性检查等场景。

四、深度优先搜索 DFS

一条路尽量走到底，再回溯。
核心辅助结构是递归调用栈或显式栈。
常用于连通分量、拓扑处理前的遍历框架等场景。

五、比较 BFS 与 DFS

BFS 更像层次推进。
DFS 更像路径深入。
一个偏“广度扩散”，一个偏“深度探路”。

六、易错点

图遍历必须配合 visited 标记，否则容易在回路里重复访问。
邻接矩阵和邻接表不是谁绝对更好，要看图的稠密程度和操作需求。
BFS / DFS 顺序会受到顶点存储次序和邻接点访问次序影响。

七、复习提问

邻接矩阵和邻接表分别适合什么图？
BFS 为什么天然适合层次最短路问题？
DFS 为什么常和递归写法联系在一起？

来源

[[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/11.图.md]]
[[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/7.图.md]]

相关页面

[[数据结构与算法]]
[[图]]
[[栈]]
[[队列]]