图的存储

· · 算法·理论

图的存储

一般情况下有三种存图的方式，分别是 邻接矩阵，邻接表，链式前向星。

邻接矩阵

用 mp[i][j] 表示 两点之间的关系。

优点：

缺点：

适用场景：

注意：

邻接表+链式前向星

两个存图思想是一致的，实现方式不大相同。我们可以把两种存图方式理解为一条链。链式前向星其实就是用数组模拟邻接表。这里简单介绍一下链式前向星的实现方法。

如图所示代表存储一个点的情况。

每一个变量的含义:

图中变量的含义：
u 代表起点的编号
cnt 代表边的编号
head[i]     代表以i为起点的最后一条边的编号

对边的信息的存储：
struct edge
{
    int to,v,nxt;
} e[M];
to 表示这条边的终点
v 表示边权
nxt 表示这条边左边一条边的编号

代码长这样：

struct edge
{
    int to,nxt;
} e[M];
int head[N],cnt;

如何加一条边？很显然要加在最右边（即最后一条边），那么此时这条边的各个信息如何变化呢？

对于e[++cnt].to和e[++cnt].v 显然是输入的内容
对于e[++cnt].nxt 从图中可以看出来是head[u]
对于head[u] 从图中可以看出来是cnt++

代码就很好写了：

void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].nxt=head[u];//cnt已经加过1了，所以这里直接用cnt即可 
    head[u]=cnt;
}

那如何遍历一条边呢？因为存图的结构是链式的，很显然我们从 head[u] 开始遍历，对于每一条边的下一条边，很显然就是 e[i].nxt。结束的条件也很好想，其实就是边的编号存在。

代码：

for(int i=head[u];i;i=e[i].nxt)

优点：

缺点：

适用场景：

注意：