图论基础——图的概念

有向图 (Directed Graph) (也叫 Digraph)：边是有方向的。
- 比如，在微博上，A 关注了 B，但 B 不一定关注 A。这条边是从 A 指向 B 的。
- 我们用 <A, B> 来表示一条从 A 指向 B 的有向边。A 是起点，B 是终点。
- 有向图示例：

2. 无权图 vs. 带权图

无权图 (Unweighted Graph) ：边没有任何附加信息，或者说边的 “成本” 或 “长度” 都是 1。
- 比如，简单的朋友关系图，只表示 “是” 或 “不是” 朋友。
带权图 (Weighted Graph) ：每条边都有一个数值，叫做权重（Weight）或权值。
- 比如，地图上的高速公路，边上的权重可以是距离（如 100 公里）或通行时间（如 2 小时）。
- 在社交网络中，边的权重可以表示亲密程度。
- 带权图示例：

3. 完全图 vs. 稠密图 vs. 稀疏图

完全图 (Complete graph) : 各点间都有边相连。
- 无向图中的任意两个顶点之间都有一条边。
- 有向图中任意两个顶点之间都有方向相反的两条边。
- 完全图示例：

稠密图 (Dense graph) : 绝大多数顶点之间都存在边。
- 边的数量接近顶点数量的平方 ( |E| ≈ |V|² )，顶点之间连接紧密，绝大多数顶点之间存在直接边。
- 比如，完全图就是一个典型的稠密图。
稀疏图 (Sparse graph) : 顶点之间的边数量较少。
- 边的数量远小于顶点数量的平方 ( |E| << |V|² )，甚至可能满足 |E| < |V| · log2 |V| 。顶点之间连接较少，可能存在顶点没有任何边相连。
- 比如，树结构就是典型的稀疏图。

4. 其他图

零图 : 图的边集可以是空的，边的集合为空的图（即没有边的图）叫做零图。
平凡图（树） : 仅有一个顶点的图称平凡图，平凡图也叫平凡树。

四、图的基本术语

1. 邻接

邻接 (Adjacency)：如果两个顶点之间有一条边相连，那么这两个顶点就是相邻的。
- 在无向图中，如果 (A, B) 是一条边，则 A 与 B 相邻，B 也与 A 相邻。
- 在有向图中，如果 <A, B> 是一条边，则 A 是 B 的前驱（Predecessor），B 是 A 的后继（Successor）。我们说 A 邻接到 B，或者 B 邻接于 A。

2. 阶、度、奇点与偶点

阶 (Order): 一个图的阶是指图中顶点的个数。
度 (Degree)：一个顶点的度是指与它相连的边的数量。
- 在无向图中，顶点 A 的度就是与它相邻的顶点的个数。
- 在有向图中，度分为入度（In-degree）和出度（Out-degree）。
  - 入度：指向该顶点的边的数量。
  - 出度：从该顶点出发的边的数量
奇点 (Odd vertex): 度数为奇数的点。
偶点 (Even vertex): 度数为偶数的点。

3. 子图

子图 (Subgraph): 标准定义是设一个图 G = (V, E) 和图 G' = (V', E')，若V'是V的子集，E'是E的子集，则称G'是G的子图。
说人话就是一个图中包含的小图叫这个图的子图。当然，这并不严谨，但是有助于你理解：

上图中标橙色的图就是整个图的子图。

4. 路径、回路（环）、自环（吊环）

路径 (Path)：是指由顶点和边交替组成的有限序列，满足：序列中每相邻两个顶点通过一条边连接；除起点和终点可能相同外，其余顶点均不重复。这种路径也叫 简单路径 (Simple path)。若路径的起点与终点相同，且其余顶点不重复，则称为 简单回路 (Simple curcuit) 或 简单环 (Simple cycle)。
可以把图想象成一张地图：顶点就是地图上的城市，边就是连接城市的道路。那么 “路径” 就好比从一个城市到另一个城市的一条路线 —— 比如从城市 A 出发，经过城市 B、C，最后到城市 D，这条 “A→B→C→D” 的路线就是一条路径。
这里的关键是：除了起点（A）和终点（D）可能是同一个城市（比如绕一圈回到 A），中间经过的城市（B、C）不能重复走，不然就不算这种 “路径” 啦。
路径长度 (Path length): 指该路径上边的数量，在例子中就是城市A到城市D的道路有多远。
回路（环）(circuit (cycle)): 起点和终点相同的路径，样例中就是从城市A出发，经过其他城市又回到了城市A，那么这条路就叫回路。

