Olverae Assets

1 图怎么塞进内存

图（graph）就是一堆「顶点」加上连接它们的「边」；要让程序处理它，得先把这些边存进数组——两种主流存法是邻接矩阵和邻接表。

把它想成城市与航线图：城市是顶点，航线是边。要记下"哪两座城市之间有航线"，可以用一张大棋盘表格（邻接矩阵：行 i 列 j 打勾表示 i 到 j 有边），也可以给每座城市挂一张小清单（邻接表：city i 的清单上列出它能直飞到的城市）。同一张图，两种记法。

同一张三角形图（0-1-2 两两相连），左、中、右是它的三种样子。下一节你将逐条加边，同时看图、矩阵、表三者一起长出来——亲眼确认它们说的是同一件事。

2 逐条加边，看三种存法一起长出来

先看代码里这两种表示怎么声明，再点 ▶ 一条条加边——左边图上的边亮起，中间矩阵对应格子翻成 1，右边清单挂上邻居，三者同步。

两种表示在 C 里怎么声明

V 个顶点编号 0…V−1。下面分别是邻接矩阵和邻接表的最小写法。

// ① 邻接矩阵：一个 V×V 的二维数组，adj[i][j]=1 表示 i→j 有边
int adj[V][V] = {0};            // 全部初始化为 0（没有边）

// ② 邻接表：每个顶点挂一条链表，存它的邻居
struct node { int v; struct node *next; };
struct node *adjList[V] = {NULL};   // V 条空链表

无向图的每条边 u–v 要"双向"记录：矩阵里 adj[u][v] 和 adj[v][u] 都置 1；表里 u 的链上挂 v、v 的链上也挂 u。漏掉对称的一半，是图题最常见的 bug——下面的演示会反复强调这一点。

加边构建：图 ↔ 矩阵 ↔ 表

图（顶点 + 边）

邻接矩阵（行 i 列 j）

邻接表（每个顶点的邻居链）

提示

点 ▶ 演示加边：每条边会让图上的线亮起、矩阵的两个对称格子翻 1、表里两个顶点各挂一个邻居。

5

顶点数 V

0

已加边数 E

0

矩阵中 1 的个数

3 矩阵 vs 邻接表，到底怎么选

两种表示没有绝对优劣，全看图稠密还是稀疏、你常做什么操作。下面三张卡片是考试的命门。

① 空间：O(V²) vs O(V+E)

一句话：矩阵不管有没有边都占 V×V；表只为真实存在的边花钱。图越稀疏，表越省。

邻接矩阵：固定 O(V²)。邻接表：O(V + E)。当 E 远小于 V²（稀疏图，如社交网络、路网），表能省下大量空间；当图很稠密（E 接近 V²），两者差不多，矩阵反而更简单。

② 查询快慢：看你问什么

一句话：问"i、j 之间有边吗"矩阵 O(1) 最快；问"i 的所有邻居"表更划算。

查单条边 adj[i][j]：矩阵 O(1)，表要扫 i 的链 O(degree)。遍历邻居：表只走真实邻居 O(degree)，矩阵要扫一整行 O(V)。BFS/DFS 主要做"遍历邻居"，所以稀疏图常用表。

③ 有向 / 无向与度数

一句话：无向图矩阵沿对角线对称；有向图分"出度"和"入度"。

无向：adj[u][v]==adj[v][u]，矩阵关于对角线对称；顶点的度 = 它那一行 1 的个数。有向：adj[u][v]=1 只表示 u→v。出度 = 第 u 行的 1 的个数；入度 = 第 v 列的 1 的个数。

无向(对称): 有向(不对称): 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0

4 四个一写就错的实现坑（点一下看）

下面 4 个是写图题最常翻车的坑——无向图漏对称、出入度数错列、下标越界、把 V 和 E 搞混。点击卡片看运行效果。

① 无向图漏写对称边

只写 adj[u][v]=1，忘了 adj[v][u]=1

② 出度/入度数错方向

入度该数"列"，却去数了"行"

③ 顶点下标越界

顶点编号 0..V-1，访问 adj[V][..] 越界

④ 把 V 和 E 搞混

用边数 E 开矩阵 / 循环，行列对不上

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 自测

这 5 题正对 2521 图题套路：空间、邻居遍历代价、对称性、出入度、稠密 vs 稀疏选型。最后到练习系统亲手建矩阵、算度数。

去做例题：图 · 构建无向邻接矩阵

去做例题

Graph Representation (adjacency matrix/list)

图的表示