北京事业单位考试

您当前位置:公务员考试网 > 北京人事考试网 > 北京事业单位考试 > 备考资料 > 2018国家电网考试备考计算机之数据结构与算法(8)

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

2018-03-09 14:00:45 事业单位考试网 http://bj.huatu.com/sydw/ 文章来源:北京华图

  【导读】华图事业单位考试网同步北京华图发布:2018国家电网考试备考计算机之数据结构与算法(8)--详细信息请阅读下文!更多资讯请关注北京华图微信公众号(bjhuatu),事业单位培训咨询电话:400-010-1568

  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)的时间。

(编辑:刘冉)
北京华图:bjhuatu
想考上公务员的人都关注了我们!
立即关注

10万+
阅读量
10w+
粉丝
10000+
点赞数

联系我们
微信二维码

北京华图教育官方微信

北京华图

北京市海淀区花园路7号新时代一层

北京华图宏阳教育文化发展股份有限公司分公司

客服热线:400-010-1568

网站:http://bj.huatu.com

  • 牡丹园校区
  • 西城校区
  • 朝阳校区
  • 顺义校区
  • 大兴校区
  • 昌平校区
  • 平谷校区
  • 房山校区

海淀区花园路7号新时代大厦一层

客服热线:400-010-1568

网站:http://bj.huatu.com

西城区阜成门万通新世界A座1211

客服热线:010-58463857

网站:http://bj.huatu.com

朝阳区定福庄北里一号院鲁班大厦809室

客服热线:010-59453600/57237009

网站:http://bj.huatu.com

顺义双兴北区10号楼底商(北城根路与光明北街交叉路口)

客服热线:010-57282681

网站:http://bj.huatu.com

大兴区金星西路绿地中央广场B座609室

客服热线:010-58463856

网站:http://bj.huatu.com

昌平区政府街4-3号特步专卖店二楼(昌平二中斜对面)

客服热线:010-57282680

网站:http://bj.huatu.com

平谷区建设街229号二层(平谷六中北路口往西50米)

客服热线:010-59146957

网站:http://bj.huatu.com

房山区良乡拱辰南大街荣鹏花园底商

客服热线:010-57428000

网站:http://bj.huatu.com