Elian's blog page

边的权、带权图与带权路径长度在图中，边或弧不仅可以表示“有没有关系”，还可以标上一个数值来表示关系的强弱、代价或收益。 边的权在一个图中，每条边都可以标上具有某种含义的数值，这个数值称为该边的权值。 权值不是固定语义，题目会给定它代表什么。解题时先读清“权值表示什么”，再判断要最短、最小、最大还是最优。 带权图，也称网边上带有权值的图称为带权图，也称网。 无向图可以带权，有向图也可以带权： 无向带权图：边 $(u,v)$ 有权值。 有向带权图：弧 $\langle u,v\rangle$ 有权值，方向仍然有效。 带权路径长度当图是带权图时，一条路径上所有边或弧的权值之和，称为该路径的带权路径长度。 Example 例如路径 $P\to G\to R\to Y$若三条边的权值分别是 $50,40,40$，则这条路径的带权路径长度为：$$50+40+40=130$$

最小生成树最小生成树（Minimum Spanning Tree, MST）讨论的是：在一个带权无向连通图中，既要让所有顶点连通，又要让选中边的总代价尽可能低。 什么是最小生成树设带权无向连通图为 $G=(V,E)$，$R$ 为 $G$ 的所有生成树的集合。对任意生成树 $T$，它的权值是 $T$ 中所有边权值之和： $$w(T)=\sum_{e\in T}w(e)$$ 若某棵生成树 $T$ 满足： $$w(T)=\min_{T_i\in R}w(T_i)$$ 则 $T$ 称为 $G$ 的最小生成树，也称最小代价树。 MST 的对象 最小生成树通常只讨论带权无向连通图。“带权”决定有代价可比较；“无向”决定边没有方向限制；“连通”决定存在覆盖全部顶点的一棵生成树。 MST 必须同时满足什么 条件 说明 覆盖全部顶点 不能只连接一部分顶点 连通 任意两个顶点之间都有路径 无环 有环就能删去环上的某条边并仍保持连通，不是生成树的最简形态 边数为...

强连通分量的常见求法有 Tarjan 和 Kosaraju。Tarjan 更适合理解代码实现，Kosaraju 更适合手算 SCC 个数。 TarjanTarjan 算法可以在线性时间内求出有向图的强连通分量。它的核心是 DFS 时间戳 dfn、追溯值 low 和一个维护当前搜索路径的栈。 dfn 与 low 数组 含义 dfn[u] 顶点 u 第一次被 DFS 访问到的时间戳 low[u] 从 u 出发，沿 DFS 树边向下走，再通过一条返祖边或栈内边能回到的最小 dfn 直观理解： dfn 记录访问顺序； low 记录当前顶点所在搜索分支还能向前追溯到哪里； 当 dfn[u] == low[u] 时，u 是某个强连通分量在 DFS 树中的根。 栈的作用Tarjan 只把“已经访问但尚未确定所属 SCC”的顶点留在栈中。 遇到边 u -> v 时： 若 v 没访问过，先 DFS v，回来后用 low[v] 更新 low[u]； 若 v 仍在栈中，说明 u 能到达当前未完成的搜索路径上的某个点，用 dfn[v] 更新 low[u]； 若 v...

生成树与生成森林生成树讨论的是：在保持全部顶点连通的前提下，把边删到尽可能少。非连通图不能得到覆盖全图的一棵生成树，只能得到生成森林。 相关基础：子图与生成子图、连通性与连通分量。 生成树连通图的生成树是包含图中全部顶点的一个极小连通子图。 若图中有 $n$ 个顶点，则任意生成树都有： $$n-1$$ 条边。 生成树有两个等价的直观判断： 角度 说明 边尽可能少 去掉生成树中任意一条边，图都会变成非连通 无环 在生成树中加入原图里一条额外边，一定会形成回路 极小与极大 连通分量是“极大连通子图”：连通区域已经不能再扩大。生成树是“极小连通子图”：已经连通，但边已经少到不能再删。 生成森林非连通无向图没有覆盖全图的生成树。此时，对每个连通分量分别取一棵生成树，这些生成树合在一起称为生成森林。 若非连通图有 $n$ 个顶点、$k$ 个连通分量，则其生成森林共有： $$n-k$$ 条边。因为每个连通分量若有 $n_i$ 个顶点，其生成树有 $n_i-1$ 条边，总和为： $$\sum_{i=1}^{k}(n_i-1)=n-k$$

子图与生成子图子图描述“从原图中取出一部分结构”。取子图时，顶点和边不能随意拼接：一条边若被取出，它的两个端点也要在子图顶点集中。 子图的概念同时适用于无向图和有向图；区别只在于有向图取出的是带方向的弧，弧的方向也要与原图一致。 设有两个图： $$G=(V,E),\quad G’=(V’,E’)$$ 若满足： $$V’\subseteq V,\quad E’\subseteq E$$ 并且 $E’$ 中每条边或弧的端点都属于 $V’$，则称 $G’$ 是 $G$ 的子图。 子图不是任意点边组合从原图中随便挑几个点、几条边，不一定能构成子图。 关键检查： 顶点是否来自原图； 边或弧是否来自原图； 每条被选中的边或弧，其端点是否也被选入子图； 有向图中弧的方向也要与原图一致。 生成子图若子图 $G’$ 满足： $$V(G’)=V(G)$$ 则称 $G’$ 是 $G$ 的生成子图。 生成子图保留原图的全部顶点，但边可以只保留一部分。因此： 生成子图一定覆盖全部顶点； 生成子图不一定连通； 生成树...