示例：上图中从点c到点d存在一条路径为（c — e — a — b — d）其路径长度为4；路径（a — b — e — a）为一条简单回路，其路径长度为3；路径（a — b — e — f — b）不是一条简单路径，因为存在着一条从点b回到点b的一条回路。
自环（吊环）(Self-loop): 是指一条特殊的边，其两个端点（起点和终点）为同一个顶点，即该边仅连接单个顶点自身，是图中边的一种特殊形式。就是一条连接同一个点的边。

该图中，点d就存在一条连接自己和自己的自环。

5. 连通图与连通分量

连通图 (Connected graph): 在无向图中，若任意两个不同顶点之间都存在至少一条路径，则称该图为连通图。对于有向图，需满足任意两顶点间双向都有路径（称为 强连通图 (Strongly connected graph)，单向有路径则为 弱连通图 (Weakly connected graph)，通常未特别说明时，连通图默认指无向图的情况。
连通分量 (Connected Component): 对于非连通的无向图，其极大连通子图称为连通分量。“极大” 意味着该子图无法再添加原图中的其他顶点或边（即图内能挑出的最大子图），仍保持连通性；每个连通分量本身是连通图，且不同连通分量之间没有任何路径相连。一个连通图的连通分量就是其自身。
- 强连通分量 (Strongly Connected Component, SCC)
  强连通分量是针对有向图的概念，指有向图中的极大子图。该子图内任意两个不同顶点 u 和 v，都存在从 u 到 v 的有向路径，同时也存在从 v 到 u 的有向路径；“极大” 意味着无法向该子图中添加原图的其他顶点，仍保持这种双向连通性。
- 弱连通分量 (Weakly Connected Component, WCC)
  弱连通分量同样针对有向图，指将有向图中所有有向边视为无向边后，得到的连通分量。也就是说，不考虑边的方向时，子图内任意两个顶点间存在路径，但考虑方向时，可能不存在双向甚至单向路径；其 “极大” 性与连通分量的定义一致，无法再添加原图顶点保持连通。
还是通俗易懂的讲解：

1. 连通图
依旧用 “城市 - 道路” 类比：连通图就像一整片互通的城市网络。比如京津冀地区的城市，北京、天津、石家庄、保定等，不管从哪个城市出发，都能通过高速公路、铁路等 “道路”，直接或间接到达其他任意一个城市，没有孤立的、到不了的城市，这整个网络就是连通图。

2. 连通分量
如果把视野放大到全国，不考虑飞机（只看地面道路），情况就不一样了。比如大陆的城市网络是一个连通分量 —— 任意两个大陆城市能互通；中国台湾的城市网络是另一个连通分量 —— 岛内城市能互通，但和大陆城市没有地面道路相连；中国海南的城市网络也是一个独立的连通分量。这三个相互没有直接道路相连、内部连通的 “城市群”，就是整个全国地面道路图的三个连通分量。简单说，连通分量就是非连通图里 “各自抱团、互不相连” 的连通部分。

3. 强连通分量
这次的道路都是单行道（对应有向边）。强连通分量就像一个 “双向互通的城市圈”：比如城市 A、B、C 之间，A 有单行道到 B，B 有单行道到 C，C 又有单行道到 A，同时 A 和 C、B 和 A 之间也有直接的单行道。不管从哪个城市出发，都能通过单行道绕到其他任意城市 —— 这个 “A、B、C 组成的圈子” 就是一个强连通分量。

4. 弱连通分量
依旧是单行道的城市网络，但弱连通分量不 “较真” 单行道的方向。比如城市 D、E、F 之间，D 有单行道到 E，E 有单行道到 F，但 F 没有到 E 或 D 的路，D 也没有到 F 的直接路。如果忽略单行道的方向（把它们当成普通双向路），D、E、F 是连在一起的，能从一个到另一个；但考虑方向时，可能出现 “能去不能回” 的情况 —— 这个 “忽略方向后连通的 D、E、F” 就是一个弱连通分量。

总结：强连通是 “双向都能到”，弱连通是 “不管方向能到就行”，两者都只针对有向图。

6. 权和网

在一个图中，每条边可以标上某种特殊含义的值（如长度、费用、时间等），这个数值就被称为权 (Weight)，而边上带有权的图也叫做网 (Net)。

