用C++实现图的邻接矩阵并剖析其时间复杂度详解

    小编在上篇简书简单介绍了有关图的一些基本的性质，那如何去存储图呢？首先，图的顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。图的邻接矩阵的存储方式是用两个数组来实现的，一个一维数组存储顶点信息，一个二维数组存储线（无向图）或弧（有向图）的信息。

    （1）无向图的邻接矩阵

    假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

    无向图邻接矩阵的特点为：主对角线一定为0且为对称矩阵

    求无向图顶点的度就是求邻接矩阵第i行或第j列非零元素的个数

    判断顶点i和j是否存在边就是判断Arc[i][j]是否为1

    求顶点i的所有邻接点就是将数组中第i行重新扫描一遍，若Arc[i][j]为1，则顶点j为顶点i的邻接点

    （2）有向图的邻接矩阵

    假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

    有向图的邻接矩阵不一定对称，比如完全有向图。

    有向图中，顶点i的出度为第i行元素之和，入度为第j列元素之和【这里的有向图中是指边还未添加权值，默认为1】

    代码如下：

    接下来我们简单分析下该算法的时间复杂度。

    从上述的代码截图中，我们可以发现程序执行步骤最多的为CreateMGraph这个函数，而该函数程序执行步骤最多为3个for循环语句。

    第一个for循环语句循环n次【n为输入的顶点个数】，第二次for循环语句循环n的平方次，第三次for循环语句循环e次【e为图中的边数】，在这里我们先忽略其它赋值语句执行的次数，得到的执行步数为n^2+n+e。当n越来越大时，n^2将开始占据主导地位，其它项目也可以忽略，因此我们就可以把代表程序总执行步数的记为O(n^2)。