---
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]]

## 相关页面

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