邻接矩阵

建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。
设图A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：
image.png
**

无向图的邻接矩阵表示

**
image.png

分析**1：无向图的邻接矩阵是对称的；**因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可
所需存储元素个数是
邻接矩阵 - 图3
分析2：无向图，顶点i 的度＝邻接矩阵 第 i 行 (列)中非零（或者非邻接矩阵 - 图4)元素的个数；
特别：完全图的邻接矩阵中，对角元素为0，其余1

有向图的邻接矩阵表示

image.png
分析1：有向图的邻接矩阵可能是不对称的。
分析2：顶点的**出度邻接矩阵 - 图6=第i行元素之和
 顶点的**入度邻接矩阵 - 图7=第i**列**元素之和
顶点的度=第i行元素之和+第i列元素之和

**

网（即有权图）的邻接矩阵表示法

image.png
image.png
**

优点**：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。
缺点：n个顶点需要nn个单元存储边;空间效率为O(n2)。 对稀疏图而言尤其浪费空间**。*