1．图的邻接矩阵表示法
在图的邻接矩阵表示法中：
① 用邻接矩阵表示顶点间的相邻关系
② 用一个顺序表来存储顶点信息
2．图的邻接矩阵(Adacency Matrix)
设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
【例】下图中无向图G
5
和有向图G
6
的邻接矩阵分别为A
l
和A
2
。
从图的邻接矩阵表示法中可以得到如下结论： （1）对于n个顶点的无向图，有A（i，i）=0，1≤i≤n。
（2）无向图的邻接矩阵是对称的，即A（i，j）=A（j，i），1≤i≤n，1≤j≤n。
（3）有向图的邻接矩阵不一定对称的。因此用邻接矩阵来表示一个具有n个顶点的有向图时需要n
2
个单位来存储邻接矩阵；对有n个顶点的无向图则需存入上（下）三角形，故只需n（n+1）/2个单位。
（4）无向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（v
i
）。
（5）有向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度OD（v
i
）[或入度ID（v
i
）]。
3．网（带权值的图）的邻接矩阵
若G是网络，则邻接矩阵可定义为：
其中：
w
ij
表示边上的权值；
∞表示一个计算机允许的、大于所有边上权值的数。
【例】下面(a)是一个带权图，（b）是对应的邻接矩阵的存储结构
（a）带权图
（b）邻接矩阵
4．邻接矩阵的图类
const int MaxVertices=10;
const int MaxWeight=32767;
class AdjMWGraph
{ private:
int Vertices[10]; //顶点信息的数组
int Edge[MaxVertices][MaxVertices]; //边的权值信息的矩阵
int numE; //当前的边数
int numV; //当前的顶点数
public: ………; //公有函数
private: ………; //私有函数
}
注意：
① 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）。
② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。
③ 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。
④ 邻接矩阵表示法的空间复杂度S(n)=0(n
2
)。
