前言
在没进入大学前，我对图的理解仅仅局限在几何，而在进入大学接触了离散数学的图论后，算是刷新了一次我的观念。所谓图（graph），是图论中基本的数学对象，包括一些顶点，和连接顶点的边，图论中的边只是表示的顶点连接情况，用直线或曲线表示均可。图可以分为有向图和无向图，有向图中的边是有方向的，而无向图的边是双向连通的。
在算法竞赛中有一类称为图论题的题目，涉及到对图的处理，在解决它们之前，我们首先得把图的逻辑结构通过某种形式存储起来，这个过程我们称为存图。
邻接矩阵
谈到存储图的逻辑结构，最朴素的想法是用一个二维数组 mp [ ] [ ] 来存储两个点之间的连接情况。假如从顶点 u 到顶点 v 之间有一条边，则令 mp [u] [v] = 1 。这种存图方式称为邻接矩阵，例如上面的那个有向图与无向图的邻接矩阵是：
这是没有边权的情况，对于有边权（可以理解为边的长度）的图，其实只要把对应的1换成边权即可：
邻接矩阵的代码很好实现，代码如下：
// 最大顶点数
const int maxn = 1000;
// 定义邻接矩阵
int mp[maxn][maxn];
// 增加边(这是双向有边权图的写法，其他类型的图写法类似)
inline void add(int u, int v, int w)
{
mp[u][v] = w;
mp[v][u] = w;
} 优点：
- 简单易学，代码易写，操作方便
- 对于确定的边，可以在 O(1) 的时间复杂度内实现添加，修改，删除的操作
- 易处理重边，我们可以随时覆盖掉重边，以实现存储最新的边
缺点：
- 对于 n 个点的图，我们必须开一个 $n^2$ 大小的二维数组，空间复杂度高达 $O(n^2)$ ，如果点的数量到了10000以上就可以不考虑了
- 如果图是一个稀疏图(即边很少的图)，那么将会有大量的数组空间被浪费掉，所以一般我们只在稠密图会考虑用这个
- 对于不确定边的查询，往往需要遍历完数组的一行或一列，查询效率一般
事实上，在上面那个图，我们也可以发现二维数组中有许多个0，但我们其实更关注那些确实存在的边。我们希望，可以跳过这些0，直达有边的地方，就像下面这样，这个就是邻接表的雏形
邻接表
邻接表在三种常用的存图方式中属于较为中庸和普遍的存图方式了，缺点不致命，优点不明显。邻接矩阵可以看作有 n 个一维数组，第 i 个数组的第 j 个值存储的是顶点 i 到顶点 j 的边的边权。而在邻接表中，我们相当于换成了有 n 个不定长的链表，此时第 i 个链表的第 j 个值表示的是以 i 为起点的第 j 条边的边权。
因为替换成链表后，数组下标的含义发生了变化，所以我们需要用一个结构体来同时存储边的终点(相当于邻接矩阵的第二个下表)和边权：
// 定义边结点(如果没有边权可以不使用结构体，只存储终点即可)
struct Edge
{
int to,w;
};那么，文章中的第三张图中的图的邻接表如下：
换句话说，邻接表存储每个顶点能够到达哪些顶点。注意这里链表的顺序是无关紧要的，取决于存图的顺序。接下来我们来实现邻接表，在算法竞赛上手写链表这种动态数据结构，又费时又容易写错，所以我们一般用 vector 代替链表
// 最大顶点数
const int maxn = 1000;
// 定义边结点(如果没有边权可以不使用结构体，只存储终点即可)
struct Edge
{
int to,w;
};
// 邻接表
vector<Edge> edges[maxn];
// 加边（无向图只需要调用两次即可）
inline void add(int from, int to, int w)
{
Edge e = {to, w};
edges[from].push_back(e); //向vector的最后添加一条边
}遍历图时用通常遍历数组的方法即可，注意vector的size()方法可以返回其包含元素的个数
// 遍历2号点能到达的所有点
for (int i = 0; i < edges[2].size(); ++i)
printf("%d ", edges[2][i].to); 优点：
- 容易理解，相比起邻接矩阵，其实就是把空余的元素去掉了
- 代码易写不复杂，也不容易写错
- 内存利用率高，V 个点 E 条边的图，邻接矩阵空间复杂度为 $O(V^2)$ ，邻接矩阵仅为 $O(V+E)$ ， 能较好地适用于稠密图和稀疏图
- 对不确定边的操作效率高，比如要遍历从某点出发的所有边，不会像邻接矩阵一样可能会遍历到不存在的边
缺点
- 判重比较麻烦，必须遍历已有的边，无法直接判断，一般情况下邻接表会存储重边
- 对于以确定的边操作效率一般，比如要查询或修改 i->j 的边，只能遍历链表去寻找
链式前向星
链式前向星这种存图方式的数据结构主要是边集数组，顾名思义，图的边是用数组来存储的。当然想要完美表示图结构，光有一个边集数组还不够，还要有一个 head 数组存储指向每一个点的第一条边的“指针”。而每一条边的结构体都需要存储接下来一条边的“指针”，这样就能够像类似邻接表一样方便遍历每一个点的所有边了。
根据上面这张图可以发现，链式前向星其实是另一种邻接表的实现思路，它使用数组来模拟了链表，只不过每次加边都是在头部插入。因为STL常数大，所以平时竞赛中较多使用的是这种方式，对比起前两种，链式前向星则多了一个 cnt 变量为每条边赋予了编号
// 最大顶点数
const int maxn = 1000;
// 最大边数
const int maxm = 1000;
// 边集数组
struct Edge
{
int to, w, nxt; // 边的终点，边权，同一起点下一条边的编号
}edges[maxn];
int head[maxn], cnt; // cnt为当前边的编号
// 添加边
inline void add(int from, int to, int w)
{
edges[++cnt].w = w; //新增一条编号为cnt+1的边，边权为w
edges[cnt].to = to; //该边的终点为to
edges[cnt].nxt = head[from]; //把下一条边，设置为当前起点的第一条边
head[from] = cnt; //该边成为当前起点新的第一条边
}遍历链式前向星的时候稍微复杂一点，类似于链表的遍历，例如：
//打印2号顶点能到达的所有点
for (int e = head[2]; e != 0; e = edges[e].nxt)
printf("%d ", edges[e].to);优点：
- 内存利用率高，相比起vector实现的邻接表而言，链式前向星可以准确开辟最多边数情况下的内存，vector 的动态变化则有爆内存的风险(每次都是倍增)
- 对不确定的边的操作效率不错，不会遍历到不存在的边
缺点：
- 代码稍微复杂，不是那么直观易懂（建议可以画图模拟加边的过程）
- 重边不好处理，只能通过遍历判重
- 对已确定的边的操作效率一般，不能通过两点马上确定边，只能遍历
总结
- 对于邻接矩阵，由于内存消耗的局限性，它的使用范围比较狭窄(顶点<10000)，几乎只能在简单图论题目见到
- 邻接表是最常见的一种，绝大多数情况下采用 vector 来实现，大部分的图论题目都能使用该存图方式
- 链式前向星是一种邻接表的特殊实现，在邻接表存图不能使用时可以使用，几乎可用于全部图论的题目
参考资料
版权属于：PCsky
本文链接：http://hyouka.club/index.php/archives/135/
转载时须注明出处及本声明