图的关系概念速查表

这一组概念都在描述“顶点与边/弧的关系”“顶点到顶点能否走到”或“从原图中取出怎样的结构”。复习时先分清：度看边数统计，路径看走法序列，连通性看可达范围，生成结构看保留哪些顶点和边。

概念 适用对象 一句话定义 判定关键词 易错点
度 $TD(v)$ 无向图、有向图 与顶点 $v$ 相关的边或弧的总数 “依附于该顶点” 有向图中 $TD(v)=ID(v)+OD(v)$
入度 $ID(v)$ 有向图 以 $v$ 为终点的弧数 箭头指向 $v$ 只数进入的弧，不数出去的弧
出度 $OD(v)$ 有向图 以 $v$ 为起点的弧数 箭头从 $v$ 发出 只数出去的弧，不数进入的弧
路径 无向图、有向图 从一个顶点到另一个顶点的顶点序列 相邻顶点之间有边或方向正确的弧 有向图路径要沿弧方向
回路，也称环 无向图、有向图 起点和终点相同的路径 首尾顶点相同 回路不一定是简单回路
简单路径 无向图、有向图 顶点不重复出现的路径 顶点不重复 起点和终点也不能重复，否则变成回路
简单回路 无向图、有向图 除首尾同一顶点外，其余顶点不重复的回路 首尾相同，中间不重复 允许第一个顶点和最后一个顶点相同
路径长度 无向图、有向图 路径上边或弧的数目 数边，不数点 经过 $k$ 个顶点的路径长度通常是 $k-1$
距离 无向图、有向图 两点间最短路径的长度 最短路径 不存在路径时记为 $\infty$
连通 无向图 两个顶点之间存在路径 有路径可达 只用于无向图的普通可达关系
强连通 有向图 两个顶点互相都有路径可达 双向可达 $v$ 到 $w$ 可达不代表 $w$ 到 $v$ 可达
连通图 无向图 任意两个顶点都连通 任意两点可达 $n$ 个顶点的连通图最少有 $n-1$ 条边
非连通图 无向图 至少有一对顶点不连通 存在两点不可达 $n$ 个顶点的非连通图最多有 $C_{n-1}^{2}$ 条边
强连通图 有向图 任意两个顶点都强连通 任意两点双向可达 $n$ 个顶点的强连通图最少有 $n$ 条弧
子图 无向图、有向图 从原图中取部分顶点和部分边或弧 $V’\subseteq V,\ E’\subseteq E$ 选了边或弧，就要同时保留它的端点；有向图还要保留方向
生成子图 无向图、有向图 保留原图全部顶点的子图 $V(G’)=V(G)$ 生成子图不一定连通，也不一定是树
连通子图 无向图 本身连通的子图 子图内部任意两点可达 连通子图不一定是连通分量
连通分量 无向图 极大连通子图 极大、连通 不是随便取一个连通子图，而是已经不能继续扩大
强连通分量 有向图 极大强连通子图 极大、强连通 考手算 SCC 个数时优先用 Kosaraju 的两次 DFS；代码分析再看 Tarjan 的 dfn、low 和栈
生成树 连通无向图 包含全部顶点的极小连通子图 全顶点、连通、边尽可能少 有 $n-1$ 条边；删任一边会非连通，加任一边会成环
生成森林 非连通无向图 各连通分量的生成树组成的森林 每个分量各取一棵生成树 $n$ 个顶点、$k$ 个连通分量时有 $n-k$ 条边
最小生成树 带权无向连通图 权值总和最小的生成树 MST、权值和最小 图不连通时只能求最小生成森林
Kruskal 带权无向图 按边权从小到大选不成环的边 排序、并查集、避环 适合稀疏图；选够 $n-1$ 条边停止
Prim 带权无向图 从树集合出发，每次接入最近的外部顶点 lowCost、点扩张 邻接矩阵朴素实现适合稠密图
边的权 无向图、有向图 边或弧上标注的数值 权值含义由题目给定 权值可表示距离、费用、概率、时间等不同含义
带权图，也称网 无向图、有向图 边或弧带有权值的图 权值、网 图结构相同，权值含义不同，最优问题可能不同
带权路径长度 带权图 路径上所有边或弧的权值之和 沿路径求和 不等于边数；边数是普通路径长度
单源最短路径 无向图、有向图、带权图 从一个源点到其他各顶点的最短路径 源点、dist、prev 无权图可用 BFS；非负权图常用 Dijkstra
每对顶点间最短路径 有向图、无向图、带权图 求任意两个顶点之间的最短路径 all-pairs、dist[][]、path[][] Floyd 可处理负权边，但不能处理负权回路
负权回路 带权图 回路上边权之和为负 反复绕行、距离不断变小 存在可达负权回路时，最短路径可能没有定义
邻接矩阵 无向图、有向图、带权图 用 $\lvert V\rvert\times \lvert V\rvert$ 矩阵表示顶点之间是否有边、弧或权值 行列都对应顶点编号 空间只和顶点数有关，不和实际边数有关
无向图邻接矩阵 无向图 $A[i][j]=A[j][i]$，矩阵关于主对角线对称 对称矩阵 可以只存主对角线加上三角或下三角
有向图邻接矩阵 有向图 $A[i][j]$ 表示从 $v_i$ 到 $v_j$ 的弧 行看出边，列看入边 $A[i][j]=1$ 不代表 $A[j][i]=1$
邻接表 无向图、有向图、带权图 顶点表顺序存储顶点，每个顶点后接链表保存邻接点 顺序 + 链式 表示方式不唯一
无向图邻接表 无向图 每条边在两个端点的链表中各存一次 边结点数 $2\lvert E\rvert$ 顶点度等于对应链表长度
有向图邻接表 有向图 每条弧只存到起点的链表中，默认保存出边 弧结点数 $\lvert E\rvert$ 出度方便，入度和入边需要扫描整个邻接表
十字链表 有向图 一个弧结点同时挂入弧尾的出边链和弧头的入边链 firstin、firstout 只用于有向图
邻接多重表 无向图 一条无向边只存一个边结点，同时挂入两个端点的边链 iLink、jLink 只用于无向图
广度优先搜索 无向图、有向图 借助队列从起点按层扩展访问顶点 队列、visited、先发现先扩展 非连通图需要从未访问顶点继续调用 BFS
广度优先生成树 连通图的 BFS 过程 由 BFS 第一次发现新顶点时经过的边构成 发现边、层次结构 邻接表顺序不唯一时，生成树也可能不唯一
广度优先生成森林 非连通图的完整 BFS 过程 各连通分量的 BFS 生成树组成的森林 多次调用 BFS 无向图中 BFS 调用次数等于连通分量数
深度优先搜索 无向图、有向图 沿未访问邻接点不断深入，走不动再回退 递归、调用栈、回退 非连通图需要从未访问顶点继续调用 DFS
深度优先生成树 连通图的 DFS 过程 由 DFS 第一次递归进入新顶点时经过的边构成 递归树边 邻接表顺序不唯一时，生成树也可能不唯一
深度优先生成森林 非连通图的完整 DFS 过程 各连通分量的 DFS 生成树组成的森林 多次调用 DFS 无向图中 DFS 调用次数等于连通分量数
DFS 判有向图环 有向图 若搜索边指向当前递归栈中的顶点，则存在有向环 VISITING、回边 不能把指向 DONE 顶点误判为环
遍历与连通性 无向图、有向图 通过 BFS/DFS 的覆盖范围和启动次数分析连通关系 visited、调用次数、可达范围 无向图调用次数等于连通分量数；有向图要按弧方向具体分析
DAG 有向图 不存在有向环的有向图 Directed Acyclic Graph、无环 有拓扑序列当且仅当该有向图是 DAG
表达式 DAG 表达式结构 合并重复操作数和重复子表达式后的表达式图 公共子表达式、复用结点 通常按结构相同合并，不自动做复杂代数化简
AOV 网 有向无环图 顶点表示活动，边表示活动先后约束 Activity On Vertex、前驱、后继 必须无环；有环表示依赖关系矛盾
拓扑排序 DAG、AOV 网 使每条路径起点都排在终点前面的顶点序列 入度为 0、删除出边 序列不唯一；图有环时不存在拓扑序列
逆拓扑排序 DAG、AOV 网 从后继约束末端开始输出的反向拓扑序列 出度为 0、DFS 退栈前输出 指向 DONE 顶点不是环
AOE 网 带权有向无环图 顶点表示事件，边表示活动，边权表示活动耗时 Activity On Edge、源点、汇点 用于求关键路径；活动在边上，不在顶点上
关键路径 AOE 网 从源点到汇点的最长路径 ve、vl、e、l、d 关键路径长度是工程最短完成时间
关键活动 AOE 网 时间余量为 0 的活动 d(i)=l(i)-e(i)=0 关键活动延期会导致工期延期
稀疏图 无向图、有向图 边数较少的图 $\lvert E\rvert<\lvert V\rvert\log\lvert V\rvert$ 这是经验界限，不是绝对定义
稠密图 无向图、有向图 边数较多的图 接近完全图边数上界 常和邻接矩阵适用性一起考
树 无向图 连通且无回路的无向图 连通、无环 树作为数据结构的完整概念见 tree-basic-concepts
森林 无向图 若干棵互不相交的树组成 每个连通分量是一棵树 $n$ 个顶点、$k$ 个分量时有 $n-k$ 条边
有向树 有向图 一个顶点入度为 0，其余顶点入度均为 1 唯一根、其余入度 1 只看入度条件时仍要注意题目是否默认连通或可达
无向完全图 无向图 任意两个不同顶点之间都有边 两两相连 边数是 $C_n^2$，不是 $n(n-1)$
有向完全图 有向图 任意两个不同顶点之间都有方向相反的两条弧 两两双向相连 弧数是 $2C_n^2=n(n-1)$

