在图的邻接矩阵表示法中,我们用一个二维数组,即邻接矩阵,来刻画顶点之间的连接关系。对于无向图,邻接矩阵是对称的,意味着如果顶点i与顶点j相连,那么矩阵的第i行第j列和第j行第i列都会有一个非零元素,这表示它们之间的边是双向的。对于有向图,矩阵则可能不对称,只表示从一个顶点到另一个顶点的单向连接。
邻接矩阵的定义通常包括一个元素w_ij,它表示边上的权值,如果不存在边则用计算机允许的较大数值(如∞)来表示。在实际应用中,邻接矩阵的存储结构可以简化,例如,当仅表示边的存在与否时,边的权值可以简化为0和1的枚举类型。对于大型图,为了节省空间,可以采用压缩存储方式。
空间复杂度方面,邻接矩阵表示法的存储量是O(n^2),其中n为顶点数。创建无向网络的算法首先需要输入顶点数和边数,然后逐个读取顶点信息和边的连接情况,最后填充邻接矩阵。这个过程的时间复杂度为O(n+n^2+e),其中e是边的数量。
例如,图G5和G6的邻接矩阵A1和A2,以及带权图的A3和A4,都是通过这个算法生成的。用户可以自定义最大顶点数、顶点类型和边的权值类型,用MGragh结构体来存储这些信息。在简单的场景下,可以省略顶点表和相关参数,直接使用二维数组作为邻接矩阵。
逻辑结构分为两部分:V和E的集合。因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