2018年国家电网考试备考计算机之数据结构与算法(10)

【导读】华图事业单位考试网同步华图教育发布：2018年国家电网考试备考计算机之数据结构与算法(10)，详细信息请阅读下文！事业单位考试考情政策解读，点击领取备考资料，更多事业单位考试资讯请关注(htshiyedanwei)公众号，欢迎加入事业单位招聘考试交流群：  参加刷题、模考、领取备考资料，考编路上不孤单！

1.1 邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(邻接矩阵)存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

看一个实例，下图左就是一个无向图。

从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。

从这个矩阵中，很容易知道图中的信息。

(1)要判断任意两顶点是否有边无边就很容易了;

(2)要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;

(3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点;

而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。

若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

这里的wij表示(vi,vj)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面左图就是一个有向网图，右图就是它的邻接矩阵

。

那么邻接矩阵是如何实现图的创建的呢?代码如下。

手机端链接：https://m.sydw.huatu.com/2017/1102/1601766.html

官方微信号

官方微博号