交大学位考辅导3试卷.ppt

主要内容： 1. 图 2.查找、排序;第七章 图;1 图的定义、术语和存储结构;顶点数n和边(弧)的数目e： 无向图： 有向图： 完全图：有n(n-1)/2条边的无向图; 有向完全图：有n(n-1)条弧的有向图; 稀疏图、稠密图 子图：G=(V,{E}),G’=(V’,{E’})，若V’ V,且E’ E,则称G’为G的子图 邻接点：无向图中，(v,v’)∈E，则v,v’互为邻接点； 顶点v的度：与v相关联的边的数目，TD(v) 有向图中,若v,v’∈A，则顶点v邻接到顶点v’，而顶点v’邻接自v 出度：以v为尾的弧的数目，OD(v) 入度：以v为头的弧的数目，ID(v) TD(v)=OD(v)+ID(v) ;路径： 回路（环） 简单路径：顶点序列中顶点不重复的路径。 连通图、连通分量、强连通图、强连通分量：;一个连通图的生成树：一个极小连通子图，含有图中全部结点，但只有足以构成一棵树的n-1条边。 一棵有n个顶点的生成树有且仅有n-1条边 但有n-1条边的图不一定是生成树 有向图：如果有一个顶点的入度为0，其余顶点的入度都为1，则是一棵有向树。; 图的存储结构; 图的邻接矩阵 A[i][j]=1 //若vi,vj存在 A[i][j]=0 //若vi,vj不存在 无向图：第i行分量的和为结点vi的度 有向图：第i行分量的和为结点vi的出度； 第i列分量的和为结点vi的入度 网的邻接矩阵 A[i][j]=无穷大 vi, vj间无边 =权 vi, vj间有边 问题：为什么放无穷大而不放0; 邻接表：一种链式存储结构 为图中的每一个顶点创建一个单链表，其中的结点表示依附于顶点的边(以该顶点为尾的弧);无向图的邻接表中，顶点v的度就是该顶点的单链表中的结点数； 有向图中，第i个链表的结点数是该顶点的出度； 如何求有向图中顶点的入度？——有向图的逆邻接表。;V1;邻接多重表：无向图的另一种链式存储结构。 ;2. 图的遍历;深度优先遍历;v1;一个非连同图的深度优先遍历过程图解;广度优先遍历;一个非连同图的广度优先遍历过程图解;3.图的连通性问题——掌握连通分量的求法;4 掌握最小生成树的概念和求法;Prim算法构造最小生成树的过程：;Kruskal算法构造最小生成树的过程; 拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，就是拓扑排序。 偏序：集合中仅有部分成员之间可以比较； 全序：集合中全体成员之间均可比较。 AOV网：顶点表示活动，弧表示活动之间的优先关系的有向图称为顶点表示活动的网。;进行拓扑排序的方法： 在有向图中选一个没有前驱的顶点且输出； 从图中删除该结点和所有以该结点为尾的弧。 重复上述操作。若可以输出全部顶点，则该图中不存在环，否则存在环。 例如： 算法实现： 以邻接表的方法存储有向图； 头结点增加信息：顶点入度； 增加一个栈：存放入度为0的顶点。;6 最短路径;Dijkstra算法 求最短路径;查找;1 顺序表的查找;Int Search_Seq(SSTable ST, KeyType key) { //从尾部依次比较key和数据元素的关键字， //当比到0下标才成功则查找不成功，返回0 //否则返回下标i ST.elem[0].key = key; for (i=ST.length; !EQ(ST.elem[i].key, key); --i); return i; }//Search-Seq 0下标为监视哨,时间复杂度O(n) 平均查找长度： ASL =sum(pici) i=1…n;查找成功： pi = 1/n ci= 1,2,3…n ASL=1/n[1+2+…+n] = (n+1)/2 查找不成功：ASL = n+1 , (n, n-1…1, 0) 成功和不成功同概率：1/2 ASL = ?*1/n[1+2+…+n]+1/2(n+1) = ?(n+1) ;折半查找：先确定待查记录的范围，逐步缩小范围直到找到或找不到。 例：在下列数据元素中查找关键字为21和85的数据元素 分析：设置两个指针low ,high指示待查元素所在范围的上界和下界。mid＝（low+high）/2 ST.elem[mid].key=ke