图的存储必须要完整、准确的反映顶点集和边集的信息。采用不同的存储方式对程序的效率产生相当大的影响，所以要选取适合求解的问题

一、邻接矩阵（适用于稠密图）

如果题目给知”对称矩阵“ ，若不是”对称矩阵“，那么必然不可能是无向图

1.1定义

是指用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中边或弧的信息（即各顶点之间的邻接关系）

1.2通过邻接矩阵存储图

1.2.1结点数为n的图：

1.2.2 带权图：

1.3邻接矩阵的性质

空间复杂度: 0(|V|) —— 只和顶点数相关，和实际的边数无关

对称矩阵：n阶矩阵的元素满足aij = aji,(0<=j, j<=n)；从矩阵的左上角到右下角的主对角线为轴，右上角的元素与左下角对应的元素对应全都是相等的。

无向图的邻接矩阵一定是对称矩阵（并且唯一），因此，在存储时只需要存储上（或下三角）

1.4的路径数目的意义

若是 “平方”的意义

关于a12和a24的解释：

a12对应的是1（即第一行第二列），1说明从A->B有一条边
a24对应的是1（即第二行第四列），1说明从B->D有一条边
a12 乘 a24等于1（隐含的意思我们可以找到一条路径，从A->B->D 这一条路径是存在的）

关于a13和a34的解释：
a13对应的是0（即第一行第3列），0说明从A->C不存在路径
a34对应的是0（即第三行第4列），0说明从C->D不存在路径

关于A的平方[1][4]=1: 说明当A->D路径为2的时候，只能找到一条路径符合条件的；

若是 “立方”的意义

其实就是把平方在乘上原本的矩阵就可以成为三次方

解释：
取三次方的 “a14”为例子：
1·0意思是：A平方的的第一行第一列对应的是1，乘上A的第一行第四列
1·0意思是：1表示的是 从A->A长度为2的路径有1条
0的意思是从A->D长度为1的路径有0条
1·0=0，因此我们没办法把这两段路径凑齐来形成 A->D长度为3的路径
a14对应的是1（即第一行第二列），1说明从A->B有一条边

二、邻接表法（顺序+链式存储）

2.1存储思路

此前谈过孩子表示法，将结点存入数组，并对结点的孩子进行链式存储，不管有多少个孩子，也不会存在空间浪费问题，我们将这种数组与链表相结合的存储方法称为邻接表法

2.2存储方法

对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）

每个链表上附设一个表头结点：

1. 邻接点域(advex)：与顶点vi邻接的点在图中的位置
2. 链域(nextarc)：指示下一条边或弧的结点
3. 数据域（info）：存储和边或弧相关的信息，如权值等

头结点：

1. 数据域(data)：用于存储顶点vi的名或其他有关信息
2. 链域（firstarc）：指向链表中第一个结点之外

有向图与无向图的邻接实例：

2.3存储特点

三、十字链表（有向图）

3.1定义

十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧都有一个结点，对应于每个顶点也有一个结点

3.2十字链表性质

四、邻接多重表（无向图）

当要删除A与B相连的边的时候：

1. 首先删除结点
2. 可以看到接下来我们需要修改两个指针
3. 上面的指针是指向与A相邻的边，下面的指针是指向与B相邻的边
4. 删除A：则我们只需要在删除结点之前，顺着橙色方块，找到下一条边对应的是哪个结点即可
5. 删除B：结点也一样，我们只需要通过绿色块，找到与绿色块相邻的边即可，则让B指向她即可