图的几种存储方式

 第一次给501的同学们讲课，所以好好准备了一下。

本博客大多为自己整理的，错误或不妥当之处还望各位多多指正！谢谢了！

本博客代码所用例题为SDUT OJ 图的存储专题的第一题-------> https://acm.sdut.edu.cn/onlinejudge3/problems/3116

废话不多说，直接上目录

图的几种存储结构：

1、邻接矩阵

2、邻接表

3、链式前向星

4、C++中vector的邻接表实现（补充）

（一）邻接矩阵 邻接矩阵是表示顶点之间相邻关系的矩阵。

邻接矩阵的好处：

（1）直观、简单、好理解

（2）方便检查任意一对定点间是否存在边

（3）方便找任一顶点的所有“邻接点”（有边直接相连的顶点）

（4）方便计算任一顶点的度

对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。

对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。

邻接矩阵的局限性：时间复杂度O(n^2），空间复杂度O(n^2)

（1）浪费空间。对于稠密图还是很合算的。

                          但是对于稀疏图（点很多而边很少）有大量无效元素。

（2）浪费时间。要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。

bb这么多，我们直接来以OJ此专题第一题为例

这题二维数组map不能用int，会爆内存，bool可以自己百度，简而言之就是用于逻辑判断，只有true和false两种情况。

bool类型在存储二值变量，或者说只有真假时，更具优势，因为只有0和1即false和true，省空间

（int型的0和1都是4字节，bool都是1字节）

#include#include#includebool map[5001][5001];int main(){ int n,m; int u,v; int q; while(~scanf("%d %d",&n,&m)) { memset(map,false,sizeof(map)); while(m--) { scanf("%d %d",&u,&v); map[u][v]=true; } scanf("%d",&q); while(q--) { scanf("%d %d",&u,&v); if(map[u][v]) { printf("Yes "); }else { printf("No "); } } } return 0;} （二）邻接表 图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。

在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。

邻接表的特点如下：

（1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的