严蔚敏版数据结构(C语言版)PPT-第七章.ppt

1、数据结构，7.1图的定义和相关术语，7.2图的存储结构，7.4最小生成树，7章图，7.3图的扫描，7.5最短路径，7.5.2关键路径，7.5.1拓扑排序，2，数据结构，7.1图的定义和相关术语，7章图，图的结构定义333 Graph=(V，e )其中： v=|v -数据对象r= e e=|p (v，wV)表示从v到w的弧，v称为电弧的尾，w称为电弧的头。 谓词P(v，w )定义了电弧的意思和信息，表示从v到w的单向信道。3、数据结构、7.1图的定义和相关用语、第7章图、有向图、“弧”有方向性，因此将由顶点集和弧集构成的图称为有向图。 例如：其中V1=A，b，c，d，EE1=，4，数据结构，7.1图的定义和相关用语，第7章图，无向图，由顶点集和边集构成的图称为无向图。 例如：V2=A，b，c，d，e，FE2=(A，b )，(a，e )，(b，e )，(c，d )，(d，f )，(b，f )，(c，F)，如果VR需要VR，则替换成(v，w )，在v和w之间存在边缘。5、数据结构、7.1图的定义和相关术语、第7章图、名词和基本术语、假设图中有n个顶点、e边，则包含e=n(n-1)/2边的无向图称为完整图，包含e=n(n-1 )弧的有向图称为有向图，边或弧的个数e。 p=图形 v .next； /*p是第v个顶点的第一个相邻点*/while(p！=空) if (visited p-data =DFS (visited，p-data )； /*递归调用*/p=p-next； ，37，数据结构，7.3图的扫描，第7章图，深度优先搜索，非递归形式的DepthFirstSearch，I .首先把v0放入堆栈中，.只要堆栈不空闲，重复以下处理： a .堆栈的顶点离开堆栈、a、a、1、e、d、b、1、e、c、1、f、f、1、e、1、g、1、h、I、1、38、数据结构、7.3图的扫描，第7章图、宽度优先探索、基本思想：I .图如果vi和vk是当前节点，且vi在vk之前被访问，则vi中的所有未访问的相邻点将确保在vk的所有未访问的相邻点之前被访问。 重复，直到所有末端节点都没有被访问的相邻接点消失为止。 树的分层遍历、39种数据结构、7.3图的遍历、第7章的图、 40、数据结构、宽度优先搜索、宽度优先扫描图g的算法描述、voidBFS(int*visited、intv、int*Queue)GraphNode*p； addquene (队列，v) /*初始顶点入队*/visitedv=1； /*访问的顶点*/printf(%d-， v )； /*表示*/while(front！=rear)/*队列不为空*/ v=队列(队列)/*检索队列元素*/p=Graphv.next； 相邻顶点*/while(p！=NULL)/*相邻顶点*/if(visitedp-data=0)/*从未横穿过*/AddQuene(Queue，p-data )； /*v的相邻顶点入队*/visitedp-data=1； 打印( % d-，p-data )； p=p-next； /*接下来的相邻顶点*/，41，数据结构，7.3图的扫描，第7章图，算法思想：I .将访问起点v0标记访问标志，将v0入队广泛的优先搜索，.只要团队不空闲，重复以下处理： a .团队的开头no 对b.v的所有相邻点w，w没有访问时，访问w设置访问标志，将w入队。a，1，a，b，d，e，1，1，1，b，d，e，c，1，c，g，1，g，f，1，f，f，f，h，1h，I，1，I，42，数据结构，7.4最小生成树，第7章图，图的连接性问题，最短路径问题， 利用图的遍历可以判断一个图是否相连，在遍历过程中，如果多次调用搜索过程，则表示该图是非连通图，如果多次调用搜索过程，则表示该图中有几个连通成分。1 .图的连接性问题，无向图的连接成分，a、b、d、c、I、e、f、g、h、j、44、数据结构，7.4最小生成树，第7章图、1 .图的连接性问题，求图中两个顶点间的简单路径，从顶点b到顶点k的简单路径。 例如，从顶点b开始进行深度优先搜索扫描。a，b，c，d，e，k，h，a，b，e，k，45，数据结构，7.4最小生成树，第7章图，1 .图的连接性问题，图的生成树和最小生成树，生成树：如果图g是连通的图，则从图中的某一顶点横穿横断面图时，横穿图中的所有顶点一个连通图的生成树是极小连通子图，包含图中的全部n个顶点，但只有足以构成一棵树的n-1边。46，数据结构，7.4最小生成树，第7章图，1 .图的连接性问题，图的生成树和最小生成树，该问题等效于：结构网的一条最小生成树，即在e波段权的边中选择n-1条边(不构成循环)，使“权重之和”最小化。 如果在n个城市之间建立通信联系网的话，连接n个城市只需要建设n-1条线路，如何最节约经费来建立这个通信网呢？47、数据结构，7.4最小生成树，第7章图，1 .图的连接性问题，图的生成树和最小生成树，I .尽可能选择权重小的边，但不能构成电路。 .为了连接网的n个顶点，选择n-1条适当的边。 算法1 :克鲁斯卡尔算法(Kruskal )，算法2 :普利姆算法(Prim )，最小生成树的两个问题： 48，数据结构，7.4最小生成树，第7章图， 1 .图中的连接性问题，图中的生成树和最小生成树，算法1 :克鲁斯卡尔算法(Kruskal )，考虑问题的起点：为了使生成树边的权重之和最小，尽可能地对生成树边进行加权。 具体而言，首先构筑仅包含n个顶点的子图SG，从权重最小的边开始，如果由于该追加而在SG中不产生电路，则对SG加该边，反复进行直到加n-1边为止。 加法，49，数据结构，7.4最小生成树，第7章图，1 .图的连接性问题，图的生成树和最小生成树，算法1 :克鲁兹卡尔算法(Kruskal )的例子，算法步骤如下： (1)边的权重首先按从小到大的顺序排序。 (2)从所有未扫描的边缘取出最小权重的边缘，记录该扫描并检查是否形成了循环。 50、数据结构，1 .所有边都按照权重值从小到大的顺序排列，5(B、c )、b、a、e、f、d、c、18、11、6、5、16、 6(B、d )、6(C、d )、11(B、e )、14(D、e )、16(A、b )、18(D、f )、19(A、f )、21(A、e )、33(E、f )、2 .顶点集合状态： b，c，c，d，e，b，c，d，e，c，d，e，e，b，c，d，e，e，f，3 .最小生成树边的集合：51，数据结构，7.4最小生成树第7章图，1 .图的连接性问题，图的在追加的顶点w和已经位于生成树上的顶点v之间一定存在边缘，该边缘的权重在连接所有顶点v和w之间的边缘中取最小的值。 之后，继续向生成树追加顶点，直到生成树中包含n个顶点为止。52，数据结构，7.4最小生成树，第7章图，1 .图的连接性问题，图的生成树和最小生成树，算法2 :普利姆算法(Prim )，一般追加的顶点应满足条件：在生成树的结构过程中，图中n个顶点两个集合：已经在生成树中在连接未落入生成树的顶点集V-U的u顶点和V-U顶点的所有边中，必须选择权重最小的边。基本思想：加分法，53，数据结构，7.4最小生成树，7章图，1 .图的连接性问题，图的生成树和最小生成树，算法Prim，实例：a，b，c，d，e，g，f，54，数据结构1 .图的连接性问题图的生成树和最小生成树，算法2 :普利姆算法(Prim )，算法思想，N=(V，E )作为连通网，TE作为n上最小生成树中的边的集合。 第一个U=u0，(u0V )，TE=，重复执行以下运算：在所有u-u，vV-U的边(u，v)E中，查找成本最小的边(u0，v0 )并耦合到集合te，同时将v0耦合到u，以达到U=V 55，数据结构，7.4最小生成树，第7章图，1 .图的连接性问题，图的生成树和最小生成树，算法2 :普利姆算法(Prim )，算法思想，连接网用加权的邻接矩阵表示，辅助数组closedge，数组元素下标用当前V-U集中的顶点即，对于vV-U的各顶点，closedgev记录与v邻接的从u到V-U的边中最小的边的全部信息。56，数据结构，7.4最小生成树，第7章图，1 .图的连接性问题，图的生成树和最小生成树，算法2 :算法思想，57，数据结构，7.4最小生成树，第7章图，1 .图的连接性问题，图的生成树和最小生成树，算法算法思想演示，a，b，c，d，e g，f，0，1a，19，1a，14，1a，18，0，5e，16，0，4d，7，4d，3，4d，21，0，3c，5，0，0，0 I .图的生成树不是唯一的，可以从不同的顶点循环，得到不同的生成树，.从相同的顶点出发，在选择最小边时，可以选择多个相同的边。 此时，选择其中一个。 7.4最小生成树，第7章图，1 .图的连接性问题，图的生成树和最小生成树，59，数据结构，7.4最小生成树，第7章图，1 .图的连接性问题，图的生成树和最小生成树，O(n2 )，O(eloge )，稠密图， 稀疏图，比较两种算法，60，数据结构，7.5无循环图及其应用，第7章图，2 .在无循环图中有应用，有加权图的最短路径，在从一个顶点(起点)到另一个顶点(终点)的路径中，各边(或弧)的I .从单源点到其馀各点的最短路径离散算法(Dijkstra )，ii .各顶点之间的最短路径浮点算法(floyd )，61，数据结构，第7章图，2 .应用于无环图；加权图的最短路径，I .从单源点开始Dijkstra算法、基本思想：按照最短路径的长度递增的顺序求出各路径。 在源点V0、vi、vj，中，从源点V0到顶点vi的最短路径是从V0到各点的最短路径集合中最长的路径。7.5无环路图及其应用，62，数据结构，第7章图，2 .无环路图的应用，戴克斯特拉算法(戴克斯特拉)，最短路径长度(v0，v2)10(v0，v4，v3)30(v0，v4，v3，v3)50(v0，v3 v5)60v0v1，7.5无环路图及其应用，63，数据结构，第7章图，2 .应用于无环图，Dijkstra法(Dijkstra )，路径长度最短的最短路径特征：该路径必须包含一个弧，而且该弧的重(v0vi )，下一个路径的长度较短的最短路径特征：或从源到该点vj (仅包括一条弧)； 或者，从原点经由顶点vi到达vj (由两条弧构成)。7.5无环图及其应用，64，其馀最短路径特征：下一条路径长度短的最短路径特征：它可能有两种情况：或者直接从源到该点(仅包括一条弧)。 或者，从原点经由顶点vi、vj到达该顶点(由多条弧构成)。的双曲馀弦值。 或者，从源点到该点(仅包括一个圆弧)或者从源点经由求出的最短路径的顶点，到达该顶点。 有在数据结构，第7章图，2 .无环图中的应用，有distra算法(distra )，有7.5无环图及其应用，有65，数据结构，第7章图，2 .无环图中的应用，distra算法实现了思想2 .顶点分为s、V-SS两组，存储求出的最短路径的终点的集合。 3 .辅助一维阵列dist:vis，disti表示源点vi的最短路径长度： viV-S，disti表示仅包含源点vi的s中的顶点的最短路径。 初始： S=v0，v0是源点disti=g.arcs0i.adj； (viV-S )，7.5无循环图及其