数据结构导论（02142） · 图：存储、遍历与典型应用至练习验收
学习顺序是：先分清逻辑结构与存储方式，再学习线性表、栈队列、树和图，最后比较查找与排序。每一类结构都按“表示 → 操作 → 复杂度 → 选择条件”理解，算法实现可继续读对应手册。
图：存储、遍历与典型应用
图与邻接关系
图用 G=(V,E) 表示。基础课程常约定 V 非空，E 可空；有向边有起终点，无向边没有方向。是否允许重边和自环需先声明，不能把简单图规则默认为所有图的定义。
简单无向完全图边数为 n(n−1)/2，简单有向完全图为 n(n−1)。无向图各顶点度数之和为 2|E|；有向图入度和、出度和均为 |E|。
路径连接一串顶点；简单路径通常不重复顶点；环的起终点相同。无向连通图中任意两点可达，不连通时拆成连通分量；有向图要区分单向可达与强连通。
邻接矩阵与邻接表
| 表示 | 空间与访问特点 |
|---|---|
| 邻接矩阵 | O(V²) 空间；可直接判断两点是否有边；无向图矩阵对称 |
| 邻接表 | O(V+E) 空间；便于枚举邻居；无向边通常保存两个邻接项 |
带权图要区分“无边”与权重 0，不能用同一个值模糊表示。十字链表、邻接多重表等是为特定有向/无向操作设计的表示，不是另外的逻辑图类型。
DFS、BFS 与连通分量
在下图无向图中，若从A开始且先访问B，DFS可以是A、B、D、C，BFS可以是A、B、C、D。D与两条分支相连，所以访问标记能防止重复处理。
查看图表代码
DFS 沿一条路径深入再回溯，常用栈；BFS 按距离层次扩展，常用队列。两者都需要访问标记，防止环造成重复访问；BFS 通常在入队时标记。
邻居访问顺序不同可得到不同遍历序列；遍历本身没有固定唯一答案。要覆盖不连通图，应从每个尚未访问的顶点启动遍历；使用邻接表时总复杂度通常为 O(V+E)。
实现对照见 DFS、BFS 与连通分量。
最小生成树与拓扑排序
生成树覆盖连通无向图的全部顶点且没有环，边数为 V−1。遍历生成树不一定是最小生成树；带权图的最小生成树要求总边权最小。
- Prim 从已有树选择连接外部顶点的合适边；Kruskal 按权处理边，常配并查集避免环。实现和数据结构决定复杂度，不能只按稠密/稀疏一句话选定。
- 拓扑排序用于有向无环图。可反复输出入度为零顶点并删除其出边；若最终输出数小于 V，说明存在环。
- 最短路径与最小生成树的目标不同，不能把“总边权最小”当成“根到每点都最短”。
具体实现见 Prim 与 Kruskal 最小生成树、拓扑排序。
查找：从顺序扫描到散列
顺序、折半与分块查找
有序数组[2,5,8,11,14]查11时，先与中间8比较，排除8及其左边；再在右半区比较11。区间每次至少缩小，结束条件必须与闭区间或半开区间约定一致。
查看图表代码
顺序查找逐项比较，无需有序但最坏 O(n)。折半查找要求有序且能有效访问中间位置，每步缩小区间，最坏 O(log n)；它不是从末尾逐项扫描。
分块查找先通过块间有序的索引定位块，再在块内查找。使用前先明确索引维护与块内顺序条件。
二叉搜索树与散列表
二叉搜索树要求左子树键小于当前键、右子树键大于当前键；重复键策略另行定义。查询沿路径进行，复杂度取决于树高；未经平衡的树可能退化为链，不能保证所有输入都是对数级。
散列表通过哈希定位候选位置，仍需比较原始键以处理碰撞。常见冲突策略有链地址与开放寻址，负载因子和哈希质量影响性能；平均常数级不是最坏常数级。
静态查找表重点是查询，动态查找表还需支持插入删除；“静态”不等于只能二分，“动态”也不等于只有某一种树。
排序：过程、稳定性与选择
先明确稳定性与内外排序
稳定排序保持相同键记录原来的相对次序。内排序主要在内存完成；外排序还需考虑数据无法整体装入内存时的 I/O。比较辅助空间时不把输入本身再加一次。
| 方法 | 平均 / 最坏时间 | 常见辅助空间 | 稳定性（常见实现） |
|---|---|---|---|
| 直接插入 | O(n²) / O(n²) | O(1) | 稳定 |
| 冒泡 | O(n²) / O(n²) | O(1) | 稳定 |
| 直接选择 | O(n²) / O(n²) | O(1) | 不稳定 |
| 快速 | O(n log n) / O(n²) | 平均栈 O(log n)，朴素递归最坏 O(n) | 不稳定 |
| 堆 | O(n log n) / O(n log n) | 原地实现 O(1) | 不稳定 |
| 数组归并 | O(n log n) / O(n log n) | O(n) | 稳定 |
各方法的操作与不变量
归并时两侧已经有序，比较各自当前首项，把较小者写入结果并前进该侧指针。下图将[2,5]与[1,4]合并；若键相等先取左侧，才能延续原有相对次序。
查看图表代码
- 直接插入：前缀已有序，把当前项插进正确位置；相等键不跨越，保持稳定。
- 冒泡：交换逆序相邻项，一趟后一个极值到位；整趟无交换可提前结束。
- 直接选择：从未排序区找最小项，与当前首项交换；非相邻交换可能打乱相等键的次序。
- 快速：围绕枢轴分区，再递归处理两边。差的枢轴会导致不平衡递归，退化为平方级，但不是“变成冒泡排序”。
- 堆：建堆，再反复将堆顶交换到尾部、缩小堆并下沉调整。
- 归并：把有序子序列合并，等值时优先取左侧可保持稳定。
例如冒泡第一趟处理 21,25,49,25,16,8 后得到 21,25,25,16,8,49。后续只处理尚未就位的区间；手算时同时记录比较、移动与边界，避免只背最终结果。
完整算法示例见 比较排序实现。
练习验收
- 对同一序列分别用数组与链表插入/删除，说明定位成本与修改成本。
- 手算循环队列从满到空的下标，覆盖回绕和只剩一个元素。
- 为一棵带空子树的二叉树写四种遍历结果，用图核对顺序。
- 为含环且不连通的图执行 DFS/BFS，确认每点恰好访问一次。
- 用相等键、已有序、逆序和空输入比较排序；分别说明时间上界、递归栈与稳定性。
继续阅读
- 专题笔记
- 专题笔记
- 系统学习