邻接矩阵表示了结点之间的邻接关系。一个拥有n个结点的图G的邻接矩阵是一个n阶方阵A(G)，其元素为：
　　　　　　　　　　　　

　　图6.6.1给出了一个图以及其邻接矩阵表示。
　　　　
　　　　　　　　图6.6.1 一个图G和它的邻接矩阵表示

　　邻接矩阵既可以表示有向图，又可以表示无向图，还可以表示混合图。它能表示自环，但不能表示重边。无向图的邻接矩阵是对称矩阵。

　　为了能用邻接矩阵表示重边，可以把邻接矩阵的每个元素的值定义为两个结点间边的个数。

　　把每个元素的值定义为结点间边的权重（两个结点之间没有边用无穷来表示，结点与自己之间的权重记为0），则邻接矩阵可以表示赋权图。这种邻接矩阵称为加权邻接矩阵。