7. 树和森林

树（Tree）:树是一种特殊的无向图，满足两个核心条件：一是连通性，任意两个顶点间存在且仅存在一条路径；二是无回路性，图中不存在任何闭合的路径（回路 / 环）。
森林（Forest）:森林是由若干棵互不连通的树组成的无向图，核心属性是 “无回路”。森林中的每一棵独立的树都是一个连通分量。
还是用 “城市 - 道路” 类比：树就像一个省会城市（根顶点），连接着几个地级市，每个地级市又连接着各自的县城，县城再连接乡镇 —— 所有城市都能通过道路互通，但没有任何一条 “绕圈的路”（即没有从县城连接到省会城市的路）。

而且这个网络有个特点：少一条路就会有城市孤立（比如删了省会到某地级市的路，那片地级市和县城就通不了了）；多一条路就会出现绕圈（比如给两个县城直接修条路，就形成了 “省会→A 市→县城 1→县城 2→A 市” 的环路），就是定义中的连通性和无回路性。

森林就像多个独立的城市网络，各城市网之间没有道路连接。比如北方有一个树状城市网络（省会 + 地级市 + 县城），南方有另一个树状城市网络（另一个省会 + 其下属城市），这两个网络内部都无环路、各自连通，但南北两个网络之间没有任何道路 —— 这两个独立的 “树” 合起来就是一片森林。

8. 二分图

二分图（Bipartite Graph）又称二部图、双分图，是一种特殊的无向图。其顶点集可被划分为两个互不相交的非空子集（通常称为 “partitions” 或 “部”），且图中所有边的两个端点都分别属于这两个不同子集 —— 即同一子集内的顶点之间不存在任何边，所有边均 “跨子集” 连接。二分图示例：
二分图的核心判定性质：一个无向图是二分图，当且仅当它不包含任何长度为奇数的回路（奇数环）。
通俗易懂的讲解
还是用 “城市 - 道路” 来类比：二分图就像把所有城市分成了两个 “阵营”，比如 “东部城市” 和 “西部城市”。
这里的规则很严格：所有连接城市的道路（边），只能是 “东部城市” 和 “西部城市” 之间的通道，同一阵营内部的城市之间没有任何道路。举个具体例子：假设东部城市有 A、B，西部城市有 C、D。可以有 A-C、A-D、B-C 这样的道路，但绝对不能有 A-B（同东部）、C-D（同西部）这样的道路。另外还有个小特点：如果这个图里有 “绕圈的路”（回路），比如 A-C-B-D-A，这个圈子的长度（边的数量）一定是偶数；要是出现 3 条边、5 条边这样的奇数长度回路，那它就不是二分图了。
判断一个图是否为二分图，一般用 “染色法” 进行判断。用两种颜色对所有顶点进行染色，要求一条边所连接的两个相邻顶点的颜色不同。染色结束后，如果能实现所有相邻顶点的颜色都不相同，它就是二分图。如下图示：

无向图 G 为二分图的充分必要条件是，G 至少有两个顶点，且其所有回路的长度均为偶数。

9. 有向无环图

有向无环图 (DAG): 字面意思，即一个不存在环和自环的有向图，在未来的图论学习中有着重要的地位。

五、图的基本公式、定理（重点）

