第八章图 教学内容:8.1图的基本概念 8.2图的存储表示 8.3图的遍历 8.4图的连通性 8.5最小生成树 8.6最短路径 8.7有向无环图及其应用 2教学目的:(理解图的基本概念及术语 2)掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法 (3)熟练掌握图的两种遍历的算法思想、步骤 (4)理解最小生成树的概念,能按Prim算法构造最小生成树 ⑤5领会并掌握拓扑排序、关键路径、最短路径的算法思想。 3教学重点:(1理解图的定义、术语及其含义: (2)掌握各种图的邻接矩阵表示法及其类型说明 ③3理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法 4领会生成树和最小生成树的概念 (5)掌握由Pim算法思想构造最小生成树按Pim算法思想 (6)领会拓扑序列和拓扑排序的概念 (7)理解并掌握拓扑排序的算法思想 ⑧)理解并掌握关键路径的算法思想: (9)理解并掌握最短路径的算法思想 4.教学难点:(正确理解与区别图的常用术语 (2)区别图的两种存储结构的不同点及其应用场合 (3)关键路径的算法思想 (4)最短路径的算法思想 5学时安排:12学时 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 1 第八章 图 ⒈教学内容：8.1 图的基本概念 8.2 图的存储表示 8.3 图的遍历 8.4 图的连通性 8.5 最小生成树 8.6 最短路径 8.7 有向无环图及其应用 ⒉教学目的：⑴理解图的基本概念及术语； ⑵掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法； ⑶熟练掌握图的两种遍历的算法思想、步骤； ⑷理解最小生成树的概念，能按Prim算法构造最小生成树； ⑸领会并掌握拓扑排序、关键路径、最短路径的算法思想。 ⒊教学重点：⑴理解图的定义、术语及其含义； ⑵掌握各种图的邻接矩阵表示法及其类型说明； ⑶理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法； ⑷领会生成树和最小生成树的概念； ⑸掌握由Prim算法思想构造最小生成树按Prim算法思想； ⑹领会拓扑序列和拓扑排序的概念； ⑺理解并掌握拓扑排序的算法思想； ⑻理解并掌握关键路径的算法思想； ⑼理解并掌握最短路径的算法思想。 ⒋教学难点：⑴正确理解与区别图的常用术语； ⑵区别图的两种存储结构的不同点及其应用场合； ⑶关键路径的算法思想； ⑷最短路径的算法思想。 ⒌学时安排： 12学时
81图的基本概念 ◆图的定义和术语 ◆图的基本操作 ☆ ☆ 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 2 8.1 图的基本概念 图的定义和术语 图的基本操作
8.1.1图的定义和术语 4.图的定义 图( Graph)是由非空的顶点集合和一个描述顶点之间关 系一边(或者弧)的集合组成,其形式化定义为 G=(V, E V={ilv∈ dataobject},E={(ⅵi)ⅵ,ⅵ∈V∧P(ⅵ,)} 其中,G表示一个图,V是图G中顶点的集合,E是图G中边 的集合,集合E中P(V)表示顶点ⅵ和顶点v之间有一条直接 连线,即偶对(V)表示一条边 2 2021年1月21日 无向图G1
2021年1月21日 数据结构讲义 3 8.1.1 图的定义和术语 1．图的定义 图(Graph)是由非空的顶点集合和一个描述顶点之间关 系——边（或者弧）的集合组成，其形式化定义为： G＝（V，E） V＝{vi| vi∈dataobject}，E＝{( vi,vj)| vi, vj ∈V ∧P(vi, vj)} 其中，G表示一个图，V是图G中顶点的集合，E是图G中边 的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接 连线，即偶对(vi,vj)表示一条边
2图的相关术语 (1)无向图。在一个图中,如果任意两个顶点构成的偶对 中(v)∈E是无序的,即顶点之间的连线没有方向,则 称该图为无向图。如前图所示是一个无向图G1 2有向图。在一个图中,如果任意两个顶点构成的偶对 (v,v)∈E是有序的,即顶点之间的连线是有方向的, 则称该图为有向图。如下图所示是一个有向图G2:G2 (V2,E2) 有向图G2 2021年1月21日
2021年1月21日 数据结构讲义 4 2.图的相关术语 ⑴无向图。在一个图中，如果任意两个顶点构成的偶对 （vi, vj）∈E是无序的，即顶点之间的连线没有方向，则 称该图为无向图。如前图所示是一个无向图G1。 ⑵有向图。在一个图中，如果任意两个顶点构成的偶对 （vi, vj）∈E是有序的，即顶点之间的连线是有方向的， 则称该图为有向图。如下图所示是一个有向图G2：G2= (V2,E2)
(3)顶点、边、弧、弧头、弧尾。图中,数据元素ⅵ称为顶」 点 (vertex);P(vi,y)表示在顶点v和顶点v之间有一条直接连 线。如果是在无向图中,则称这条连线为边;如果是在有向 图中,一般称这条连线为弧。边用顶点的无序偶对(ⅵy) 来表示,称顶点ⅵ和顶点y互为邻接点,边(ⅵ,v)依附于 顶点v与顶点v;弧用顶点的有序偶对<vy来表示,有序 偶对的第一个结点v被称为始点(或弧尾),在图中就是不 带箭头的一端;有序偶对的第二个结点ⅵ被称为终点(或弧 头),在图中就是带箭头的一端。 (4)无向完全图。在一个无向图中,如果任意两顶点都有一 条直接边相连接,则称该图为无向完全图。可以证明,在 个含有n个顶点的无向完全图中,有n(n1)2条边 (5)有向完全图。在一个有向图中,如果任意两顶点之间都 有方向互为相反的两条弧相连接,则称该图为有向完全图 在一个含有n个顶点的有向完全图中,有n(n-1)条边 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 5 ⑶顶点、边、弧、弧头、弧尾。图中，数据元素vi称为顶 点(vertex )；P(vi, vj)表示在顶点vi和顶点vj之间有一条直接连 线。如果是在无向图中，则称这条连线为边；如果是在有向 图中，一般称这条连线为弧。边用顶点的无序偶对（vi, vj） 来表示，称顶点vi和顶点vj互为邻接点，边（vi, vj）依附于 顶点vi与顶点vj；弧用顶点的有序偶对<vi, vj>来表示，有序 偶对的第一个结点vi被称为始点（或弧尾），在图中就是不 带箭头的一端；有序偶对的第二个结点vj被称为终点（或弧 头），在图中就是带箭头的一端。 ⑷无向完全图。在一个无向图中，如果任意两顶点都有一 条直接边相连接，则称该图为无向完全图。可以证明，在一 个含有n个顶点的无向完全图中，有n(n-1)/2条边。 ⑸有向完全图。在一个有向图中，如果任意两顶点之间都 有方向互为相反的两条弧相连接，则称该图为有向完全图。 在一个含有n个顶点的有向完全图中，有n(n-1)条边