数据结构第7章 图3课件

1、、7.1图的类型定义、7.2图的记忆结构、7.3图的扫描、7.4最小生成树、7.5无环图及其应用、7.6最短路径、1、PPT学习交流、7.3图的扫描、图的扫描：从图中的某个顶点出发，扫描图中的剩馀顶点，仅访问图中的各顶点一次在图中，访问了一部分顶点后，有可能再次回到沿另一边访问过的顶点。 为了确保每个顶点只能被访问一次，必须对顶点进行标记，通常使用辅助数组visit0.n-1作为顶点的标记，如果没有访问顶点vi，则visiti值为0如果访问vi，则visiti值为1。 通常，横穿该图的路径有深度优先搜索和宽度优先搜索两种，其应用于无向图和有向图两者。 2、PPT学习交流、图的两种扫描方法：1.

2、深度优先搜索图的深度优先扫描是树一样的先根扫描。 所采用的检索方法的特征是尽可能先检索深度方向。 这种搜索方法被称为深度优先搜索(Depth-First Search )。 因此，以该方式扫描附图被称为附图中的深度优先扫描。 2 .宽度优先搜索像宽度优先搜索树一样的分层搜索。 采用的搜索方法的特征在于尽可能在横向上进行搜索，从而被称为宽度优先搜索(Breadth-FirstSearch )。 相应的扫描被称为宽度优先扫描。 3、PPT学习交流，1 .深度优先搜索DFS，基本思想：选择图中的某(强)连接成分的顶点v出发：访问过顶点v，访问过其访问标志，visitedv=1； 依次，从v未被访问的

3、邻接点开始，到(强)连通成分和v有路连通的顶点被访问为止，继续图中的深度优先扫描，图中顶点还没有被访问的情况下，以图中的剩馀(强)连结成分中的未被访问的顶点为起点，直到图中的所有顶点被访问为止，上述4、PPT学习交流、5、PPT学习交流、(强)连通成分的扫描： W1、W2、W3都是v的邻点。 SG1是可以从W1访问的顶点集，SG2是可以从W2访问的顶点集，SG3是可以从W3访问的顶点集合。 存取步骤： SG1 SG2 SG3。 交叉部分只访问一次。 6、PPT学习通信、7、PPT学习通信、t、t、t、t、t、t、a、c、d、k、f、e、g、a、c、h、k、f、e、d、b、g、访问标志3360

