最小支撑树 0.5小时 图知识点总结0.5小时 4.重点和难点 (1)图的存储结构以及各种存储结构的优缺点 (2)图的周游算法。 (3)解决图的最短路径问题的各种算法。 (4)图的最小支撑树的两种典型算法:Pim算法和 Kruskal算法 5.授课提示 采用灵活的教学方式,通过提出问题、分析问题、解决问题这样的基本流程,加深学生 对重难点知识的理解,并培养其创新意识和创新能力 下面是图这一章的重点和难点内容的讲授注意事项 (1)邻接表、十字链表 邻接表 adjacency list)表示法是一种链式存储结构,由一个顺序存储的顶点表和n个链 接存储的边表组成。顶点表目有两个域:顶点数据域和指向此顶点边表指针域。边表把依附 于同一个顶点v的边(即相邻矩阵中同一行的非0元素)组织成一个单链表。边表中的每 一个表目都代表一条边,由两个主要的域组成:与顶点v1邻接的另一顶点的序号、指向边 表中下一个边表目的指针。 十字链表( Orthogonal list)是有向图的另一种链式存储结构,可以看成是邻接表和逆 邻接表的结合。表中对应于有向图的每一条弧有一个表目,共有5个域:头 headvex)和尾 ( tailvex)分别表示弧头(终点)和弧尾(始点)顶点序号; tailnextarc链接指针指向下一条顶 点以 tailvex为弧尾的弧; headnextarc指针指向下一条以顶点 headvex为弧头的弧;此外还 有一个表示弧权值等信息的 info域。顶点表目由3个域组成:data域存放顶点的相关信息 firstinarc链接指针指向第一条以该顶点为终点的弧; firstoutarc链接指针指向第一条以该顶 点为始点的弧。所有的顶点也可以放在顺序存储结构中 图的存储结构这一部分,需要多用图片进行展示。 (2)深度优先周游 深度优先周游方法的特点是尽可能先对纵深方向进行搜索。 对于给定的图G=<V,E,初始状态是V中的所有顶点都未被访问。首先选取一个顶 点开始搜索。设v∈V是源点,访问顶点vo并标记为Ⅴ SITED,然后访问v邻接到的未被 访问过的顶点ⅵ1,再从v出发递归地按照深度优先的方式周游。当遇到一个所有邻接顶点 都被访问过了的顶点w时,则回到己访问顶点序列中最后一个拥有未被访问的相邻顶点的 顶点u,再从u出发递归地按照深度优先的方式周游。重复上述过程直至从v0出发的所有边 都已检测过为止,此时,图中所有由源点有路径可达的顶点都己被访问过。若图G是连通 图,则周游过程结束;否则选择一个尚未访问的顶点作为新的源点进行深度优先搜索,直至2 最小支撑树 0.5 小时 图知识点总结 0.5 小时 4．重点和难点 （1） 图的存储结构以及各种存储结构的优缺点。 （2） 图的周游算法。 （3） 解决图的最短路径问题的各种算法。 （4） 图的最小支撑树的两种典型算法：Prim 算法和 Kruskal 算法。 5．授课提示 采用灵活的教学方式，通过提出问题、分析问题、解决问题这样的基本流程，加深学生 对重难点知识的理解，并培养其创新意识和创新能力。 下面是图这一章的重点和难点内容的讲授注意事项。 （1）邻接表、十字链表 邻接表(adjacency list)表示法是一种链式存储结构，由一个顺序存储的顶点表和 n 个链 接存储的边表组成。顶点表目有两个域：顶点数据域和指向此顶点边表指针域。边表把依附 于同一个顶点 vi 的边（即相邻矩阵中同一行的非 0 元素）组织成一个单链表。边表中的每 一个表目都代表一条边，由两个主要的域组成：与顶点 vi 邻接的另一顶点的序号、指向边 表中下一个边表目的指针。 十字链表（Orthogonal List）是有向图的另一种链式存储结构，可以看成是邻接表和逆 邻接表的结合。表中对应于有向图的每一条弧有一个表目，共有 5 个域：头(headvex)和尾 (tailvex)分别表示弧头（终点）和弧尾（始点）顶点序号；tailnextarc 链接指针指向下一条顶 点以 tailvex 为弧尾的弧；headnextarc 指针指向下一条以顶点 headvex 为弧头的弧；此外还 有一个表示弧权值等信息的 info 域。顶点表目由 3 个域组成：data 域存放顶点的相关信息； firstinarc 链接指针指向第一条以该顶点为终点的弧；firstoutarc 链接指针指向第一条以该顶 点为始点的弧。所有的顶点也可以放在顺序存储结构中。 图的存储结构这一部分，需要多用图片进行展示。 （2）深度优先周游 深度优先周游方法的特点是尽可能先对纵深方向进行搜索。 对于给定的图 G = <V，E>，初始状态是 V 中的所有顶点都未被访问。首先选取一个顶 点开始搜索。设 v0∈V 是源点，访问顶点 v0 并标记为 VISITED，然后访问 v0邻接到的未被 访问过的顶点 v1，再从 v1 出发递归地按照深度优先的方式周游。当遇到一个所有邻接顶点 都被访问过了的顶点 w 时，则回到已访问顶点序列中最后一个拥有未被访问的相邻顶点的 顶点 u，再从 u 出发递归地按照深度优先的方式周游。重复上述过程直至从 v0 出发的所有边 都已检测过为止，此时，图中所有由源点有路径可达的顶点都已被访问过。若图 G 是连通 图，则周游过程结束；否则选择一个尚未访问的顶点作为新的源点进行深度优先搜索，直至