数据结构第7节 图3.ppt

例1：深度优先遍历图G，并写出深度优先遍历序列。 序列1： V1,V2,V4,V8,V5,V3,V6,V7 序列2： V1,V2,V5,V8,V4,V3,V7,V6 深度优先遍历序列????? 对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或DFS序列。 ⒈一个图的DFS序列不一定惟一; ⒉源点和存储结构的内容均已确定的图的DFS序列惟一。 ⑴ 邻接矩阵表示的图确定源点后，DFS序列惟一； ⑵只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列 例1：广度优先遍历图G，并写出广度优先遍历序列。 广度优先遍历序列： V1,V2,V3,V4,V5,V6,V7,V8 例6： ⑴画出该网的邻接矩阵。 ⑵根据画出的邻接矩阵存储结构，从顶点1出发，分别进行深度优先遍历和广度优先遍历； 上述问题等价于： 构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和” 最小。 求最小生成树的两个算法： 普里姆算法：适用于求边稠密的网的最小生成树。 克鲁斯卡尔算法：适用于求边稀疏的网的最小生成树。 (1)普里姆算法举例 例1 使用普里姆算法为图G构造最小生成树。 (1)普里姆算法举例 (1)普里姆算法举例 (1)普里姆算法举例 (1)普里姆算法举例 (1)普里姆算法举例 (1)普里姆算法举例 练习题1 使用普里姆算法为图G构造一棵最小生成树。 练习题2 使用普里姆算法为图G构造一棵最小生成树。 (2)克鲁斯卡尔算法 (2)克鲁斯卡尔算法 (2)克鲁斯卡尔算法 (2)克鲁斯卡尔算法 (2)克鲁斯卡尔算法 (2)克鲁斯卡尔算法 (2)克鲁斯卡尔算法 练习题1 使用克鲁斯卡尔算法为图G构造一棵最小生成树。 练习：求图G的最小生成树（详细步骤） 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n 个顶点为止。 普里姆算法的基本思想: V2 V0 V3 V5 V4 V1 3 6 5 2 1 6 5 5 4 6 步骤： (1)初始时， U={v0}，边集合TE= ? ； (2)在所有 v0?U 、w?V-U的边中选择一条权值最小的边，设这条边为（v0, w）； (3)将边 (v0,w) 加入TE，同时将w 加入U中，而把w从V-U中删掉； (4)重复(2)、(3)，直到U=V为止。 V3 V1 V4 V6 V5 V2 3 6 5 2 1 6 5 5 4 6 设最小生成树为： T＝( U，{ TE } ) 图 G＝( V, {E} ) 构造步骤如下： 步骤 1 ：初始状态 U＝{v1} TE= ? V-U={v2,v3,v4,v5,v6} V1 V3 V1 V4 V6 V5 V2 3 6 5 2 1 6 5 5 4 6 图 G＝( V, {E} ) 步骤 2 ： V3 V1 1 U＝{v1,v3} V-U= {v2,v4,v5,v6} V3 V1 V4 V6 V5 V2 3 6 5 2 1 6 5 5 4 6 图 G＝( V, {E} ) 步骤 3 ： V3 V1 V6 1 4 U＝{v1, v3, v6} V-U= {v2,v4,v5} V3 V1 V4 V6 V5 V2 3 6 5 2 1 6 5 5 4 6 图 G＝( V, {E} ) 步骤 4 ： U＝{v1, v3, v6,v4} V-U= {v2,v5} V3 V1 V4 V6 1 4 2 V3 V1 V4 V6 V5 V2 3 6 5 2 1 6 5 5 4 6 图 G＝( V, {E} ) 步骤 5 ： U＝{v1, v3, v6,v4,v2} V-U= {v5} V3 V1 V4 V6 V2 1 4 2 5 V3 V1 V4 V6 V5 V2 3 6 5 2 1 6 5 5 4 6 图 G＝( V, {E} ) 步骤 6 ： U＝{v1,v2,v3,v4,v5,v6} U＝V，结束 V3 V1 V4 V6 V5 V2 1 4 2 5 3 V3 V1 V4 V6 V5 V2 3 6 5 2 1 6 5 5 4 6 图 G＝( V, {E} ) 在算法实现中设置一个辅助数组 closedege，对当前 V-U 集合中的每个顶点，记录和顶点集 U 中顶点相连接的代价最小的边； struct { VertexType adjvex; // U集中的相邻顶点序号 VRT