8935教学目标

8935教学目标内容摘要：

} if( top !=1) { v=stack[top]。 top。 p=G[v].firstarc。 p=pnextarc。 } } } } 广度优先遍历算法  广度优先遍历法类似于树的按层次遍历的过程。 即先访问第 1个顶点所有邻接点后，再访问下一个顶点所有未被访问的邻接点。  算法思想： – step1 从图中某个顶点 V0出发，并访问此顶点； – step2 从 V0出发，访问 V0的各个未曾访问的邻接点 W1， W2， … ,Wk。 然后 ,依此从W1,W2,… ,Wk出发访问各自未被访问的邻接点。 – step3 重复 step2，直到全部顶点都被访问为止。 广度优先遍历法举例 遍历过程 访问顶点 所过边 •起始顶点 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 示例 遍历产生的结果  广度优先遍历 G6所走过的序列： V1 V3  V2  V4  V5  V6  所走过的边： （ V1， V3） ， （ V1， V2） ， （ V1， V4） ， （ V3， V5） ， （ V4， V6）  遍历生成树 V1 V3 V5 V2 V4 V6 四、图的操作  图中顶点无序可言 – 任一顶点都可以看作第一个顶点； – 任一顶点的邻接点间也无序可言；  为操作方便 ， 对图中顶点按人为意志给其排序；同样 ， 也可以对某个顶点的所有邻接点进行排队 ， 在这个队列中自然形成第一个或第 K个邻接点。 若某个顶点的邻接点个数大于 K， 则称第 K+1个邻接点为第 K个邻接点的下一个邻接点 ， 而最后一个邻接点的下一个邻接点为 “ 空 ”。 图的常用基本操作  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的弧。 五、图的应用  最小生成树  拓扑排序  关键路径  最短路径 最小生成树  该问题是构造连通图的最小代价生成树问题。 一棵生成树的代价就是树上各边 （ 弧 ） 的代价之和。  例如 ， 若要在 n个城市间建立通信联络网 ， 则只需 n1条线路。 但在 n个城市间 ， 最多可能架设 n（ n1） /2条线路 ， 选择哪 n1条线路 ， 使费用最少。 – 普里姆 （ Prim） 算法 – 克鲁斯卡尔 （ Kruskal） 算法 普里姆（ 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的最小生成树。 普里姆（ 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} 普里姆（ Prim） 算法举例 (续 ) 4 7 5 3 5 （ 4） 7 6 （ 5） 6 （ 6） 4 7 6 3 8 （ 7） 8 3 6 5 4 7 2 2 1 3 6 5 8 9 (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 6 3 1 克鲁斯卡尔（ Kruskal）算法  操作步骤 : – 假设 N=（ V， E） 是连通图 – 取图中每个顶点自成一个连通分量 – 在 { E }中选择代价最小的边 ， 若该边所依附的顶点落在 T中不同的连通分量上 ，则将此边加入生成树 T中；否则 ， 舍去此边 ， 再选择下一条代价最小的边。 – 重复上述步 ， 直到 T中所有顶点都在同一连通分量上为止。 克鲁斯卡尔（ 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 克鲁斯卡尔（ 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） 拓扑排序  研究一个有机整体中不同个体间的次序问题。 例如课程间优先关系有向图问题。  软件专业的课程优先关系： 课程编号 课程名称 先决条件 C1 程序设计基础 无 C2 离散数学 C1 C3 汇编语言 C1， C2 …… C9 高等数学 无 拓扑排序举例  方法步骤 – 在有向图中选一个没有前驱的顶点并输出。 – 从图中删除该顶点和所有以它为尾的弧。 – 重复前 2步 ,直到全部顶点均输出为止。 – 输出序列即为拓扑排序序列。  拓扑排序序列不唯一。 拓扑排序举例 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 关键路径  研究的是在一个有机整体中不同个体间的次序问题。 即研究的是工程进度及影响进度的关键因素问题。 最短路径  研究的是类似于交通调度一类的带权有向图问题。 求路径最短或费用最省。 六、二叉排序树的生成 对给定数列 {a1， a2， … ,an},根据二叉排序树特性 ,逐个将结点插入到二叉排序中。 具体操作步骤： step1 a1是根结点； step2 若 aiaj ,且 aj的左子为空 ,则将 ai插入到 aj的左子。 若 aj的左子非空 ,则继续寻找合适的插入位置。 若 aiaj， 且 aj的右子为空 ， 则将 ai插入到 aj的右子；否则继续沿右子树寻找合适的插入位。