4006-01-9999
登录

华图事业单位官网

您当前位置: 事业单位 > 备考 > 专业课辅导 > 2018年国家电网考试备考计算机之数据结构与算法(14)

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

2017-11-02 09:55:16 事业单位考试网 https://sydw.huatu.com/ 文章来源:华图教育

立即领取
专属客服答疑
在线模考
事业单位公众号

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

重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说,它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点,如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2,如上图圆圈2。对于顶点v1,它有一个入边顶点v2,所以它的firstin指向顶点v2的边表结点中headvex为1的结点,如上图圆圈3。

十字链表的好处就是因为把邻接表和逆邻接表整合在一起,这样既容易找到以v为尾的弧,也容易找到以v为头的弧,因而比较容易求得顶点的出度和入度。

而且除了结构复杂一点外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图应用中,十字链表是非常好的数据结构模型。

这里就介绍以上三种存储结构,除了第三种存储结构外,其他的两种存储结构比较简单。

二、图的遍历

图的遍历和树的遍历类似,希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫图的遍历。

对于图的遍历来说,如何避免因回路陷入死循环,就需要科学地设计遍历方案,通过有两种遍历次序方案:深度优先遍历和广度优先遍历。

2.1 深度优先遍历

深度优先遍历,也有称为深度优先搜索,简称DFS。其实,就像是一棵树的前序遍历。

它从图中某个结点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中的所有顶点都被访问到为止。

我们用邻接矩阵的方式,则代码如下所示。


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

官方微信号

官方微博号

事业单位考试推荐
热点考试
招考公告 职位表 报名时间 报名条件 报名入口
考试时间 缴费入口 考试科目 考试大纲 报考指导
准考证 成绩查询 资格复审 面试公告 工资待遇
实用备考
每日直播 时政周播 领资料包 试题资料 备考指导
图书购买 笔试课程 面试课程 网络课程 更多>>>
(编辑:admin)
推荐活动
联系方式
华图事业单位企微客服

事业单位微信

考情备考答疑
获得免费备考资料
华图事业单位官方微博二维码

事业单位微博号

关注微博号
领取更多备考福利

图书推荐

更多>
有报考疑惑?在线客服随时解惑

公告啥时候出?

报考问题解惑?报考条件?

报考岗位解惑   怎么备考?

冲刺资料领取?

事业单位