跳转到内容
Arietids Learn

第五章 图 · 速览

数据结构目录阅读详版下载 Markdown

概念速记

跳转到：概念速记
  • 图 G=(V,E)G=(V,E)：VV 顶点非空集合，EE 边（弧）集合；图表示"多对多"关系。
  • 有向边 ⟨C,A⟩\langle C,A\rangle（尖括号，C 弧尾、A 弧头）；无向边 (C,A)(C,A)（圆括号，与 (A,C)(A,C) 同一条边）。
  • 度：无向图＝邻接边总数；有向图分出度（射出）/入度（射入）。邻接＝顶点间有边相连。
  • 图的限制：本章默认简单图无重边、无自环 (j,j)(j,j)/⟨j,j⟩\langle j,j\rangle；树中除根外直接前驱唯一，图中顶点的直接前驱不保证唯一，也可能没有。
  • 完全图边数上界：无向 Cn2=n(n−1)2C_n^2=\frac{n(n-1)}{2}；有向 Pn2=n(n−1)P_n^2=n(n-1)。
  • 网络＝边带权重的图（加权有向图/加权无向图统称）。
  • 路径长度两种度量：无权图按边数；带权图可按权重之和（先看是否带权再计算）。
  • 简单路径/简单回路：除首尾可相同外其余顶点都不相同；首尾相同的简单路径＝简单回路。中间任何顶点重复即非简单。
  • 子图：V′⊆VV'\subseteq V，E′E' 取 EE 中两端点均属于 V′V' 的边的子集（边集不必取全、与画法无关；G 是自身的子图）。
  • 连通分量＝无向图的极大连通子图（孤立顶点自成一个分量）；强连通分量＝有向图的极大强连通子图，要求每对顶点双向可达，单顶点可自成强连通分量。

存储结构对照

跳转到：存储结构对照
结构适用关键字段要点
邻接矩阵有向/无向一维顶点数组 + 二维矩阵有向：行=出度、列=入度；无向：对称、对角全 0，可只存上/下三角；边少时浪费（恒占 n2n^2 单元）
加权邻接矩阵网络A[i][j]=wA[i][j]=w / ∞\infty（无边）/ 对角 00有向加权矩阵一般不对称
邻接表有向/无向顶点表 data/adj + 边结点 dest/weight/link出度＝边表长度（方便）；无向图每条边存 2 次
逆邻接表仅有向边结点存 src方便求入度、不便求出度

实现要点（C++）

跳转到：实现要点（C++）
  • 邻接矩阵版：矩阵两步动态分配（行指针数组→逐行）；初始化对角线 0、其余 noEdge；existEdge 用 i==verts 判"未找到"、i==j 返 false；removeVertex＝顶点表前移＋扫第 ii 行减边数（有向再扫第 ii 列）＋矩阵删行删列＋verts--。
  • 邻接表版：insertEdge 头插法，无向图镜像插两个结点但 edges++ 仅一次；removeVertex 五步——删自身边链（计数）→摘各表中 dest==i 结点→所有 dest>i 的下标减 1→有向 edges-=count、无向 edges-=count/2→顶点表前移。

图的遍历

跳转到：图的遍历

  • 共同前提：顶点无根、地位相同；可能有回路 → 必须用 visited 标记防重复访问；非连通图需外层循环逐一选未访问顶点再启动。两种遍历结果都不唯一（如 G17 两种 DFS、G18 两种 BFS）。

  • DFS（类比二叉树前序）：访问顶点→置标记→依次对未访问邻接点递归。非递归用栈存顶点编号；弹栈后必须再判 if (visited[start]) continue;（同一顶点可被多次进栈）。改进：栈改存边结点地址（邻接表）或 (i,j)(i,j) 二元组（邻接矩阵）。

  • BFS（类比二叉树层次遍历）：用队列存顶点编号；出队后同样需二次判 visited，访问后将所有未访问邻接点入队（入队时不置标记）。

  • 复杂度：邻接表存储下 DFS（递归/非递归）与 BFS 均为 O(n+e)O(n+e)（每顶点访问一次＋每边表扫一遍）。

  • 例题·最大岛屿面积（网格 DFS）：主函数双重 for 枚举格子，遇 1 调 getArea 四向递归求面积、三目取最大；把访问过的格子置 0 代替 visited；「相邻」只算水平/竖直四方向（对角不算，示例答案 6 而非 11）；无岛返回 0。

图的连通性

跳转到：图的连通性
  • 无向图连通性：在 DFS/BFS 外循环加计数器 count（每启动一次新遍历 +1）——count==1 连通；count>1 不连通且 count＝连通分量个数，每轮访问的顶点集＝一个分量。内层遇 visited[p->dest]==true 提示可能有回路。
  • 有向图强连通分量（三步 DFS 法）：①对 G 做 DFS，按回退次序编号（最先回退＝1）；②所有边反向得 Gr；③在 Gr 上反复"选未访问的最大编号顶点做 DFS"——每次 DFS 访问的顶点集＝一个强连通分量。例 G19：回退编号 F=1,B=2,D=3,C=4,A=5,E=6 → Gr 上三次 DFS 得 {E}\{E\}、{A,B,C,D}\{A,B,C,D\}、{F}\{F\}，故非强连通图。
  • 欧拉概念：欧拉路径＝每条边恰走一次；首尾相同→欧拉回路（即"一笔画"）；有欧拉回路→欧拉图（E 图）；只有欧拉路径→半欧拉图。
  • 欧拉定理（前提：无向连通图，按奇度顶点数分类）：>2 个奇度顶点→无欧拉路径；恰 2 个→存在以两奇度顶点为起终点的欧拉路径；全偶→任意起点存在欧拉回路。记忆：路径"有进必有出"→中间顶点度必偶、起终点（不同时）度必奇。七桥问题四顶点度 3,5,3,3 全奇→无解。
  • 欧拉回路求解（回路拼接法）：任选 v 沿未访问边 DFS 回到 v 得首个回路→从结果回路上尚有未访问边的顶点再搜一个回路并在该顶点处并入→重复至无未访问边。标记按边记。例 G20（度全偶）：2->0->4->2 ⊕ 0->1->3->0 ⊕ 3->4->5->3 ⇒ 2->0->1->3->4->5->3->0->4->2。
  • 欧拉实现：私有 EulerCircuit(start,end) 找一段路径，公有函数用 EulerNode{NodeNum,next} 单链表拼接各段；访问边后从邻接表删除，用 clone() 备份并在输出前恢复原图；链表中若某顶点仍有未访问边，就以该顶点为起点生成新段并接入原链表。

