数据结构——图(图的存储及基本操作)

---

前言

1. 邻接矩阵法(图的顺序存储结构)
   1.1 无向图邻接矩阵算法
   1.2 有向图邻接矩阵算法
2. 邻接表法(图的一种链式存储结构)

---

一、邻接矩阵法（顺序存储）

1. 定义：用一个一维数组存储顶点，一个二维数组存储边的信息（各顶点之间邻接关系），n个顶点是n×n的矩阵，若(vi,vj)属于E ，则A[i][j]=1，否则等于0；对于带权图，则邻接矩阵中对应项存放着该边对应的权值，若顶点vi和vj不相连，则用∞来表示这两个顶点之间不存在边【是表示顶点之间相邻关系的矩阵。所谓两顶点的相邻关系即它们之间有边相连。】
2. 注意
   ①无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储
   ②邻接矩阵表示法的空间复杂的为O(n^2)，其中n为图的定点数|V|