小编在上篇简书简单介绍了有关图的一些基本的性质，那如何去存储图呢？首先，图的顶点之间的关系是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】
代码如下：
C++实现邻接矩阵
运行截图
接下来我们简单分析下该算法的时间复杂度。
从上述的代码截图中，我们可以发现程序执行步骤最多的为CreateMGraph这个函数，而该函数程序执行步骤最多为3个for循环语句。
for循环
第一个for循环语句循环n次【n为输入的顶点个数】，第二次for循环语句循环n的平方次，第三次for循环语句循环e次【e为图中的边数】，在这里我们先忽略其它赋值语句执行的次数，得到的执行步数为n^2+n+e。当n越来越大时，n^2将开始占据主导地位，其它项目也可以忽略，因此我们就可以把代表程序总执行步数的记为O(n^2)。
网友评论