第1个回答 2022-07-18
上一节，学习了 图的基本概念或术语 ，本节学习图的存储结构： 邻接矩阵
邻接矩阵
又称数组表示法，图示形如坐标轴，一般的做法是通过 定点表Vexs 记录顶点信息， 邻接矩阵arcs (二维数组)记录各顶点的关系，图示形如坐标轴。在邻接矩阵中， 顶点i和顶点j直接存在边或者出度，则记作1，否作0
无向图对应的邻接矩阵如下
有向图对应的邻接矩阵如下
网的邻接矩阵如下（有权记值，无权记#）
创建
有向网的连接矩阵
根据顶点表初始化邻接矩阵
如上图所示，顶点表为['v1','v2','v3','v4','v5']，记作vexs
根据顶点表的个数，初始化邻接矩阵，每个坐标点的默认值置为#表示无穷大
构造邻接矩阵
获取边数，如图为6，记作arcNum
获取权值及权值对应的边，记作weights
构造矩阵
无向网
对于无向网来说，其实就一个地方不一样：在构造矩阵的最后一步，还有对其对称点进行权重赋
值
优缺点
优点：直观、一眼可看出"邻接点"、"顶点的度"、"是否存在边"
缺点：增删操作不易、存在冗余元素，浪费空间（完全图除外）、统计边总数不易，浪费时间（n个顶点e条边的无向图创建的时间为O(n+ +e),而对邻接矩阵的初始化则需要O( )）