邻接矩阵adjMatrix[i][j] 表示顶点 i 和顶点 j 之间是否存在连接关系(1 表示有关联 0表示无关联)

可以表示成一个n*n的矩阵形式

这种表示方式有以下优点

• 方便检查一对顶点之间是否存在边
• 方便查找任意顶点的所有邻接点
• 方便计算任意顶点的度

对于有向图 行对应的是出度 列对应的是入度

行和为出度总数 列和为入度总数

例如这张图

容易得到 顶点1,2之间有关联 1,3之间有关联 1,4之间有关联

(2,4),(3,4),(2,5),(4,5)也有关联 可以由此画出图结构

容易知道对于无向图来说 其邻接矩阵是对称的 因为两个顶点会共用一条边

下面是主要代码实现过程:

构建图结构体 包含以下结构

• 存放顶点信息数组
• 表示顶点之间关系的邻接矩阵二维数组
• 顶点数量
• 边的数量

初始化图 两次申请空间 第一次是申请二维数组顶点数目个空间 第二次是对每个数组继续申请顶点数目个内存空间 这样就申请好了邻接矩阵的空间

i=j时为adj[i][j]=0 否则为未连接状态INF

这是打印图函数 比较简单不赘述

输入图的各方面信息 并用Locate函数找到两关联顶点的对应下标 为其连接的边添加权值

释放内存……

邻接矩阵虽然简单直观 但缺点也很明显!!!

1.对于稀疏图浪费大量空间在顶点表示上(很多顶点之间无连接但仍存储了位置信息)

2.从图中删除一个顶点，不仅需要移动顶点数组中的顶点位置，而且还要删除该顶点在邻接矩阵中对应的行和列，引起行列的移动,十分不方便

删除V3需要删除,移动大量元素 可见其繁琐

所以还要继续学习关于图的表示方法 数据结构我爱你!!!