将书本上的理论知识与最前沿的技术知识融为一体,设计验证型、探索型、应用型的 实习题和上机题,帮助同学更好的理解书本上的基本原理,锻炼学生的思维能力、实践能力。 图这一章可以安排8-10道书面作业,1-2道综合上机实习题。安排一次习题讲评。 例如:算法方面的考察 (1)写出一个算法确定一个有n个顶点e条边的图(有向图或者无向图)是否包含回 路,所设计的算法的时间代价应该是O(n+e) (2)设计算法找图(有向图或无向图)的所有连通分量(对于有向图则是强连通分 量)。提示:第一个连通分量的所有顶点使用第一分量的标记,第二个连通分量的所有 顶点使用第二分量的标记,依此类推。 (3)设计一个程序,输入一个图(有向图或者是无向图)G=<VE>以及一对顶点v v∈V,输出的结果是:如果从v到v存在一条简单路径,则输出从v到v所有简单路 径:如果不存在,则输出空 .教学案例 构造最小生成树的Prim算法 设G=<V,E>是一个联通的带权图,其中V是顶点的集合,E是边的集合,TE为最小 生成树的边的集合。则Prim算法通过以下步骤得到最小生成树 (1)初始状态:U={uo},TE={}。其中υ是顶点集合Ⅴ中的某一个顶点 (2)在所有u∈U,v∈VU的边(uv)∈E中找一条权值最小的边(u,vo),将这条边加进 集合TE中,同时将此边的另一顶点v并入U。这一步骤的作用是在边集E里找一条两个 顶点分别在集合U和VU中且权值最小的边,把这条边添加到边集TE中,并把这条边上 不在U中的那个顶点加入到U中。 (3)如果U=V,则算法结束:否则重复步骤2。 算法结束时,TE中包含了G中的n-1条边。经过上述步骤选取到的所有边恰好就构成 了图G的一棵最小生成树 例如,对于左图中的带权图,按照Prim算法选取边的过程如右图所示。5 将书本上的理论知识与最前沿的技术知识融为一体，设计验证型、探索型、应用型的 实习题和上机题，帮助同学更好的理解书本上的基本原理，锻炼学生的思维能力、实践能力。 图这一章可以安排 8-10 道书面作业，1-2 道综合上机实习题。安排一次习题讲评。 例如：算法方面的考察 （1） 写出一个算法确定一个有 n 个顶点 e 条边的图（有向图或者无向图）是否包含回 路，所设计的算法的时间代价应该是 O(n+e)。 （2） 设计算法找图（有向图或无向图）的所有连通分量（对于有向图则是强连通分 量）。提示：第一个连通分量的所有顶点使用第一分量的标记，第二个连通分量的所有 顶点使用第二分量的标记，依此类推。 （3） 设计一个程序，输入一个图（有向图或者是无向图）G = <V, E>以及一对顶点 vi、 vj∈V，输出的结果是：如果从 vi到 vj 存在一条简单路径，则输出从 vi到 vj 所有简单路 径；如果不存在，则输出空。 7．教学案例 构造最小生成树的 Prim 算法 设 G = <V，E>是一个联通的带权图，其中 V 是顶点的集合，E 是边的集合，TE 为最小 生成树的边的集合。则 Prim 算法通过以下步骤得到最小生成树： (1) 初始状态：U = {u0}，TE = {}。其中 u0是顶点集合 V 中的某一个顶点。 (2) 在所有 u∈U，v∈V-U 的边(u,v)∈E 中找一条权值最小的边(u0，v0)，将这条边加进 集合 TE 中，同时将此边的另一顶点 v0 并入 U。这一步骤的作用是在边集 E 里找一条两个 顶点分别在集合 U 和 V-U 中且权值最小的边，把这条边添加到边集 TE 中，并把这条边上 不在 U 中的那个顶点加入到 U 中。 (3) 如果 U = V，则算法结束；否则重复步骤 2。 算法结束时，TE 中包含了 G 中的 n-1 条边。经过上述步骤选取到的所有边恰好就构成 了图 G 的一棵最小生成树。 例 如 ， 对 于 左 图 中 的 带 权 图 ， 按 照 Prim 算 法 选 取 边 的 过 程 如 右 图 所 示