2020-02-10 19:39:32 新疆公务员考试网 //xj.huatu.com/ 文章来源:新疆华图
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)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值,也就是一个不可能的极限值。下面左图就是一个有向网图,右图就是它的邻接矩阵
。
那么邻接矩阵是如何实现图的创建的呢?代码如下。
——推荐阅读——
招考公告——2022新疆事业单位报考公告
试题资料——2022新疆事业单位相关考题
考试技巧——事业单位备考技巧
职位查询——新疆事业单位职位库
笔试课程——事业单位好课程 备战事考有方法
以上为本文的全部内容,由新疆公务员考试网提供,希望对考生有所帮助!更多新疆公务员招考信息,请加新疆公务员考试交流群,及关注新疆公务员考试招考资讯/新疆人事考试网。
(编辑:新疆华图)贴心微信客服
新疆华图公众号
10万+
阅读量150w+
粉丝1000+
点赞数