完全图完全图强调“任意两个不同顶点之间都直接相连”。无向图和有向图的完全图计数不同，关键差别来自边是否有方向。 完全图给出了同顶点数图的边数上界，也常用于理解稀疏图与稠密图。 无向完全图在无向图中，若任意两个不同顶点之间都存在边，则称该图为无向完全图。 若顶点数为 $n$，则每两个顶点确定一条无向边，因此边数为： $$C_n^2=\frac{n(n-1)}{2}$$ 一般 $n$ 个顶点的无向图，边数范围为： $$0\le |E|\le C_n^2$$ 其中 $|E|=C_n^2$ 时就是无向完全图。 有向完全图在有向图中，若任意两个不同顶点之间都存在方向相反的两条弧，则称该图为有向完全图。 对任意两个不同顶点 $v_i$ 和 $v_j$，有向完全图同时包含： $$\langle v_i,v_j\rangle$$ $$\langle v_j,v_i\rangle$$ 若顶点数为 $n$，则每对不同顶点贡献两条方向相反的弧，因此弧数为： $$2C_n^2=n(n-1)$$ 一般 $n$ 个顶点的有向图，弧数范围为： $$0\le |E|\le...

图的关系概念速查表这一组概念都在描述“顶点与边/弧的关系”“顶点到顶点能否走到”或“从原图中取出怎样的结构”。复习时先分清：度看边数统计，路径看走法序列，连通性看可达范围，生成结构看保留哪些顶点和边。 概念 适用对象 一句话定义 判定关键词 易错点 度 $TD(v)$ 无向图、有向图 与顶点 $v$ 相关的边或弧的总数 “依附于该顶点” 有向图中 $TD(v)=ID(v)+OD(v)$ 入度 $ID(v)$ 有向图 以 $v$ 为终点的弧数 箭头指向 $v$ 只数进入的弧，不数出去的弧 出度 $OD(v)$ 有向图 以 $v$ 为起点的弧数 箭头从 $v$...

图的连通性与连通分量连通性讨论顶点之间是否“走得到”。无向图看是否有路径，有向图还要看两个方向是否都走得到。 相关概念可配合 图的关系概念速查表 复习。 无向图的连通与连通图在无向图中，若从顶点 $v$ 到顶点 $w$ 存在路径，则称 $v$ 和 $w$ 是连通的。 若图 $G$ 中任意两个顶点都是连通的，则称 $G$ 为连通图；否则称为非连通图。 对于 $n$ 个顶点的无向图： 若 $G$ 是连通图，则最少有 $n-1$ 条边（树）。 若 $G$ 是非连通图，则最多可能有 $C_{n-1}^{2}$ 条边。 非连通图最多边数的理解：为了让图仍然非连通，至少要有一个顶点与其余顶点不连通；其余 $n-1$ 个顶点内部最多构成无向完全图，因此最多有 $C_{n-1}^{2}$ 条边。 有向图的强连通与强连通图在有向图中，若从顶点 $v$ 到顶点 $w$ 有路径，并且从 $w$ 到 $v$ 也有路径，则称 $v$ 和 $w$ 是强连通的。 Warning 只有在有向图中才有强连通图这个概念。 若有向图中任何一对顶点都是强连通的，则称此图为强连通图。 对于 $n$...

图的路径与距离路径描述“能不能从一个顶点走到另一个顶点”，距离则在可达的基础上取最短路径长度。 相关概念可配合 图的关系概念速查表 复习。 路径顶点 $v_p$ 到顶点 $v_q$ 的一条路径，是一个顶点序列： $$v_p, v_{i_1}, v_{i_2}, \cdots, v_{i_m}, v_q$$ 序列中相邻顶点之间要有边或弧相连。 在无向图中，只要边存在，就可以沿边的两个方向理解连接关系。 在有向图中，路径要沿着弧的方向走；有边形状相连不等于路径一定存在。 回路、简单路径、简单回路 概念 判定方式 路径 相邻顶点之间都有边或方向正确的弧 回路，也称环 第一个顶点和最后一个顶点相同的路径 简单路径 顶点序列中顶点不重复出现 简单回路 除第一个和最后一个顶点相同外，其余顶点不重复出现 图中左侧例子： $A \to B \to D$ 是一条路径，长度为 $2$。 $A \to B \to C \to A$ 是一个回路。 $A \to B \to C$ 是简单路径。 $A \to B \to C \to A$...

图的顶点度顶点的度描述一个顶点与多少条边或弧相关，是图中最常考的局部数量关系之一。 相关概念可配合 图的关系概念速查表 复习。 无向图的度在无向图中，顶点 $v$ 的度是指依附于该顶点的边的条数，记作 $TD(v)$。 上图左侧中： 顶点 依附的边 度 $A$ $AB, AC$ $TD(A)=2$ $B$ $AB, BC, BD$ $TD(B)=3$ $C$ $AC, BC, CD$ $TD(C)=3$ $D$ $BD, CD$ $TD(D)=2$ 若无向图有 $n$ 个顶点、$e$ 条边，则： $$\sum_{i=1}^{n} TD(v_i)=2e$$ 原因很直接：每条无向边有两个端点，在统计所有顶点的度时，每条边都会被两个端点各统计一次。 有向图的入度、出度、度在有向图中，边有方向，需要分开统计： 名称 记号 含义 入度 $ID(v)$ 以顶点 $v$ 为终点的有向边数 出度 $OD(v)$ 以顶点 $v$...