图的应用算法

跳转到：图的应用算法
  • 最小代价生成树：带权无向连通图的子图，含原网络全部顶点、部分边、保持连通，且在满足这些条件的子图中边权和最小；生成树含 nn 个顶点和 n−1n-1 条边。
  • Prim：着眼于顶点，用 UU 存已入树顶点、WW 存未入树顶点、TT 存树边；维护 source/dist/selected/treeEdges，每轮先用当前选择点松弛未入 UU 的邻接点，再选 dist 最小顶点并入 UU 和 TT；邻接表实现仍为 O(n2)O(n^2)。
  • Kruscal：着眼于边，初始 MST={V,∅}MST=\{V,\varnothing\} 且每个顶点自成连通分量；每次取当前最小边，若加入会成回路则放弃，否则并入 MST，直到边数达到 n−1n-1；讲义原式写作 O(e)+O((n−1)log⁡2e)+O(n2)O(e)+O((n-1)\log_2 e)+O(n^2) 并归为 O(n2)O(n^2)，但若按“可能检查所有边并从堆中删除”严格计，删堆项应为 O(elog⁡2e)O(e\log_2 e)。
  • Dijkstra：单源最短路径，前提是加权有向图边权非负；维护距离标签和已确定集合 SS，反复松弛当前顶点出边，再从 V−SV-S 选距离标签最小者加入 SS。它是贪心算法，负权边会破坏正确性；邻接矩阵实现为 O(n2)O(n^2)。
  • 无权最短路径：边无权值时，可把每条边权都看作 1 后用 Dijkstra，也可从源点做 BFS；顶点被遍历时获得最短距离，其距离为直接前驱顶点距离加 1。
  • Floyd：所有顶点对最短路径；若 dist<i,j> > dist<i,k> + dist<k,j>，用经由 kk 的路径刷新，并用 pre[i][j] 记录中介顶点以恢复路径；时间复杂度 O(n3)O(n^3)。Floyd 允许负权边，但不允许负权回路。
  • AOV / AOE：AOV（Activity On Vertex Network）把活动放在顶点上，边表示活动先后关系，典型应用是课程先修；AOE（Activity on Edge Network）把活动放在边上，顶点表示事件/状态，典型应用是工程问题。AOV 对应拓扑排序，AOE 对应关键路径。
  • 拓扑排序：先把所有入度为 0 的顶点入栈/队列；每弹出一个顶点，就把它射出的邻接点入度减 1，减到 0 时入栈/队列。拓扑序列不唯一；可用来判断有向图是否有环。邻接矩阵 O(n2)O(n^2)，邻接表 O(n+e)O(n+e)。
  • 关键路径：先求顶点事件最早/最迟发生时间，再求活动最早/最迟开始时间；活动 ⟨u,v⟩\langle u,v\rangle 的最早开始时间为 ve(u)ve(u)，最迟开始时间为 vl(v)−w(u,v)vl(v)-w(u,v)，二者相等则为关键活动，关键活动组成从起点到终点的一条或多条关键路径。
  • 关键路径实现：keyActivity 用 verEarly/verLast 存顶点事件最早/最迟发生时间，用 edgeEL 存活动边的 early/last；先按拓扑次序正推最早时间，再按逆序倒推最迟时间，最后输出 early==last 的边。邻接矩阵实现总时间代价为 O(n2)O(n^2)。

高频易错点清单

跳转到：高频易错点清单
  1. 路径长度：带权图按权和、无权图按边数，勿混用。
  2. 邻接矩阵初始化：对角线是 0，其余才是 noEdge。
  3. 邻接表删顶点：dest>i 的下标必须减 1；无向图 edges -= count/2。
  4. DFS/BFS 非递归：出栈/出队后必须再次检查 visited（同一顶点可能重复入栈/入队）。
  5. 欧拉定理前提"无向连通图"不可省略；标记按边而非按顶点。
  6. 强连通分量第三步在反向图 Gr 上、按编号从大到小选起点，勿在原图上做。
  7. Dijkstra 只适用于非负权边；遇负权边时，贪心确定的顶点距离可能后来被改短。
  8. Floyd 可以处理不在负权回路中的负权边，但不能处理边权和为负的回路。
  9. 拓扑排序结果不唯一；“入度为 0 的顶点”可用栈也可用队列保存，不同选择会影响输出序列。
  10. AOV 顶点是活动、边是先后关系；AOE 边是活动、顶点是事件/状态，二者不要混用。
  11. 关键活动判定看活动的最早开始时间是否等于最迟开始时间，不是只看顶点最早/最迟时间是否相等。