若一个图中有n个顶点和e条边，则该图所有顶点的度桶边数e满足： $e=\frac{1}{2}\sum_{i=1}^{n}D(v_{i})$ 。说人话就是全部顶点的度数之和等于所有边数的2倍。这很容易理解，因为一条边连接两个顶点，所以每条边度数都为2。
有向图中所有顶点的入度之和等于所有顶点的出度之和。因为每一条有向边都连接着两个点，一个点出、一个点入，所以每条有向边都有着一入一出，入度和就等于出度和了。
任意一个无向图一定有偶数个（或0个）奇点。因为每条无向边会给图增加 2个度数，总度数一定是偶数。奇数个奇数相加是奇数，没法凑出总度数的偶数，所以奇点只能成对出现（偶数个）或没有（0 个）。
一个无向完全图中有 $\frac{n(n-1)}{2}$ 条边，有向完全图中有 $n(n-1)$ 条边。因为 n 个结点都分别会与其他 n-1 个结点相连接，而无向图中每两个结点只需要连接一次，所以在所有边中，仅剩下一半，而有向图所有点都要互相连接，所以不用除以二。
n个顶点的无向连通图最少有n - 1条边。说白了就是：想让所有顶点（比如看成 “人”）都能互相 “碰到”（不用直接碰，通过别人传话也行，这就是 “连通”），最省事儿、不浪费一条边的方式，就是把它们 “串成一串” 或者 “拉成树杈”—— 比如 3 个人只要 2 条线（A 拉 B、B 拉 C），4 个人只要 3 条线（A 拉 B、B 拉 C、C 拉 D），刚好比人数少 1 条。
n个顶点的强连通图最少有n条边。简单说：强连通图得让每个顶点都能顺着箭头，找到其他所有顶点（有向图的要求，比无向连通严），最省边的方式就是把所有顶点排成一个 “环”——n 个顶点刚好需要 n 条边，少一条都不行。
树的顶点数 n 与边数 m 满足固定关系：m = n - 1，且任意添加一条边都会形成唯一回路，任意删除一条边都会导致图不连通。森林的顶点数 n 与边数 m 满足 m = n - k（k 为森林中树的棵数）。当森林中只有一棵树时，森林就退化为树。
树的情况 - 边数关系（m = n - 1）：树是“最省边”的连通图，没有环。可以想象把n个顶点“串成一条链”，比如3个顶点用2条边（A-B、B-C），4个顶点用3条边（A-B、B-C、C-D），刚好比顶点数少1，所以m = n - 1。 - 加边成唯一回路：树原本没环，加一条边后，这两个顶点原本就有唯一路径，加上新边就会形成一个环，且只有这一个环（因为原路径唯一）。删边变不连通：树的边都是“桥梁”，删一条边就会把树分成两个独立的部分，所以图就不连通了。森林的情况森林是多棵互不连通的树（比如几棵单独的树，彼此之间没边）。假设森林里有k棵树，每棵树的顶点数分别是n₁、n₂…nₖ，总顶点数n = n₁ + n₂ + … + nₖ。每棵树的边数是顶点数 - 1，所以总边数m = (n₁ - 1) + (n₂ - 1) + … + (nₖ - 1) = n - k（k是树的棵数）。
一个无向图是二分图，当且仅当图中不存在奇环。这很好理解：
如果是二分图，就没奇环：二分图的点能分成两拨，边只在两拨之间连。要是有个奇数条边的环（比如三角形），你给它涂色时，转一圈会发现有两个相邻点颜色一样，矛盾了，所以奇环不能存在。
如果没奇环，就是二分图：随便选个点涂颜色 1，它的邻居涂颜色 2，邻居的邻居涂颜色 1…… 因为没奇环，涂的时候不会有邻居颜色撞车的情况，最后自然分成两拨，就是二分图。

本文到这里就结束啦，作者花了很多时间呢，希望大家多多支持！

下一篇：图论基础——图的存储

乐奇 Rokid 开放社区

更多推荐

用径向菜单完成 macOS 窗口管理的 Loop 上手指引

周三上午，你要同时摆好代码、终端、文档三个窗口。别急着来回拖拽，先按住触发键，把鼠标指向屏幕右侧，窗口就落进了右半屏。这就是 macOS 窗口管理工具 Loop，它用径向菜单和预览窗口，替掉了繁琐的拖边操作。## 🚀 5 步装好 Loop 并完成第一次窗口调整**第 1 步：安装**用 Homebrew 一行装好：```brew install loop```也可以克隆源

乐奇 Rokid 开放社区

memU 的 Claude Code bridging 任务是一个定时作业，它从裸的、非交互的环境里调用 `claude -p` 来挖掘最近的 Claude Code 会话并写入记忆。这意味着在注册这个定时任务之前，必须先有一个能独立解析、能 headless 认证的 `claude` CLI——[BRIDGING_TASK.md](https://link.gitcode.com/i/85f1a

乐奇 Rokid 开放社区

Plate 模板 CI 修复实战：Registry 辅助依赖与 RSC 客户端边界的完整排查指南

本文以 Plate 仓库中 [2026-04-06-fix-template-ci-registry-helper-deps.md](https://link.gitcode.com/i/4790f561dac586c6b2e17e1cadaa2911) 这份修复计划为骨架，完整复盘一次"模板 CI 构建失败"的真实排查过程：注册表（registry）UI/插件重构引入了一批辅助文件后，`plat