华图事业单位官网
2014-09-27 15:14:50 事业单位考试网 https://sydw.huatu.com/ 文章来源:华图教育
【导读】华图事业单位考试网同步华图教育发布:2015年国家电网考试备考计算机之数据结构与算法(14),详细信息请阅读下文!事业单位考试考情政策解读,点击领取备考资料,更多事业单位考试资讯请关注(htshiyedanwei)公众号,欢迎加入事业单位招聘考试交流群: 参加刷题、模考、领取备考资料,考编路上不孤单!
对比两个不同的存储结构的深度优先遍历算法,对于n个顶点e条边的图来说,邻接矩阵由于是二维数组,要查找某个顶点的邻接点需要访问矩阵中的所有元素,因为需要O(n2)的时间。而邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是O(n+e)。显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。
2.2 广度优先遍历
广度优先遍历,又称为广度优先搜索,简称BFS。图的广度优先遍历就类似于树的层序遍历了。
邻接矩阵做存储结构时,广度优先搜索的代码如下。
对于邻接表的广度优先遍历,代码与邻接矩阵差异不大, 代码如下。
对比图的深度优先遍历与广度优先遍历算法,会发现,它们在时间复杂度上是一样的,不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的,只是不同的情况选择不同的算法。
7.堆 (Heap)
在计算机科学中,堆是一种特殊的树形数据结构,每个结点都有一个值。通常我们所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。
例程
为将元素X插入堆中,找到空闲位置,建立一个空穴,若满足堆序性(英文:heap order),则插入完成;否则将父节点元素装入空穴,删除该父节点元素,完成空穴上移。直至满足堆序性。这种策略叫做上滤(percolate up)。
void Insert( ElementType X, PriorityQueue H ){ int i; if( IsFull(H) ) { printf( "Queue is full.\n" ); return; } for( i = ++H->Size; H->Element[i/2] > X; i /= 2 ) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = X;}
以上是插入到一个二叉堆的过程。
DeleteMin,删除最小元,即二叉树的根或父节点。删除该节点元素后,队列最后一个元素必须移动到堆得某个位置,使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。
手机端链接:https://m.sydw.huatu.com/2014/0927/1070701.html
官方微信号
官方微博号
事业单位考试推荐 | |||||
热点考试 | |||||
招考公告 | 职位表 | 报名时间 | 报名条件 | 报名入口 | |
考试时间 | 缴费入口 | 考试科目 | 考试大纲 | 报考指导 | |
准考证 | 成绩查询 | 资格复审 | 面试公告 | 工资待遇 | |
实用备考 | |||||
每日直播 | 时政周播 | 领资料包 | 试题资料 | 备考指导 | |
图书购买 | 笔试课程 | 面试课程 | 网络课程 | 更多>>> |
事业单位微信
事业单位微博号