数据结构教案第七章

安徽新华电脑专修学院课堂教学教案（软工专业课使用）课程名称数据结构教学对象新华软工专业教材数据结构（C语言）授课内容第七章图课时3教学目的与要求1、了解图的各种存储结构及其构造算法，了解实际问题的求解效率和采用何种存储结构和算法有密切联系2.了解图的两种遍历：深度优先遍历和广度优先遍历的算法，在学习中应注意图的遍历算法和树的遍历算法之间的类似和差异，树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3.了解课件中讨论的各种图的算法重点、难点重点：图的概念，存储，遍历，拓朴排序，最小生成树难点：算法实现、遍历有生成树和拓朴排序课型电脑应用课教学方法讲授、投影、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）课程导入：前面所学的数据结构中有线性结构和非线性结构，其中线性表，栈和队列及串、数组均为线性结构，而上章所讲的树是非线性结构。树的结构特点是任一结点除根有且仅有一个直接前驱含有一个或多个直接后继。本章将学习另一种非常重要的非线性结构图，它的特点是：任意两个结点都有可能相关联，即任一结点可能有多个直接前驱和多个直接后继，结点间的邻接关系可以是任意的。（10分钟）任务一、图的基本概念1．图的定义教学过程设计(续表)图G是集合V和集合E组成，记G=（V，E），其中V是G中顶点的非空有限集，E是G中边的集合，面边是V中顶点的偶对。若顶点的偶是有序的，刚称为有向图，用尖括号括起，若为无序的，则称为无向图。有向边又称为弧。图中E（G）可以为空。任务二、图的基本述语1．无向图边是无向的2．有向图每条边是有向的3．端点和邻接点4．起点和邻接点5．度、入度、出度6．子图G=（V，E）和G`=（V`，E`），若V`是V的子集且E`是E的子集，并使得E`中的边仅与V`中顶点相关联，则G`是G的子图。7．无向完全图和在向完全图设一无向图有N个顶点，且有n(n-1)/2条边，即任何两顶点都有边相关联，这样的无向图称为无向完全图。有向图中基有n(n-1)条边，即任何两顶点都有一对反向弧，则此有向图称为有向完全图。8．路径和路径长度及简单路径路径是顶点的序列。路径长度是路径所含的边。若一条路径的顶点序列中不出现重复顶点，称为简单路径9．回路或环10．连通、连通图和连通分图11．强连通图和强连通分图12．赋权图任务三、图的存储结构1.图的邻接矩阵存储它是用二维数组来表示图中顶点之间的邻接关系，可将G的邻接矩阵定义为一个n阶方阵。#defineMAVX50Voidcreatadjmatrix(intcost[MAXV][MAXV],intvexnum,intenum){intI,j,k,v1,v2;For(i=1;i=vexnum;i++)For(j=1;j=vexnum;j++)Cost[i][j]=0;For(k=1;k=enum;k++){scanf(“%d%d”,&v1,&v2);Cost[v1][v2]=1;Cost[v2][v1]=1;}}2、邻接链表一个图的邻接链表存储结构的类型定义：#definemaxvertex50Typedefstructarcnode{intadjvex;Structarnode*nextarc;}arcnodetyp;Typestructvexnode{intvertex;Arcnodetp*firstarc;}adjlist[maxvertex];Typedefstructgraph{adjlistadjlist;Intvexnum,arcnum;}graphtp;复习思考题作业上机任务1.搞清图的基本概念的含义2.描述图的存储的实现参考文献晋良颖数据结构人民邮电大学出版社课后记（或归纳小结）本次课程就介绍这里结束，总结本次的内容；安徽新华电脑专修学院课堂教学教案（软工专业课使用）课程名称数据结构教学对象新华软工专业教材数据结构（C语言）授课内容第七章图课时3教学目的与要求1、了解图的各种存储结构及其构造算法，了解实际问题的求解效率和采用何种存储结构和算法有密切联系2.了解图的两种遍历：深度优先遍历和广度优先遍历的算法，在学习中应注意图的遍历算法和树的遍历算法之间的类似和差异，树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3.了解课件中讨论的各种图的算法重点、难点重点：图的概念，存储，遍历，拓朴排序，最小生成树难点：算法实现、遍历有生成树和拓朴排序课型电脑应用课教学方法讲授、投影、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）复习内容：上讲介绍了图的基本概念，图在计算机中的存储结构，具体讲的图的邻接矩阵和邻接表的存储。这两种存储结构的算法需要重点掌握。课程导入：树一章中介绍了树的先根、中根和后根遍历，即按照某种顺序对树中的所有结点访问一次且只访问一次的顺序，那么对图来说又怎么来访问它的每一个结点呢，我们称为图的遍历。任务一、图的遍历1、深度优先搜索基本思想：从图G中某个顶点出发，访问V1，然后选择一下与V1相邻且未被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻接且未被访问过的顶点Vj访问，依次继续。若当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个仍未被访问的相邻接顶点Vw，从Vw出以按同样方法向前遍历，直到图中所有的顶点被访问。教学过程设计(续表)2．广度优先搜索基本思想：首先访问初始点Vi,并将其标记为已访问过，接着访问Vi的所有未被访问过的邻接顶点Vi1,vi2…vit,并均标记为已访问地过，然后再按照vi1,vi2…vit的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问，依次类推，直到图G中所有和初始点Vi有路径相通的顶点都有被访问过为止。voidBFSTraverse(GraphG,Status(*visit)(intv)){for(v=0;vG.vexnum;++v)visited[v]=FALSE;IntiQueque(Q);for(v=0;vG.vexnum;++v)if(!visited[v]){EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(u);visited[u]=TRUE;Visit(u);for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;visited(w);EnQueue(G,w);}}}}任务二、图的生成树1、生成树i.定义：所有顶点均由边连接在一起，但不存在回路的图叫~ii.深度优先生成树与广度优先生成树iii.生成森林：非连通图每个连通分量的生成树一起组成非连通图的~iv.说明1.一个图可以有许多棵不同的生成树2.所有生成树具有以下共同特点：a)生成树的顶点个数与图的顶点个数相同b)生成树是图的极小连通子图c)一个有n个顶点的连通图的生成树有n-1条边d)生成树中任意两个顶点间的路径是唯一的e)在生成树中再加一条边必然形成回路3.含n个顶点n-1条边的图不一定是生成树2、最小生成树（1）网络及其邻接矩阵（2）最小生成树3、求最小生成树的常用算法（1）普里姆算法算法思想：设N=(V,{E})是连通网，TE是N上最小生成树中边的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)将(u0,v0)并入集合TE，同时v0并入U重复上述操作直至U=V为止，则T=(V,{TE})为N的最小生成树算法实现：图用邻接矩阵表示算法描述算法评价：T(n)=O(n²)（2）克鲁斯卡尔算法算法思想：设连通网N=(V,{E})，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边依此类推，直至T中所有顶点都在同一连通分量上为止（3）统观法复习思考题作业上机任务1、课后习题2题2、P138第三题3、P1384、5、6题参考文献晋良颖数据结构人民邮电大学出版社课后记（或归纳小结）本次课程的内容为图的遍历和最小生成树，相对较难，课余时间要多看，多做题。安徽新华电脑专修学院课堂教学教案（软工专业课使用）课程名称数据结构教学对象新华软工专业教材数据结构（C语言）授课内容第七章图课时3教学目的与要求1、了解图的各种存储结构及其构造算法，了解实际问题的求解效率和采用何种存储结构和算法有密切联系2.了解图的两种遍历：深度优先遍历和广度优先遍历的算法，在学习中应注意图的遍历算法和树的遍历算法之间的类似和差异，树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3.了解课件中讨论的各种图的算法重点、难点重点：图的概念，存储，遍历，拓朴排序，最小生成树难点：算法实现、遍历有生成树和拓朴排序课型电脑应用课教学方法讲授、投影、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）复习内容：上一讲主要讲解的是图的深度优先和广度优先遍历及其算法的实现，以及生成树和最小生成树及求解最小生成树的各种算法，如普里姆算法、克鲁期斯卡尔算法等。课程导入:用带权的有向图表示一个交通运输网，图中：顶点——表示城市边——表示城市间的交通联系权——表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径教学过程设计(续表)任务一、最短路径迪杰斯特拉(Dijkstra)算法(1)设置两个顶点的集合T和S;集合S存放已找到最短路径的顶点集合T存放当前还未找到最短路径的顶点(2)初始状态时,S只包含源点v0;(3)从T中选取某个顶点vi(要求vi到v0的路径长度最短)加入到S中,;(4)S中每加入一个顶点vi,都要修改顶点v0到T中剩余顶点的最短路径长度值;它们的值为原来值与新值的较小者新值是vi的最短路径长度值加上vi到该顶点的路径长度(5)不断重复(3)和(4),直到S包含全部顶点;任务二、拓朴排序1、问题提出：学生选修课程问题顶点——表示课程有向弧——表示先决条件，若课程i是课程j的先决条件，则图中有弧i,j学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业——拓扑排序2、定义AOV网——用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(ActivityOnVertexnetwork)，简称AOV网若vi,vj是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继AOV网中不允许有回路，这意味着某项活动以自己拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫~检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止为先决条件拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫~检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止算法实现以邻接表作存储结构把邻接表中所有入度为0的顶点进栈栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕邻接表结点：typede