《《数据结构[Python语言描述]》教案第13课图（7.1-7.3）.docx》由会员分享，可在线阅读，更多相关《《数据结构[Python语言描述]》教案第13课图（7.1-7.3）.docx（8页珍藏版）》请在三一办公上搜索。
1、课题第13课图(7.1-7.3)课时2课时(90min)教学目标知识目标：(1)理解图的定义、基本术语和基本操作(2)掌握图的两种存储结构,包括邻接矩阵和邻接表(3)掌握图的深度优先遍历和广度优先遍历方法技能目标：能在邻接矩阵、邻接表中完成基本操作素质目标：强化学习意识，努力提高应用理论知识解决实际问题的能力教学重难点教学重点：图的基本术语和基本操作、图的两种存储结构、图的深度优先遍历和广度优先遍历方法教学睚点：图的两种存储结构、图的深度优先遍历和广度优先遍历方法教学方法问答法、讨论法、i并授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签
2、到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：什么是图形结构？【学生】思考、举手回答传授新知【教师】通过学生的回答引入要讲的知识，介绍图的定义、基本术语和基本操作，图的两种存储结构，图的深度优先遍历和广度优先遍历方法7.1 图概述7.1.1 图的定义图(graph)由顶点及描述顶点之间关系的边的有限集合组成，其形式化定义为G=(V,E)其中，V是图G中顶点的有限集合(顶点集)，记为V(G)；E是连接V中两个不同顶点的边的有限集合(边集)，记为E(G)eE(G)可以为空集，当E(G)为空集时，图G只有顶点而没有边。对于图G,如果其中的边为无向边，即两个顶点之间的边没有方向，则称图
3、G为无向图；如果其中的边为有向边，即两个顶点之间的边有方向，则称图G为有向图。在无向图中，顶点对通常用圆括号()括起来，以表示一条无向边。在有向图中，顶点对通常用尖括号”括起来，以表示一条有向边。【提示】在有向图中,又称为弧，其中W是弧尾，匕是弧头。7.1.2 图的基本术语1 .无向完全图和有向完全图对于一个无向图,如果图中任意两个顶点之间都存在一条边，则称该无向图为无向完全图。对于一个有向图，如果图中任意两个顶点之间都存在两条方向相反的边，则称该有向图为有向完全图。【高手点拨】具有n个顶点的无向完全图中共有n(n-l)2条边，具有n个顶点的有向完全图中共有n(n-l)条边。2 .子图对于两个
4、图G=(V,E)和=(VE,),如果V是V的子集，E是E的子集，则称图G是图G的子图。3 .稀疏图和稠密图有较少条边的图称为稀疏图，反之称为稠密图。4 .邻接点对于无向图G=(V,E),如果边(vO,vl)E,则称顶点v与顶点vl互为邻接点，即顶点VO与顶点Vl相邻接；同时称边WO,vl)依附于顶点Vo和顶点vl,或者说边(v,vl与顶点v和顶点Vl相关联。对于有向图G=(V,E),如果边E,则称顶点Vo邻接到顶点Vl,顶点Vl邻接自顶点v；同时称边VVo.vl依附于顶点v和顶点vl,或者说边与顶点v和顶点vl相关联。5 .顶点的度、入度和出度对于无向图，顶点V的度是指与顶点V相关联的边的数目
5、，记作TD(v).对于有向图，顶点V的度分为入度和出度。其中，入度是以顶点V为弧头的弧的数目，记作ID(V)；出度是以顶点V为弧尾的弧的数目，记作OD(V),因此，顶点V的度TD(V)=ID(V)+OD(v).6 .权和网在实际应用中，图的边往往具有一定意义且会被赋予相应的数值，该数值称为该边的权(也称为权值).这种带权的图称为网。7 .路径和路径长度对于图G=(V,E),从顶点V出发到达顶点的一条路径是一个顶点序列(v.v,vlvm,v)其中，若G为无向图，则边(v,vO)、(v,vl)(Vm,v)E；若G为有向图，则边E一条路径中经过的边的数目称为路径长度。8 .回路若一条路径中的开始顶点
6、和结束顶点相同，则称该路径为回路或环。9 .简单路径、简单回路或简单环顶点序列中顶点不重复出现的路径称为简单路径。除了开始顶点和结束顶点外，其余顶点不重复出现的回路称为简单回路或简单环。10 .连通、连通图和连通分量对于无向图G=(V,E),如果从顶点v到顶点V1有路径,则称顶点v和顶点V1是连通的。如果图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。无向图中的极大连通子图称为无向图的连通分量。【提示】在无向图中，若某一个连通子图不包含在其他连通子图内，则称该连通子图为极大连通子图。也就是说，与该连通子图中某顶点连通的所有顶点必包含在该连通子图中。显然，连通图的极大连通子图只
7、有其自身一个，而非连通图的极大连通子图有多个。H.强连通图和强连通分量对于有向图G=(V,E),如果从顶点v到顶点vlx从顶点vl到顶点v都有路径，则称图G为强连通图，否则称为非强连通图。有向图中的极大强连通子图称为有向图的强连通分量。12 .连通图的生成树一个连通图的生成树是指该连通图的一个极小连通子图，它含有图中的全部顶点(顶点个数为n),但只有足以构成一棵树的n-1条边。【提示】极小连通子图既要保证图的流畅，又要使图的边数最少。如果一个无向图有n个顶点和少于n-1条边，则该图是非连通图；如果一个无向图有n个顶点和多于n-1条边，则该图中一定有回路。值得注意的是，有n个顶点和n-1条边的图
8、不一定是生成树。13 1.3图的基本操作【教师】用多媒体展示“图基本操作的定义”表(详见教材)，井介绍图的基本操作7.2图的存储结构7.2.1 邻接矩阵1 .邻接矩阵表示法邻接矩阵表示法也称数组表示法，通常采用二维数组存储图中各顶点之间的邻接关系。(1)假设G=(KH是具有个顶点的图，则它的邻接矩阵是一个X的方阵，定义如下.1若或(斗,vz)EAfiI5=并5、cO若或(4,)任E(2)假设G=(Ua是具有0个顶点的网，则它的邻接矩阵是一个X”的方阵，定义如下。% Aij = ,若或,)E若或(4)E其中，Wjj表示顶点i和顶点J之间边的权值。图的邻接矩阵类的定义详见教材【教师】随机邀请学生回
9、答以下问题邻接矩阵表示法有什么特点？【学生】聆听、思考、回答+【教师】总结学生的回答，讲解“知识库”的相关知识(1)图的邻接矩阵是唯一的.(2)根据邻接矩阵很容易判断任意两个顶点之间是否有边，且时间复杂度为0(1)。(详见教材)2 .邻接矩阵中基本操作的实现1 )返回顶点在图中的位置该算法是根据顶点的值获取其在顶点集中的位置，若顶点不存在，则返回-1。【算法描述】defIocateVex(self,x):foriinrange(self.vNum):#查找顶点信息ifself.vi=x:#如果顶点的值为x,返回其位置returnireturn-1#否则返回-12 )创建图下面以创建无向网为例，
10、介绍创建图的方法，其具体步骤如下。(1)输入图的顶点数和边数。(2)依次输入顶点信息并将其存入顶点集中。(3)初始化邻接矩阵,将每条边的权值初始化为极大值(8).(4)构造邻接矩阵。依次输入每条边依附的顶点及边的权值，确定两个顶点在图中的位置后，为边赋相应的权值，同时为其对称边也赋相同的权值。【算法描述】详见教材3)输出图该算法是输出图的邻接矩阵。【算法描述】详见教材7.2.2邻接表1.邻接表表示法邻接表表示法是图的一种链式存储结构。在邻接表中，对图中的每个顶点建立一个单链表，将与该顶点相邻的顶点链接到该单链表中。邻接表中每个单链表的第一个结点(表头结点)存放有关顶点的信息，以便于随机访问任一
11、顶点的单链表，其余结点存放有关边的信息。(1)表头结点的结构如图所示。datafirstarc其中，data域用于存储顶点Vi的名称或其他信息，fi个结点.(2)边结点的结构如图(a)或图(b)所示.rstarc域用于指向单链表中除表头结点外的第一avexnextarcadjvexinfonextarc(a)无权图边结点的结构(b)有权图边结点的结构【教师】用多媒体展示“图的邻接表“图(详见教材)，并介绍图的邻接表特点对于无向图，邻接表中第/(Oin)个单链表中边结点的个数是顶点口的度；对于有向图，邻接表中第i(011-l)个单链表中边结点的个数是顶点1的出度，但要求顶点1的入度必须遍历整个邻
12、接表。为此，可以对每个顶点“建立f逆邻接表，即对每个顶点V,建立一个以顶点打为弧头的单链表。这样，在逆邻接表中第/(0n-l)个单链表中边结点的个数就是顶点,的入度。【知识库】邻接表表示法的特点如下。(1)图的邻接表是不唯一的。(2)在邻接表中，无法很快判断任意两个顶点之间是否有边，且最坏时间复杂度为O(n)(详见教材)2.邻接表中基本操作的实现1 )返回顶点在图中的位置该算法是根据顶点的值获取其在顶点集中的位置，若顶点不存在，则返回-1。【算法描述】详见教材2 )创建图下面以创建无向图为例，介绍创建图的方法，其具体步骤如下。(1)构造表头结点，初始化表头结点的指针域为Nonee(2)创建邻接
13、表。依次输入每条边依附的两个顶点，并确认顶点在图中的位置，然后插入边结点.【算法描述】详见教材【高手点拨】若要创建有向图，只需对上述算法进行简单修改，即仅需生成一个边结点，并将其插入表头结点后面。3)插入边结点该算法是指在单链表中插入一个顶点i指向顶点J的权值为e的边结点。【算法描述】详见教材【教师】讲解实例7-1(详见教材)7.3图的遍历+【教师】随机邀请学生回答以下问题图的遍历和树的遍历区别是什么？)【学生】聆听、思考、回答图的遍历是指从图中某一顶点出发依次访问图中所有顶点，且每个顶点仅被访问一次.7.3.1 深度优先遍历图的深度优先遍历类1以于树的先根遍历，其步骤如下。(1)从图中某个顶
14、点V出发，访问该顶点。(2)找出刚访问过的顶点的第一个未被访问的邻接点，访问该邻接点。以该邻接点为新顶点，重复步骤(2),直到刚访问过的顶点没有未被访问的邻接点。(3)退回到上一个访问过且还有未被访问的邻接点的顶点，继续访问该顶点的下一个未被访问的邻接点.(4)重复步骤(2)和步骤(3),直到图中所有顶点均被访问。【提示】上述深度优先遍历步骤是针对连通图的。若是非连通图,执行上述遍历步骤后,图中一定还有未访问过的顶点，此时，需要从图中选择一个未访问过的顶点作为起始点，重复上述深度优先遍历步骤，直到图中所有顶点均被访问.【算法描述】详见教材【教师】用多媒体展示“深度优先遍历无向”图(详见教材)，
15、并介绍深度优先遍历无向图的过程(1)从顶点A出发，首先访问顶点Ae(2)访问顶点Be(3)访问顶点C.(4)访问顶点D.(5)访问顶点Eq(6)访问顶点G。(7)访问顶点F。(详见教材)【提示】当进行深度优先遍历时，如果一个顶点有多个邻接点，可以任选其一，故图的深度优先遍历序列不是唯一的。也就是说，对于如图7-18所示的无向图，其深度优先遍历序列也可以为A、B、C、D、G、F、Ee7.3.2广度优先遍历图的广度优先遍历类1以于二叉树的层次遍历，其步骤如下。(1)从图中的某个顶点V出发，访问该顶点。(2)依次访问顶点V的所有未被访问过的邻接点。(3)分别从这些邻接点出发依次访问它们的邻接点，并使
16、先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问。(4)重复步骤(3),直到图中所有顶点均被访问.【提示】上述广度优先遍历步骤是针对连通图的。若是非连通图，执行上述遍历步骤后，图中一定还有未访问过的顶点，此时，需要从图中选择一个未访问过的顶点作为起始点，重复上述广度优先遍历步骤，直到图中所有顶点均被访问。（详见教材）【教师】用多媒体展示“广度优先遍历无向”图（详见教材），并介绍广度优先遍历无向图的过程（1）从顶点A出发，首先访问顶点A。（2）访问顶点B和顶点Fe（3）按照顶点A访问其邻接点的顺序，首先访问顶点B未被访问过的邻接点C、D、G,然后访问顶点F未被访问过的邻接点（无符合条件的邻
17、接点）。（4）按照顶点B访问其邻接点的JI质序，首先访问顶点C未被访问过的邻接点（无符合条件的邻接点），然后访问顶点D未被访问过的邻接点E,最后访问顶点G未被访问过的邻接点（无符合条件的邻接点）。（5）至此，该无向图遍历结束,得到的广度优先遍历序列为A、B、F、C、D、G、Ee【知识库】在对无向连通图进行遍历时，由深度优先遍历得到的生成树称为深度优先生成树,由广度优先遍历得到的生成树称为广度优先生成树。无论是哪种生成树，都是由相应遍历中经过的边构成的。.（详见教材）【学生】聆听、思考、理解、记录任务实施任务一应用题（1）、（2）【教师】描述问题，分析问Sg,要求学生完成任务【问题描述】（1）对于如图7-35所示的有向图（详见教材）,试给出相应的邻接矩阵和邻接表。（2）对于如图7-36所示的无向图（详见教材），试写出从顶点A出发进行深度优先遍历和广度优先遍历时得到的遍历序列。【学生】按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问迤课堂小结【教师】简要总结本节课的要点图的定义、基本术语和基本操作图的存储结构：邻接矩阵、邻接表图的遍历：深度优先遍历、广度优先遍历【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的相关练习。【学生】完成课后任务教学反思