4、v=G.vexnum； v) visitedv=FALSE； /访问标志数组初始化for (v=1； v=G.vexnum； A ) PK (！ 根据visitedv (g，v，visit )、void DFS (Graph G，int v，Status (*Visit)(int v) /顶点v，进行深度优先搜索遍历连接成分visitedv=TRUE； (*Visit)(v) /未访问的邻接顶点递归地调用for (w=first adjvex (g，v) w=0； w=下一个调整(g，v，w) if (！ visitedw (g，w，visit) /DFS，深度优先遍历递归算法，9，PPT学习

5、通信，示例1 :深度优先遍历图g，深度优先遍历序列。 系列1: V1、V2、V4、V8、V5、V3、V6、V7系列2: V1、V2、V5、V8、V4、V3、V7、V6，注意：由于访问相邻点的顺序没有规定，所以深度优先序列并不唯一。10、PPT学习交流，例2 :写深度优先遍历图g、深度优先遍历序列。 深度优先遍历序列： V1、V2、V4、V8、V5、V6、V3、V7、V1、V2、V5、V8、V6、V1、V3、V7、V8、V6、V5、V2、V4、11、PPT学习通信、深度优先老虎图中的DFS序列是唯一的，其中标识了未必是唯一的源点和存储结构的内容。 在邻接矩阵表示的图确定了源点后，DFS序列表示唯

6、一的邻接表的内容和初始起点，才能唯一地确定DFS序列，12、PPT学习通信，例3 :已知图的邻接表如下所示，求出从顶点0起的深度优先遍历序列。深度优先遍历序列：0、1、2、3、4，深度优先遍历序列：0、1、2、3、4、1、4、2、3、3、2、1、4、0、3、2、4、1、13、PPT学习交流，示例4 :已知图的相邻矩阵，距顶点0的深度优先遍历深度优先遍历序列：0、1、3、4、2、5、6、14、PPT学习交流，例5 :已知图的邻接表如下所示，求出从顶点0起的深度优先遍历序列。 深度优先扫描序列：0，1，2，3，15，PPT学习交流，2 .宽幅优先搜索BFS，选择(强)有连接成分的顶点vi出发：访问

7、顶点vi，访问了其访问标志，访问了visitedvi=1的vi的所有未访问的邻接点w1 依次从这些相邻点访问所有这些未访问的相邻点，重复上述步骤，直到访问到(强)连通成分的所有顶点的图的所有顶点为止。 16、PPT学习交流，对于连通图，从起点v到其他各顶点必定有路径存在。 在此，Vw1、Vw2、Vw5路径长度为1，Vw3、Vw6、Vw8的路径长度为2，Vw4、Vw7的路径长度为3，各顶点与起点间具有“远近”的关系。 以“从近到远”的顺序进行遍历。 17、PPT学习交流、void bfs traverse (图形g、状态(* visit ) (int v ) )/宽度优先非递归遍历。 使用辅助队

8、列q和访问标志数组visited。 for (v=1； PD.PS num； v) visitedv=FALSE； InitQueue(Q) /空的辅助队列Q for (v=1； v G.vexnum； A ) PK (！ visitedv) /v没有访问visitedv=true (* visit ) (v )/开始访问EnQueue(Q，v) /v队列while (！ 队列实施(q ) )队列(q，u) /团队头元素离开团队u、下一页、18、PPT学习交流、for (w=第一个调整(g，u) w=0； w=下一个调整(g，u，w) /邻接点if (！ visitedw) /u的未访问的相邻

9、顶点w排队Q visitedw=TRUE； (*Visit)(w) EnQueue(Q，w) /if /while /BFSTraverse，19，PPT学习通信，示例1 :宽优先级遍历图g，宽优先级写遍历序列。 宽度优先遍历序列： V1、V2、V3、V4、V5、V6、V7、V8，示例2 :创建宽度优先遍历图g，并创建宽度优先遍历序列。 宽度优先遍历序列： V1，V2，V3，V4，V5，V6，V7，V8，20，PPT学习交流，图的宽度优先遍历序列宽度优先遍历图中得到的顶点序列，定义为图的宽度优先遍历序列，简称为BFS序列。 如果图示的BFS序列提供了源点和图示的存储结构(不一定是唯一的)，那么

10、BFS序列是唯一的。21、PPT学习交流，例3 :已知图的邻接表如下，求出从顶点0起的广度，优先遍历系列。 宽度优先遍历序列：0、1、3、2、4，宽度优先遍历序列：0、1、3、2、4、1、3、4、2、0、3、1、2、4、22、PPT学习交流，例4 :已知图的邻接矩阵，求出从顶点0开始的宽度优先遍历序列。0、1、2、3、4、6、5、宽度优先遍历序列：23、PPT学习交流，例5 :已知图的邻接表如下所示，求出从顶点0开始的宽度优先遍历序列。 24、PPT学习交流，例6 :画出其网络的邻接矩阵。 根据所绘制的相邻矩阵的存储结构，分别从顶点1开始进行深度优先扫描和宽度优先扫描，25、PPT学习交流、1

11、23456、12346、深度优先： 1、2、5、4、6、3宽度优先： 1、2、3、5、6、4、26、PPT学习交流、极大连通子图在这个子图的顶点上加上d，子图已经不连通，极小连通子图：这个子图是g的连通子图，在这个子图中如果删除任一边，子图就不连通了。 在t为g的生成树中，只有t满足以下条件：1. T为g的连接子图2. T为包括g在内的所有顶点3. T上没有循环，在7.4最小生成树、27、PPT学习通信、7.4最小生成树、n城市间构筑通信联系网问题：分析：首先，这个网必须是连通网，其次，网络上的线路必须是最低的，最后，考虑所有线路的长度之和最小。 最小生成树满足了上述要求.28、PPT学习交流

12、，上述问题等效于在e波段权重边中选择n-1边，使“权重之和”最小化。 求最小生成树的两个算法：普利姆算法：适用于求边密集网的最小生成树。 克鲁斯卡尔算法：适用于求边稀疏网的最小生成树。29、PPT学习通信，假定有链路N=V，e，求n的最小生成树T=TV，TE。 算法的基本思想：一，普利姆(Prim )算法，TV=v，TE=； /从一个顶点v开始TE =min(v，u )、TV =u、在此为vTV、uV-TV； 重复步骤2直到电视=v。 30、PPT学习交流，把图中的任一顶点v作为生成树的根，然后把新的顶点w追加到生成树中。 在追加的顶点w和生成树的顶点v之间一定存在边缘，该边缘的权重值在连接所

13、有顶点v和w之间的边缘中取最小的值。 之后，继续向生成树追加顶点，直到生成树中包含n个顶点为止。 普里姆算法的基本思想：31，PPT学习交流，步骤： (1)初始时，U=v0，边集合TE=； (2)在所有的v0U、wV-U的边中选择权重最小的边，将该边作为(v0，w )的(3)te加上边(v0，w )，在u上加上w，从V-U中删除w，反复进行(2)、(3)直到成为(4)u=v为止。 32、PPT学习交流，(1)棱镜算法的例子，例1使用棱镜算法构建图g的最小生成树。 最小生成树为T(U，TE )，图G(V )， 假设e )，如下构成： 33，PPT学习通信，步骤1 :初始状态，Uv1 TE=V-U

14、=v2，v3，v4，v5，v6，(1)算法示例，34，PPT学习通信，步骤2 :uv 棱镜算法示例，35，PPT学习通信，步骤3 :Uv1，v3，v6 V-U=v2，v4，v5，(1)棱镜算法示例，36，PPT学习通信，步骤4 :Uv1，v3，v6，v4 v - PPT学习通信，步骤5 :Uv1，v3 v6，v4，v2 V-U=v5，(1)算法示例，38，PPT学习通信，步骤6 :Uv1，v2，v3，v4，v5，v6 UV，结束，(1)步骤struct VertexType adjvex，在算法的实现中设置辅助数组closedege，对于当前V-U集合的各顶点，记录与顶点集合u的顶点连接成本最

15、小的边； /U集的邻接顶点编号VRType lowcost； /边的权重closedgeMAX_VERTEX_NUM； 40，PPT学习交流，例如：得到的生成树加权值和=148351621=67，41，PPT学习交流，a，e，d，c，b，a，a，a，19，14，18，14，例如：e，12，e，8，14 5、得到的生成树权重值和=148351621=67，42，PPT学习交流，例2:a，e，d，c，b，g，f，14，8，5，3，16，21，得到的生成树的权重和，43， 用PPT学习交流void MiniSpanTree_P (MGraph G，vertextypeu)/prim算法从顶点u出发，网络g的最小生成树/网络g用邻接矩阵表示k=LocateVex(G，u )，max=100； for (j=0； PR.PS num； j ) /辅助数组初始化if (j！=k ) closedgej=u，G.arcskj.adj； 关闭gek.low cost=0； /初期，电视TV=u for (i=1； PS PS； i ) for (n=1； n G.vexnum； I )关