是指用一个一位数组存储图中的顶点信息，用一个二位数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二位数组称为邻接矩阵。空间复杂度为 O ( n 2 ) O(n^2) O(n2)，其中为图的顶点数。
有向图，无向图和网的邻接矩阵：
注意：无向图的邻接矩阵是对称矩阵，对规模大的邻接矩阵可以采用压缩存储。
图的邻接矩阵存储结构定义如下：
#define MaxVertexNum 100 //顶点最大值为100
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
int vexnum, arcnum; //图的当前顶点数和弧数
}MGraph;
图的邻接矩阵存储的特点：
- 对于无向图，邻接矩阵的第 i i i行（或者第 i i i列）非零元素（或者非 ∞ infty ∞元素）的个数正好是顶点 i i i的度
- 对于有向图，邻接矩阵的第 i i i行非零元素（或者非 ∞ infty ∞元素）的个数正好是顶点 i i i的出度；第 i i i列非零元素（或者非 ∞ infty ∞元素）的个数正好是顶点 i i i的入度
- 设图 G G G的邻接矩阵为 A A A，则 A n A^n An的元素 A n [ i ] [ j ] A^n[i][j] An[i][j]表示由顶点 i i i到顶点 j j j的长度为 n n n的路径的数目
我们知道一个图的邻接矩阵存储的空间复杂度为 O ( n 2 ) O(n^2) O(n2)，当这个图为稀疏图时，使用邻接矩阵存储将会浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储的方法，可以很大程度上减少空间的浪费。
所谓邻接表就是指图中
G
G
G的每个顶点
v
i
v_i
vi建立一个单链表，第
i
i
i 个单链表中的结点表示依附于顶点
v
i
v_i
vi的边（对于有向图则是以顶点
v
i
v_i
vi为尾的弧），这个单链表就称为顶点
v
i
v_i
vi的边表（对于有向图则称为出边表）。边表的头指针和顶点的信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点；
如下图：
顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstac）构成；边表（邻接表）结点由邻接点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成；
图的邻接表存储结构定义如下：
#define MaxVerrexNum 100//顶点最大值为100
typedef char VertexType;//顶点的数据类型
typedef struct ArcNode {//边表结点
int adjvex;//该弧所指向的顶点的位置
struct ArcNode* next;//指向下一条弧的指针
//InfoType info;//网的权值
}ArcNode;
typedef struct VNode {//顶点表结点
VertexType data;//顶点信息
ArcNode* frist;//指向第一条依附该顶点的弧的指针
}Vnode, AdjList[MaxVerrexNum];
typedef struct {
AdjList vertices;//邻接表
int vexnum, arcnum;//图的顶点数和弧数
}ALGraph
注意：在邻接表中，给定一个顶点，很容易找到它的所有邻边，但是却很难确定两个顶点之间是否存在边。
十字链表是有向图的一种链式存储结构，邻接多重表是无向图的另一种存储结构