常用公式

图类型 公式或结论 含义
无向图 $\sum_{i=1}^{n} TD(v_i)=2e$ 每条边被两个端点各统计一次
有向图 $\sum_{i=1}^{n} ID(v_i)=\sum_{i=1}^{n} OD(v_i)=e$ 每条弧贡献一个入度、一个出度
有向图 $\sum_{i=1}^{n} TD(v_i)=2e$ 总度数仍等于弧数的 $2$ 倍
连通无向图 最少 $n-1$ 条边 极少边连通形态是树
非连通无向图 最多 $C_{n-1}^{2}$ 条边 保留一个孤立顶点，其余顶点构成完全图
强连通有向图 最少 $n$ 条弧 极少弧强连通形态是有向回路
无向完全图 $C_n^2=\frac{n(n-1)}{2}$ 条边 任意两个不同顶点之间都有一条边
有向完全图 $2C_n^2=n(n-1)$ 条弧 任意两个不同顶点之间都有方向相反的两条弧
生成树 $n-1$ 条边 覆盖连通图全部顶点且边数最少
生成森林 $n-k$ 条边 $n$ 个顶点、$k$ 个连通分量，每个分量各取生成树
邻接矩阵空间 $O(\lvert V\rvert^2)$ 只由顶点数决定，适合稠密图
邻接矩阵求度 $O(\lvert V\rvert)$ 无向图扫一行或一列；有向图入度扫列、出度扫行
邻接矩阵路径计数 $A^n[i][j]$ 是 $i$ 到 $j$ 长度为 $n$ 的路径条数 只适用于 $0/1$ 邻接矩阵的路径计数语境
邻接表空间 无向图 $O(\lvert V\rvert+2\lvert E\rvert)$；有向图 $O(\lvert V\rvert+\lvert E\rvert)$ 适合稀疏图
邻接表求度 无向图度、有向图出度都等于对应链表长度 有向图入度需要扫描所有链表
十字链表空间 $O(\lvert V\rvert+\lvert E\rvert)$ 入边和出边都能沿链直接找
邻接多重表空间 $O(\lvert V\rvert+\lvert E\rvert)$ 每条无向边只保存一个边结点
BFS 空间 $O(\lvert V\rvert)$ 辅助队列和 visited 数组
BFS 邻接矩阵时间 $O(\lvert V\rvert^2)$ 每个顶点都要扫描一整行邻接矩阵
BFS 邻接表时间 $O(\lvert V\rvert+\lvert E\rvert)$ 所有顶点访问一次，所有边或弧被扫描有限次
无向图完整 BFS 调用次数 连通分量数 连通图只需调用一次
DFS 空间 最坏 $O(\lvert V\rvert)$ 主要来自递归调用栈和 visited 数组
DFS 邻接矩阵时间 $O(\lvert V\rvert^2)$ 每个顶点都要扫描一整行邻接矩阵
DFS 邻接表时间 $O(\lvert V\rvert+\lvert E\rvert)$ 所有顶点访问一次，所有边或弧被扫描有限次
无向图完整 DFS 调用次数 连通分量数 连通图只需调用一次
BFS 求无权图单源最短路径 邻接表 $O(\lvert V\rvert+\lvert E\rvert)$，邻接矩阵 $O(\lvert V\rvert^2)$ 第一次访问某顶点时得到最短边数
Dijkstra $O(\lvert V\rvert^2)$ 邻接矩阵朴素实现；要求无负权边
Floyd $O(\lvert V\rvert^3)$ 求每对顶点间最短路径；可有负权边但不能有负权回路
SPFA 最坏 $O(\lvert V\rvert\lvert E\rvert)$ 可处理负权边，并可检测从源点可达的负权回路
拓扑排序 邻接表 $O(\lvert V\rvert+\lvert E\rvert)$ 每个顶点输出一次，每条边导致一次入度更新
邻接矩阵拓扑排序 $O(\lvert V\rvert^2)$ 删除顶点出边时需要扫描矩阵行或列
稀疏图 常用经验：$\lvert E\rvert<\lvert V\rvert\log\lvert V\rvert$ 边数较少
图论中的树 $n-1$ 条边 连通且无回路的无向图
有向树 一个顶点入度为 $0$，其余顶点入度均为 $1$ 图中的有向树判定
无向图回路判定 若 $\lvert E\rvert>n-1$，则一定有回路 常见边数结论
快速区分

“连通”只看能否走到；“强连通”看两个方向能否都走到；“分量”强调已经是极大范围；“生成”通常强调覆盖原图全部顶点；“权”强调边或弧上的数值含义。