9数据结构基本概念(九).doc

数据结构：基本概念(九) 　　? 最小生成树的定义 　　设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)，令G的最小生成树为T=(U，TE)，其初态为U=V，TE={}，然后按照边的权值由小到大的顺序，依次考察边集E中的各条边。若被考察边的两个顶点属于T的两个不同的连通分量，则将此边加入到TE中，同时把两个连通分量连接为一个连通分量;若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路。如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。 　　? 迪杰斯特拉(Dijkstra)算法的基本思想 　　设置集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径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中间顶点的序号不大于k的最短路径。 　　? AOV网的定义 　　在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。 　　? 拓扑序列的定义 　　设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。 　　? 拓扑排序的基本思想 　　对AOV网进行拓扑排序的基本思想是： 　　⑴ 从AOV网中选择一个没有前驱的顶点并且输出它; 　　⑵ 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧; 　　⑶ 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。 　　? 查找算法的时间性能 　　查找算法用关键码的比较次数来度量查找算法的时间性能。对于查找成功的情况，将关键码比较次数的数学期望值定义为平均查找长度，即： 　　ASL 其中，n表示问题规模，即查找集合中的记录个数;pi表示查找第i个记录的概率;ci表示查找第i个记录所需的关键码的比较次数。 　　? 顺序查找算法的时间复杂度 　　对于具有n个记录的顺序表，查找第i个记录时，需进行n-i+1次关键码的比较。设每个记录的查找概率相等，查找成功时，顺序查找的平均查找长度为：O (n);查找不成功时，关键码的比较次数是n+1次，则查找失败的平均查找长度为O(n)。 　　? 顺序查找的适用情况 　　顺序查找对表中记录的存储没有任何要求，顺序存储和链接存储均可应用;对表中记录的有序性也没有要求，无论记录是否按关键码有序均可应用。 　　? 折半查找的适用情况 　　折半查找(也称对半查找、对分查找、二分查找)要求线性表中的记录必须按关键码有序，并且必须采用顺序存储。 　　? 折半查找的基本思想 　　取有序表的中间记录作为比较对象，则 　　(1)若给定值与中间记录的关键码相等，则查找成功; 　　(2)若给定值小于中间记录的关键码，则在中间记录的左半区继续查找; 　　(3)若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。 　　不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。 　　? 折半查找的时间复杂度 　　具有n个结点的折半查找判定树的深度为 。 　　最好情况：比较1次，即查找的关键码是判定树的根结点; 　　最坏情况：比较次数为 ，即查找的关键码是判定树的最下一层结点; 　　平均情况：折半查找的平均时间复杂度为O(log2n)。 　　查找不成功的比较次数最多不超过树的深度，最多为 次。