第四章-字符串.ppt

第7章图,7.1图的定义、术语和基本运算,7.2图的存储结构,7.3图的遍历与拓扑排序,7.4最小生成树,7.5最短路径,7.6本章小结,7.1图的定义、术语和基本运算,7.1.1图的定义及术语图结构的形式化定义：Graph=(V,R)，其中：V=x|xD,D是具有相同特性的数据元素的集合；R=Edge，Edge=|P(x,y)(x,yV),谓词P(x,y)定义了弧上的意义或信息。,圆圈代表数据元素,圆圈之间的连线代表数据元素之间的关系,在图结构中，一个元素可以有多个直接后继，也可以有多个直接前趋。,相关术语,顶点（vertex）Edge是两个顶点之间的关系的集合：Edge，则为从x到y的一条弧；x为弧尾或始点；y为弧头或终点。此时的图称为有向图。,若Edge是对称的用无序对(x,y)表示x和y之间的一条边。此时的图称为无向图。,不考虑顶点到自身的边：完全图：N个顶点，有N(N-1)/2条边的无向图；有向完全图：N个顶点，有N(N-1)条弧的有向图；,稀疏图/稠密图,网（Network）：带边权的图,子图：,无向图中两顶点互为邻接点；边和顶点相关联；顶点的度,有向图中邻接到/邻接自顶点的入度/出度,图中的顶点与边/弧之间有以下关系,路径路径的长度,回路/环,简单路径简单回路/简单环,连通连通图连通分量,强连通图(有向图)强连通分量,连通图的生成树有向图的生成森林,7.1.2图的基本运算及其ADT,图的基本运算查找，插入和删除顶点在图中的位置：人为随意排列,图的ADT声明,ADTGraph数据对象为D:D是具有相同特性的数据元素的集合,称为顶点集。数据间的关系R:R=Edge,Edge=|P(x,y)(x,yV),谓词P(x,y)定义了弧上的意义或信息,几种基本操作:graphCreate(&graph)graphDestroy(&graph)graphClear(&graph),创建空的图对象graph,销毁一个已有的图graph,将图graph清空,graphEmpty(graph)graphCount(graph)graphInsertVertex(&graph,dataIn),判图graph是否为空,求图graph中顶点个数,在图graph中插入新顶点,新顶点数据域的值是dataIn,graphDeleteVertex(&graph,dltKey)graphInsertArc(&graph,fromKey,toKey),在图graph中插入新弧,弧头节点和弧尾节点关键字是fromKey和toKey,在图graph中删除顶点,待删顶点数据域的关键字是dltKey,graphDeleteArc(&graph,fromKey,toKey)graphTraverse(graph,visit),遍历图graph各顶点，并用visit代表的操作去处理各个顶点中的数据,在图graph中删除弧,弧头节点和弧尾节点关键字是fromKey和toKey,graphRetrieveVertex(graph,key,&DataOut),在图graph中寻找关键字为key的顶点,并将其信息放入DataOut输出参数中,7.2图的存储结构,图的常用存储结构,数组表示法连续存储方式邻接表邻接多重表链式存储方式十字链表,7.2.1数组表示法,设G=(V,E)是有N(N1)个顶点的图，则G的邻接矩阵是具有如下性质的N阶方阵：,对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和。对于有向图，第i行的元素之和为顶点vi的出度OD(vi)，第j列的元素之和为顶点vj的入度ID(vj)。,网的邻接矩阵可定义为：,描述图时，我们同时使用两个数组：一维数组中存储的是各个顶点的信息；二维数组（邻接矩阵）中存储的是边或弧的信息。,7.2.2邻接表,在无向图的邻接表中，顶点vi的度恰为第i个链表中的节点数；而在有向图中，第i个链表中的节点数只是顶点vi的出度；为求入度，必须对整个邻接表扫描一遍。在所有链表中其邻接点域的值为i的节点的个数是顶点vi的入度。有时，为了便于求每个顶点的入度，尚需建立一个有向图的逆邻接表，即对每个顶点vi建立以vi为弧头的链表。,7.2.3邻接多重表,邻接多重表适宜作无向图的存储结构。,在无向图的邻接表表示法中，每条边(vi,vj)是用两个表节点表示的。这给某些图的操作带来不便。,7.2.4十字链表,十字链表：将有向图的邻接表和逆邻接表结合在一起得到的一种链表。图示参看图7.6,在十字链表中既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度（若需要，可在建立十字链表的同时求出）。在某些有向图的应用中，十字链表是很有用的工具。,7.3图的遍历与拓扑排序,7.3.1图的遍历遍历图的方法：深度优先搜索（DepthFirstSearch）广度优先搜索（BreadthFirstSearch）,深度优先搜索体现了优先向纵深发展的趋势。算法思路可考虑回溯法。时间复杂度为O(n+e)。,广度优先搜索需要借助队列，其时间复杂度与深度优先搜索相同。,7.3.2拓扑排序,有向无环图：DirectAcyclineGraph，简称DAG图，无环的有向图。有向无环图是描述一项工程或系统其进行过程的有效工具。,拓扑排序（TopologicalSort）,由某个集合上的一个偏序得到该集合上的一个全序的运算。,当图中顶点数量与弧的数目分别为n和e时，时间复杂度为O(n+e)。拓扑排序本质上是图的遍历，其时间复杂度为O(n)，故整个算法时间复杂度为O(n+e)。,学生的选课问题（拓扑排序问题）：,拓扑排序后的序列可有多种。下面就是其中的两种拓扑序列。第一种是：1，2，3，6，4，10，5，7，9，8，11；第二种是：3，2，6，4，5，7，8，1，10，9，11。,7.4最小生成树,在连通网的生成树中选择这样一棵生成树，使它在所有生成树中总的耗费最小，即为此连通网的最小生成树。,最小生成树的MST性质：假设N=(V,E)是一个连通网，U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值（代价）的边，其中uU，vV-U，则必存在一棵包含边(u,v)的最小生成树。,最小生成树的两种算法：,Kruskal算法Prim算法,基于MST性质，使用了贪心算法的思想,Kruskal算法,按边权值的递增顺序，依次找出权值最低的边来构建最小生成树，而且规定每次新增的边，不能使已生成的部分出现回路。对于N个顶点的连通图来说，当已找出N-1条边时，过程结束。,Prim算法,与Kruskal算法思路类似，区别在于：每次加入的新边都会与已生成部分相邻接，将顶点逐个连通而成最小生成树。,7.5最短路径,带权图中求最短路径的问题，即求两个顶点间长度最短的路径。注意：这里路径长度指的是路径上的边所带权的总和，而不是路径上边数的总和。,7.5.1单源最短路径问题与分支限界法,单源最短路径问题:Dijkstra算法,Dijkstra算法解决单源最短路径的基本策略是：先求出长度最小的一条最短路，然后求出长度第二小的最短路径，最后求出长度最大的最短路径。,应用Dijkstra算法的求解过程示例,从解空间树中我们得到源点A到网中其他顶点的最短路径的分析过程中，使用了分支限界法(BranchandBound)的思想。,分支限界法与回溯法的对比：,同：同为在问题的解空间树上搜索问题解的方法。,异：1.求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。,2.对解空间树的搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费（最大效益）优先的方式搜索解空间树。,由于有双重循环，故对于含有N个顶点的有向网来说，Dijkstra算法总的时间复杂度是O(N2)。,7.5.2多源最短路径问题与动态规划法,多源最短路径问题：方法一：每次以一个顶点为源点，重复执行Dijkstra算法N次。,效率与方法一同阶，但形式相对简单,方法二：Floyed算法,Floyed算法从图的带权邻接矩阵cost出发，其基本思想是：假设求从顶点vi到vj的最短路径。如果从vi到vj有弧，则从vi到vj存在一条长度为costi,j的路径。该路径不一定是最短路径，尚需进行N次试探。首先考虑路径(vi,v1,vj)是否存在（即判断弧(vi,v1)和(v1,vj)是否存在）。如果存在，则比较其路径长度。取长度较短者为从vi到vj的中间顶点的序号不大于1的最短路径。,假如在路径上再增加一个顶点v2，即如果(vi,v2)和(v2,vj)分别是当前找到的中间顶点的序号不大于1的最短路径，那么，(vi,v2,vj)就有可能是从vi到vj中间顶点的序号不大于2的最短路径。将它和已经得到的从vi到vj中间顶点序号不大于1的最短路径相比较，从中选出较小者做为中间顶点的序号不大于2的最短路径。之后，再增加一个顶点v3，继续进行试探。依此类推，直至经过N次比较，最后求得的就是从vi到vj中间顶点的序号不大于N的最短路径。因为有向网中只有N个顶点，故该路径就是从vi到vj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。,Floyed算法中，新一步的结果总是基于上一步的结果，所以每次运算都无需从头做起，这正是动态规划(DynamicProgramming)算法的典型设计思想。,动态规划法与分治法的对比：,同：在解决问题时基于问题的划分：将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。,异：分治法中，各个子问题是独立的(即不包含公共的子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。要做许多不必要的重复工作。动态规划法中，整个问题的最优解是由各个子问题的最优解构成的。在求解过程中，每个子解都是在前面的结果上得出的新的子解，子解随着步骤的进行而逐步扩大，最后一步得到完整的解。,7.6本章小结,基本内容：1.图的定义，有关术语；2.图的四种存储结构；3.图的两种遍历方法：深度优先遍历和广度优先遍历；拓扑排序问题；4.