第5单元非线性数据结构图主讲：刘志强

第5单元非线性数据结构图主讲：刘志强内容摘要：

•起始顶点 V1 V1 •访问 V1的未被访问过的 所有邻接点 V3,V2,V4 （ V1,V3） (V1,V2) (V1,V4) •访问 V3的未被访问过 的所有的邻接点 V5 （ V3,V5） •访问 V2的未被访问过 的所有的邻接点 无 •访问 V4的未被访问过 的所有的邻接点 V6 (V4,V6) •所有顶点已被访问 ,结束。 V1 V3 V5 V4 V6 G6 V2 示例 下一页 上一页 停止放映 第 37 页 遍历产生的结果 广度优先遍历 G6所走过的序列： V1 V3  V2  V4  V5  V6 所走过的边： （ V1， V3） ， （ V1， V2） ， （ V1， V4） ， （ V3，V5） ， （ V4， V6） 遍历生成树 V1 V3 V5 V2 V4 V6 下一页 上一页 停止放映 第 38 页 程序举例 图的深度优先遍历和广度优先遍历。 V1 V3 V5 V4 V6 G6 V2 深度优先遍历序列： V1 V3 V5 V2 V4 V6 广度优先遍历序列： V1 V3 V2 V4 V5 V6 1 3 2 4 G2 深度优先遍历序列： 1 3 4 2 广度优先遍历序列： 1 3 2 4 示例 下一页 上一页 停止放映 第 39 页 四、图的操作 图中顶点无序可言 任一顶点都可以看作第一个顶点； 任一顶点的邻接点间也无序可言； 为操作方便 ， 对图中顶点按人为意志给其排序；同样 ， 也可以对某个顶点的所有邻接点进行排队 ， 在这个队列中自然形成第一个或第 K个邻接点。 若某个顶点的邻接点个数大于 K， 则称第 K+1个邻接点为第 K个邻接点的下一个邻接点 ， 而最后一个邻接点的下一个邻接点为 ‚ 空 ‛。 下一页 上一页 停止放映 第 40 页 图的常用基本操作 LOC_VERTEX（ G， Vi） 确定顶点 Vi在 G中的位置。 GET_VERTEX（ G， i） 求图 G中第 i个顶点。 FIRST_VERTEX（ G， i） 求图 G中 Vi的第 1个邻接点。 NEXT_ADJ(G,v,w) 已知 w为 G中顶点 v的第 1个邻接点 ,求顶点 w的下一个邻接点。 INS_VERTEX(G,u) 在图 G中插入一个顶点 u,为图 G的第 n+1个顶点。 INS_ARC(G,v,w) 在图 G中插入一条从顶点 v到顶点 w的弧。 DEL_VERTEX(G,Vi) 删除图 G中顶点 Vi,以及与 Vi相关联的边或弧。 DEL_ARC(G,v,w) 删除图 G中从顶点 v到顶点 w的弧。 下一页 上一页 停止放映 第 41 页 五、图的应用 最小生成树 拓扑排序 关键路径 最短路径 下一页 上一页 停止放映 第 42 页 图的应用实例  [生成树 ] 设 G= (V,E)是一个无向图，当且仅当 G中每一对顶点之间有一条路径时，可认为 G是连通的（ connected）。  一个 n节点的连通图必须至少有 n 1条边。 因此当通信网络的每条链路具有相同的建造费用时，在任意一棵生成树上建设所有的链路可以将网络建设费用减至最小，并且能保证每两个城市之间存在一条通信路径。 如果链路具有不同的耗费，那么需要在一棵最小耗费生成树上建立链路。 下一页 上一页 停止放映 第 43 页 图的应用实例 下一页 上一页 停止放映 第 44 页 最小生成树 该问题是构造连通图的最小代价生成树问题。 一棵生成树的代价就是树上各边 （ 弧 ）的代价之和。 例如 ， 若要在 n个城市间建立通信联络网 ，则只需 n1条线路。 但在 n个城市间 ， 最多可能架设 n（ n1） /2条线路 ， 选择哪 n1条线路 ， 使费用最少。 普里姆 （ Prim） 算法 克鲁斯卡尔 （ Kruskal） 算法 下一页 上一页 停止放映 第 45 页 普里姆（ Prim）算法 假设 N=（ V， E） 是连通图 ， TE是 N上最小生成树中边的集合。 从 U={u0} （ u0  V） ， TE= 空开始； 重复执行： 在所有 uU， v VU的边 （ u， v）E中找一条代价最小的边 （ u0， v0） 并入TE， 同时 u0并入 U， 直到 U=V为止； 此时 TE中必有 n1条边 ， 则 T=（ V， TE） 为 N的最小生成树。 下一页 上一页 停止放映 第 46 页 普里姆（ Prim）算法举例 1 2 3 4 5 6 8 7 2 1 4 3 5 7 6 8 11 10 9 12 U={1}， VU={2， 3， 4， 5， 6， 7， 8} 1 2 2 1 2 4 2 1 4 7 3 （ 1） （ 2） （ 3） (1) U={1,2},VU={3,4,5,6,7,8} (2) U={1,2,4},VU={3,5,6,7,8} (3) U={1,2,4,7},VU={3,5,6,8} 例子 下一页 上一页 停止放映 第 47 页 普里姆（ Prim）算法举例 (续 ) 4 7 5 3 5 （ 4） 7 6 （ 5） 6 (4) U={1,2,4,7,5} , VU={3,6,8} (5) U={1,2,4,7,5,6}, VU={3,8} (6) U={1,2,4,7,5,6,3}, VU={8} (7) U={1,2,4,7,5,6,3,8), VU={ } 4 3 （ 7） 8 3 6 5 4 7 2 2 1 3 6 5 8 9 1 5 5 （ 6） 4 7 6 3 6 3 5 5 8 下一页 上一页 停止放映 第 48 页 克鲁斯卡尔（ Kruskal）算法 操作步骤 : – 假设 N=（ V， E） 是连通图 – 取图中每个顶点自成一个连通分量 – 在 { E }中选择代价最小的边 ， 若该边所依附的顶点落在 T中不同的连通分量上 ， 则将此边加入生成树 T中；否则 ， 舍去此边 ， 再选择下一条代价最小的边。 – 重复上述步 ， 直到 T中所有顶点都在同一连通分量上为止。 下一页 上一页 停止放映 第 49 页 克鲁斯卡尔（ Kruskal）算法举例 1 2 3 4 5 6 1 5 2 4 6 6 3 5 5 6 2 5 1 3 4 6 1 2 3 (4) 1 3 1 4 6 2 (3) 1 2 3 4 5 6 (1) 1 3 (2) 1 下一页 上一页 停止放映 第 50 页 克鲁斯卡尔（ Kruskal）算法举例 (续） 1 2 3 4 5 6 (5) 1 2 3 4 1 2 3 4 5 6 1 5 2 4 6 6 3 5 5 6 1 3 2 5 6 4 1 2 4 3 5 （ 6） 下一页 上一页 停止放映 第 51 页 拓扑排序 研究一个有机整体中不同个体间的次序问题。 例如课程间优先关系有向图问题。 软件专业的课程优先关系： 课程编号 课程名称 先决条件 C1 程序设计基础 无 C2 离散数学 C1 C3 汇编语言 C1， C2 …… C9 高等数学 无 下一页 上一页 停止放映 第 52 页 拓扑排序举例 方法步骤 在有向图中选一个没有前驱的顶点并输出。 从图中删除该顶点和所有以它为尾的弧。 重复前 2步 ,直到全部顶点均输出为止。 输出序列即为拓扑排序序列。 拓扑排序序列不唯一。 下一页 上一页 停止放映 第 53 页 拓扑排序举例 C1 C9 C4 C2 C3 C5 C7 C12 C10 C11 C6 C8 •C1 C2 C3 C4 C5 C7 C9 C10 C11 C6 C12 C8 •C9 C10 C11 C6 C1 C12 C4 C2 C3 C5 C7 C8 例子 1 2 3 4 5 6 下一页 上一页 停止放映 第 54 页 关键路径 研究的是在一个有机整体中不同个体间的次序问题 ， 即研究的是工程进度及影响进度的关键因素问题。 下一页 上一页 停止放映 第 55 页 图的应用实例  [路径问题 ] 城市中有许多街道，每一个十字路口都可以看作图中一个顶点，邻接两个十字路口之间的每一段街道既可以看作一条，也可以看作两条有向边。 如果街道是双向的，就用两条有向边。 如果街道是单向的，就用一条有向边。 (路线咨询 ) 下一页 上一页 停止放映 第 56 页 最短路径 研究的是类似于交通调度一类的带权有向图问题。 求路径最短或费用最省。 从源到其余各顶点的最短路径 图中 7个顶点 、 13条弧。 Floyd算法。 例子 1 2 3 4 5 6 7 2 4 1 3 2 3 4 7 6 9 8 5 9 下一页 上一页 停止放映 第 57 页 最短路径问题描述  设下一条最短路的终点为 vk，则这条路径或者是 (v,vk) 或者是 （ v,vj,vk） 它的长度或者是从 v到 vk的弧的权值，或者是 disk[j]和从 vj到 vk的弧上的权值之和。 下一页 上一页 停止放映 第 58 页 最短路径算法描述 （ 1）假设用带权的邻接矩阵 cost来表示带权有向图，cost[i,j]表示弧。