2018国家电网考试备考计算机之数据结构与算法(8)由北京事业单位考试网提供:更多关于2018国家电网考试,计算机数据结构与算法,事业单位考试网的内容请关注北京事业单位考试网!或关注北京华图微信公众号(bjhuatu),如有问题也可点击联系各校区。
6.图 (Graph)
图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。
1.图的存储结构
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)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值,也就是一个不可能的极限值。下面左图就是一个有向网图,右图就是它的邻接矩阵
那么邻接矩阵是如何实现图的创建的呢?代码如下。
从代码中可以得到,n个顶点和e条边的无向网图的创建,时间复杂度为O(n + n2 + e),其中对邻接矩阵Grc的初始化耗费了O(n2)的时间。
点击查看:北京事业单位招聘辅导课程
★事业单位公基高频1000题领取★
手机号: | ||
所属地区: | ||
——推荐阅读——
招考信息--北京事业单位招聘信息汇总|备考咨询
面授课程--事业单位笔试面授课程|面试面授课程
在线课程--事业单位笔试在线课程|面试在线课程
图书教材--事业单位笔试图书教材|面试图书教材
华图在线APP--全年模考|30W+题库|看视频 刷题
(编辑:刘然)贴心微信客服
微信公众号