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

【导读】华图事业单位考试网同步华图教育发布：2015年国家电网考试备考计算机之数据结构与算法(13)，详细信息请阅读下文！事业单位考试考情政策解读，点击领取备考资料，更多事业单位考试资讯请关注(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有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。

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

　

　　如果使用的是邻接表存储结构，其DFSTraverse函数的代码几乎是相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下。

　　

手机端链接：https://m.sydw.huatu.com/2014/0927/1070701.html

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

（编辑：admin）