入门：从 G=(V,E) 到有向无向、稠密稀疏
基于通用数据结构概念 · 核于 2026-07
速查
- 定义：图
G = (V, E)，V是顶点集（vertex，n=|V| 个），E是边集（edge，m=|E| 条）。顶点当实体、边当关系，是表达「任意二元关系」的通用模型。 - 有向 vs 无向：边有方向叫有向图（digraph），边
(u,v)与(v,u)不同；边无方向叫无向图，边{u,v}两端等价、可双向通行。无向图的一条边在有向图里相当于两条方向相反的边。 - 带权 vs 无权：边上带数值（距离/费用/容量）叫带权图（weighted），否则是无权图（unweighted）——后者常把「有边」视为权重 1。
- 稠密 vs 稀疏：当边数
m接近n²（完全图n(n-1)/2）为稠密图；当m远小于n²（如m = O(n)或O(n log n)）为稀疏图。稀疏/稠密直接决定表示法选型。 - 度：与某顶点关联的边数叫度（degree）；有向图分入度（指向它的边数）与出度（它指出的边数），度 = 入度 + 出度。无向图所有顶点度数之和 = 2m。
- 自环与重边：
a[v][v]这种连到自己的边叫自环（self-loop）；两顶点间多条相同的边叫重边/平行边（parallel edges）；二者都没有的图叫简单图。 - 路径 / 环 / 连通：顶点序列
v0→v1→...→vk且相邻有边叫路径；首尾相同的路径叫环/回路；无向图任意两顶点都有路径叫连通图，否则分为多个连通分量。有向图对应概念是强连通。 - 树是特殊的图：树 = 连通 + 无环 + 无向的图（n 个顶点恰好 n-1 条边）。所以树能用的图表示法（邻接表）图都能用，反之不行（图可能有环）。
- 邻接矩阵预告：
n×n数组a[i][j]=1（或权重）表示有边，查边 O(1)、空间 O(n²)——见三种表示法。 - 邻接表预告：每个顶点挂一条邻居链表，空间 O(V+E)、查边 O(度)——稀疏图与 BFS/DFS/Dijkstra 标配。
- 选型一句话：稠密选矩阵、稀疏选表、按边遍历选边集数组（Kruskal/Bellman-Ford）。
- 进阶顺序：三种表示法 → 工程实现与选型 → 参考。
一、图是什么：V、E 与二元关系
图 G = (V, E) 由两部分组成：顶点集 V（vertex，通常 n=|V| 个，编号 0..n-1）和边集 E（edge，m=|E| 条）。一条边连接两个顶点，表达它们之间的「关系」。
无向图 G=(V,E)，V={0,1,2,3}，E={{0,1},{1,2},{2,3},{0,3}}
0 ─── 1
│ │
3 ─── 2图的强大在于抽象层级高：把实体映射成顶点、把关系映射成边，就能用一套模型与算法处理看似无关的问题。
| 问题 | 顶点 | 边 |
|---|---|---|
| 社交网络 | 人 | 好友关系（无向）/ 关注关系（有向） |
| 地图导航 | 地点 | 道路（带权=距离/时间） |
| 网页搜索 | 网页 | 超链接（有向） |
| 任务调度 | 任务 | 依赖「A 必须先于 B」（有向） |
| 电网 | 元器件 | 导线（带权=电流容量） |
正因为图是关系数据的「最大公约数」，先把图存好（本叶），才有后续的 BFS/DFS/Dijkstra/拓扑排序（图算法叶）。
二、有向图 vs 无向图
- 无向图（undirected graph）：边没有方向，
{u, v}表示 u、v 之间有连接，可双向通行。如「好友关系」（互为好友）、无向道路。 - 有向图（directed graph / digraph）：边有方向，
(u, v)表示「从 u 指向 v」，与(v, u)是两条不同的边。如「关注关系」（A 关注 B 不代表 B 关注 A）、网页超链接。
无向图的一条边 {u,v} 在逻辑上等价于有向图的两条边 (u,v) 和 (v,u)——这一点在存储上直接体现：无向图用邻接矩阵时矩阵对称（a[u][v]=a[v][u]=1），用邻接表时两个方向的链表都要各存一次。
三、带权图 vs 无权图
- 无权图（unweighted）：边只表示「有/无」关系，矩阵存 0/1，邻接表存邻居编号。无权图的最短路就是边数最少的路径（BFS 可解）。
- 带权图（weighted）：每条边附带一个数值，常代表距离、时间、费用、容量等。矩阵
a[u][v]直接存权重（无边常存∞）；邻接表存[邻居, 权重]二元组或对象。
带权与否决定了算法选型：无权最短路用 BFS（O(V+E)），带权最短路用 Dijkstra（O((V+E) log V)）或 Bellman-Ford（O(VE)）——这些都属于图算法叶，本叶只关心「权重往哪里存」。
四、稠密图 vs 稀疏图
这是选型最关键的判据。设顶点数 n、边数 m：
- 完全图：任意两顶点间都有边，无向完全图有
n(n-1)/2条边，有向完全图有n(n-1)条边。 - 稠密图（dense）：
m接近n²（即接近完全图）。 - 稀疏图（sparse）：
m远小于n²，典型如m = O(n)或O(n log n)。
现实中的图大多是稀疏的：社交网每人几百好友 vs 上亿用户（m ≈ n）；网页图每个页面几十出链 vs 数十亿页面；地图每个路口接几条路 vs 数百万路口。稀疏图必须用邻接表（空间 O(V+E)），否则邻接矩阵 O(n²) 会爆内存。稠密图（如运算优先关系、小规模完全图）用邻接矩阵更合适（查边 O(1)、且空间浪费小）。
五、度、入度与出度
顶点的**度（degree）**是与它关联的边数。有向图进一步细分：
- 入度（in-degree）：指向该顶点的边数（有多少边「射进来」）。
- 出度（out-degree）：从该顶点出发的边数（有多少边「射出去」）。
- 有向图顶点的度 = 入度 + 出度。
一个重要恒等式：无向图所有顶点的度数之和 = 2m（每条边贡献两端的度各一次）。由此可知度数为奇数的顶点个数必为偶数（握手定理）——这是判断「欧拉路径存在性」的基础。
在存储上，邻接矩阵某行的非零元素个数 = 该顶点的出度（有向）或度（无向）；邻接表某顶点链表长度 = 出度/度。拓扑排序（图算法叶）依赖「入度为 0 的顶点优先」，所以有向图常额外维护一个入度数组。
六、路径、环与连通分量
- 路径（path）：顶点序列
v0 → v1 → ... → vk，且相邻顶点v_{i} → v_{i+1}都有边。路径长度 = 边数（无权）或边权和（带权）。 - 简单路径：除首尾外顶点不重复的路径。
- 环 / 回路（cycle）：首尾顶点相同的路径（
v0 = vk）。含环的图叫有环图，不含环的叫无环图。 - DAG：有向无环图（Directed Acyclic Graph），是任务调度、依赖管理的标准模型，支持拓扑排序。
- 连通：无向图中两顶点间存在路径叫连通；整个图任意两点都连通叫连通图；否则图被分成若干连通分量（connected component）。
- 强连通（有向）：有向图中两顶点互相可达叫强连通；整个图任意两点互相可达叫强连通图。
这些概念是图算法（求最短路、判断环、找连通块、拓扑排序）的语言基础——本叶点到为止，深入在图算法叶。
七、树是特殊的图
树 = 连通 + 无环 + 无向的图。更精确地说：
- n 个顶点的连通无向图若恰好有 n-1 条边且无环，它就是一棵树。
- 反过来，一棵树就是一个满足上述条件的无向图。
所以树能用的图表示法（邻接表存父子关系、邻接矩阵存连接），图都能用；但图可能有环、可能不连通、可能有重边自环，这些是树没有的复杂性。换句话说，图是树的推广——掌握了图的表示，树的表示自然涵盖。
下一步
理解了图的基本概念（顶点/边、有向无向、稠密稀疏、度、连通）后，下一步是回答核心问题：怎么把这些顶点和边存进内存？ 见三种表示法——邻接矩阵、邻接表、边集数组的时空权衡。