一、邻接矩阵
图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设图G 有n 个顶点，则邻接矩阵A 是一个n ∗ n 的方阵，定义为:
下图是一个无向图和它的邻接矩阵：
可以看出:
- 无向图的邻接矩阵一定是一个对称矩阵(即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的)。因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
- 对于无向图，邻接矩阵的第i 行(或第i 列)非零元素(或非元素)的个数正好是第i 个顶点的度
- 求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，A[i][j]为 1就是邻接点。
