图的存储

## 图的存储 一般情况下有三种存图的方式，分别是 邻接矩阵，邻接表，链式前向星。 ### 邻接矩阵 用 `mp[i][j]` 表示 两点之间的关系。 优点： + 可以快速查询一条边是否存在或者边权。 缺点： + 占用很大的空间，大部分情况下是不能用 邻接矩阵 的。 适用场景： + 点的数量较少。 + 需要快速查询一条边是否存在。 注意： + 千万不要因为点的数量太多而采用 二维map。 map 的查询效率 非常低下，用map虽然可以解决一些空间问题，但是会增加时间导致TLE。 ### 邻接表+链式前向星 两个存图思想是一致的，实现方式不大相同。我们可以把两种存图方式理解为一条链。链式前向星其实就是用数组模拟邻接表。这里简单介绍一下链式前向星的实现方法。 如图所示代表存储一个点的情况。  每一个变量的含义: ``` 图中变量的含义： u 代表起点的编号 cnt 代表边的编号 head[i] 代表以i为起点的最后一条边的编号 对边的信息的存储： struct edge { int to,v,nxt; } e[M]; to 表示这条边的终点 v 表示边权 nxt 表示这条边左边一条边的编号 ``` 代码长这样： ```cpp 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++ ``` 代码就很好写了： ```cpp 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`。结束的条件也很好想，其实就是边的编号存在。 代码： ```cpp for(int i=head[u];i;i=e[i].nxt) ``` 优点： + 时间和空间上都是很优秀的数据结构，能应对大多数图论题 缺点： + 不能直接查询一条边的信息 适用场景： + 大部分场景都适用 注意： + 有的题目需要存双向边（无向边）。题目中的条件如果给的边的条数最大是 M 条。那么 e 数组一定要开成 M 的 2 倍。