Question

图--存储结构（邻接矩阵）

Answer 1

    上一节，学习了 图的基本概念或术语 ，本节学习图的存储结构： 邻接矩阵

邻接矩阵

    又称数组表示法，图示形如坐标轴，一般的做法是通过 定点表Vexs 记录顶点信息， 邻接矩阵arcs (二维数组)记录各顶点的关系，图示形如坐标轴。在邻接矩阵中， 顶点i和顶点j直接存在边或者出度，则记作1，否作0

         无向图对应的邻接矩阵如下

            有向图对应的邻接矩阵如下

            网的邻接矩阵如下（有权记值，无权记#）

创建

     有向网的连接矩阵

         根据顶点表初始化邻接矩阵

            如上图所示，顶点表为['v1','v2','v3','v4','v5']，记作vexs

             根据顶点表的个数，初始化邻接矩阵，每个坐标点的默认值置为#表示无穷大

         构造邻接矩阵

             获取边数，如图为6，记作arcNum

             获取权值及权值对应的边，记作weights

             构造矩阵

     无向网

            对于无向网来说，其实就一个地方不一样：在构造矩阵的最后一步，还有对其对称点进行权重赋

        值

优缺点

     优点：直观、一眼可看出"邻接点"、"顶点的度"、"是否存在边"

     缺点：增删操作不易、存在冗余元素，浪费空间（完全图除外）、统计边总数不易，浪费时间（n个顶点e条边的无向图创建的时间为O(n+ +e),而对邻接矩阵的初始化则需要O( )）