欢迎来到天天文库
浏览记录
ID:28798995
大小:249.50 KB
页数:3页
时间:2018-12-14
《计算机备考资料:数据结构基本概念(九)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、数据结构:基本概念(九) Ø最小生成树的定义 设G=(V,E)是一个无向连通网,生成树上各边的权值之和称为该生成树的代价,在G的所有生成树中,代价最小的生成树称为最小生成树。 Ø普里姆(Prim)算法的基本思想 设G=(V,E)是一个无向连通网,令T=(U,TE)是G的最小生成树。T的初始状态为U={v0}(v0∈V),TE={},然后重复执行下述操作:在所有u∈U,v∈V-U的边中找一条代价最小的边(u,v)并入边集TE,同时v并入顶点集U,直至U=V为止。 Ø克鲁斯卡尔(Kruskal)算法的基本思想 设无向连通网为G=(V,E
2、),令G的最小生成树为T=(U,TE),其初态为U=V,TE={},然后按照边的权值由小到大的顺序,依次考察边集E中的各条边。若被考察边的两个顶点属于T的两个不同的连通分量,则将此边加入到TE中,同时把两个连通分量连接为一个连通分量;若被考察边的两个顶点属于同一个连通分量,则舍去此边,以免造成回路。如此下去,当T中的连通分量个数为1时,此连通分量便为G的一棵最小生成树。 Ø迪杰斯特拉(Dijkstra)算法的基本思想 设置集合S存放已经找到最短路径的顶点,S的初始状态只包含源点v,对vi∈V-S,假设从源点v到vi的有向边为最短路径。以后每
3、求得一条最短路径v,…,vk,就将vk加入集合S中,并将路径v,…,vk,vi与原来的假设相比较,取路径长度较小者为当前最短路径。重复上述过程,直到集合V中全部顶点加入到集合S中。 ØFloyd算法的基本思想 假设从vi到vj的弧(若从vi到vj的弧不存在,则将其弧的权值看成∞)是最短路径,然后进行n次试探。若vi,…,vk和vk,…,vj分别是从vi到vk和从vk到vj中间顶点的序号不大于k-1的最短路径,则将vi,…,vk,…,vj和已经得到的从vi到vj中间顶点的序号不大于k-1的最短路径相比较,取长度较短者为从vi到vj中间顶点的序
4、号不大于k的最短路径。 ØAOV网的定义 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这样的有向图为顶点表示活动的网,简称AOV网。 Ø拓扑序列的定义 设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列v1,v2,…,vn称为一个拓扑序列,当且仅当满足下列条件:若从顶点vi到vj有一条路径,则在顶点序列中顶点vi必在顶点vj之前。 Ø拓扑排序的基本思想 对AOV网进行拓扑排序的基本思想是: ⑴从AOV网中选择一个没有前驱的顶点并且输出它; ⑵从AOV网中删去该顶点,并且删去所有以该顶点为尾的弧
5、; ⑶重复上述两步,直到全部顶点都被输出,或AOV网中不存在没有前驱的顶点。 Ø查找算法的时间性能 查找算法用关键码的比较次数来度量查找算法的时间性能。对于查找成功的情况,将关键码比较次数的数学期望值定义为平均查找长度,即: ASL其中,n表示问题规模,即查找集合中的记录个数;pi表示查找第i个记录的概率;ci表示查找第i个记录所需的关键码的比较次数。 Ø顺序查找算法的时间复杂度 对于具有n个记录的顺序表,查找第i个记录时,需进行n-i+1次关键码的比较。设每个记录的查找概率相等,查找成功时,顺序查找的平均查找长度为:O(n);查找
6、不成功时,关键码的比较次数是n+1次,则查找失败的平均查找长度为O(n)。 Ø顺序查找的适用情况 顺序查找对表中记录的存储没有任何要求,顺序存储和链接存储均可应用;对表中记录的有序性也没有要求,无论记录是否按关键码有序均可应用。 Ø折半查找的适用情况 折半查找(也称对半查找、对分查找、二分查找)要求线性表中的记录必须按关键码有序,并且必须采用顺序存储。 Ø折半查找的基本思想 取有序表的中间记录作为比较对象,则 (1)若给定值与中间记录的关键码相等,则查找成功; (2)若给定值小于中间记录的关键码,则在中间记录的左半区继续查找;
7、 (3)若给定值大于中间记录的关键码,则在中间记录的右半区继续查找。 不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。 Ø折半查找的时间复杂度 具有n个结点的折半查找判定树的深度为。 最好情况:比较1次,即查找的关键码是判定树的根结点; 最坏情况:比较次数为,即查找的关键码是判定树的最下一层结点; 平均情况:折半查找的平均时间复杂度为O(log2n)。 查找不成功的比较次数最多不超过树的深度,最多为次。
此文档下载收益归作者所有