数据结构授课教案-第7章

山东轻工业学院教师授课教案课程名称：数据结构（计科）课程代码：0301306学分：4.5课程类别：必修开课单位:信息科学与技术学院授课班级：授课教师：杨春花山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第七章图第一节图的定义和术语图的定义；有向图和无向图、完全图、顶点的度、路径、连通分量、生成树等基本术语。第二节图的存储结构邻接矩阵、邻接表、十字链表和邻接多重表。第三节图的遍历深度优先搜索的定义及实现和广度优先搜索的定义及实现。第四节图的连通性问题无向图的连通分量和生成树，最小生成树的定义以及构造最小生成树的算法（Prim算法和Kruskal算法）。第五节有向无环图及其应用有向无环图的定义；拓扑排序、AOV-网的定义和拓扑排序的算法；AOE-网的定义、关键路径的定义和求法。第六节最短路径单源最短路径问题：Dijkstra算法；各顶点之间的最短路径问题：Floyd算法。目的要求目的：理解图的定义和实现。基本要求：理解拓扑排序的概念和算法，理解关键路径问题、最短路径问题；掌握图的基本概念、邻接矩阵和邻接表存储结构、深度和广度优先遍历、最小生成树的概念、普里姆算法和克鲁斯卡尔算法求最小生成树的方法。重点图的邻接矩阵和邻接表存储结构；深度和广度优先遍历方法；最小生成树。难点图的深度和广度优先遍历方法；关键路径；最短路径。作业布置习题7参考书1.数据结构题集(C语言版),严蔚敏，清华大学出版社，2002。3.数据结构、算法与应用－C++语言描述，(美)SartajSahni著，汪诗林等译，机械工业出版社，2002。课型理论课学时分复习分钟主要教具投影、黑板讲授分钟教学方法讲解、提问、示例配指导分钟教学手段板书、课件总结分钟备注共8学时注：课型一栏填写理论课、实验课、习题课等授课内容备注第7章图7.1图的定义和术语7.1.1图的定义图（Graph）是一种网状数据结构，其形式化定义如下：Graph=（V，VR）其中V是顶点（Vertex）的非空有限集合，VR是顶点间关系的集合。弧：若x，y∈VR，则x，y表示从顶点x到顶点y的一条弧（arc），并称x为弧尾（tail）或起始点(Initialnode)，称y为弧头（head）或终端点(Terminalnode)。此时的图称为有向图(Digraph)。无向图：若x，y∈VR，必有y，x∈VR，即VR是对称关系，这时以无序对（x，y）来代替两个有序对，表示x和y之间的一条边（edge），此时的图称为无向图(Undigraph)。7.1.2图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系7.1.3图的基本术语设用n表示图中顶点的个数，用e表示图中边或弧的数目，并且不考虑图中每个顶点到其自身的边或弧。无向完全图：有n（n-1）/2条边（图中每个顶点和其余n-1个顶点都有边相连）的无向图为完全图(Completedgraph)。有向完全图：有n（n-1）条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为（1）有向完全图。稀疏图(Sparsegraph)：对于有很少条边的图（enlogn）称为稀疏图，反之称为稠密图(Densegraph)。权与网:在实际应用中，有时图的边或弧上往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为权(Weight)，这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图叫做赋权图或网(NetWork)。子图：设有两个图G=（V，E）和图G=（V，E）,若VV且EE，则称图G为G的子图(Subgraph)。例下面(b)、(c)是(a)的子图邻接点及关联边：对于无向图G=（V，{E}），如果边（v，v）∈E，则称顶点v，v互为邻接点(Adjacent)，即v，v相邻接。边（v，v）依附(Incident)于顶点v和v，或者说边（v，v）与顶点v和v相关联。对于有向图G=（V，{A}）而言，若弧v，v/∈A，则称顶点v邻接到顶点v，顶点v邻接自顶点v，或者说弧v，v与顶点v，v相关联。度、入度和出度：对于无向图而言，顶点v的度(Degree)是指和v相关联的边的数目，记作TD（v）。对于有向图而言，顶点v的度有出度和入度两部分：以顶点v为弧头的弧的数目称为该顶点的入度(InDegree)，记作ID（v），以顶点v为弧尾的弧的数目称为该顶点的出度(OutDegree)，记作OD（v）则顶点v的度为：TD（v）=ID（v）+OD（v）。一般地，若图G中有n个顶点，e条边或弧，则图中顶点的度与边的关系如下：2/))((e1niiVTD路径与回路无向图G=（V，{E}）中从顶点v到v/的路径(Path)是一个顶点序列(V=vi0，vi1，vi2，…，vim=v/),其中（vij-1，vij）∈E，1≤j≤m。如果图G是有向图，则路径也是有向的，顶点序列应满足vij-1，vij∈E，1≤j≤m。路径长度：指路径上经过的弧或边的数目。回路或环：在一个路径中，若其第一个顶点和最后一个顶点是相同的，即v=v/，则称该路径为一个回路或环。简单路径：若表示路径的顶点序列中的顶点各不相同，则称这样的路径为简单路径。简单回路：除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为简单回路。连通图：在无向图G=（V，{E}）中，若从vi到vj有路径相通，则称顶点vi与vj是连通的。如果对于图中的任意两个顶点vi、vj∈V，vi，vj都是连通的，则称该无向图G为连通图(ConnectedGraph)。连通分量：无向图中的极大连通子图称为该无向图的连通分量(ConnectedComponent)。强连通图：在有向图G=（V，{A}）中，若对于每对顶点vi、vj∈V且vi≠vj，从vi到vj和vj到vi都有路径，则称该有向图为强连通图。强连通分量：有向图的极大强连通子图称作有向图的强连通分量。生成树一个连通图的生成树是指一个极小连通子图，它含有图中的全部顶点，但只有足已构成一棵树的n-1条边。7.2图的存储结构图的存储结构方法有：①邻接矩阵表示法；②邻接表；③邻接多重表；④十字链表1邻接矩阵表示法图的邻接矩阵表示法（AdjacencyMatrix）也称作数组表示法。它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。邻接矩阵法的特点：1.存储空间：需要n2个存储空间。2.便于运算：便于判定图中任意两个顶点之间是否有边相连;便于求得各个顶点的度。２邻接表(AdjacencyList)邻接表是图的链式存储结构1）无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储2）有向图的邻接表和逆邻接表有向图的邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储有向图的逆邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储邻接表的特点：存储空间：对于有n个顶点，e条边的无向图而言，若采取邻接表作为存储结构，则需要n个表头结点和2e个表结点。无向图的度：在无向图的邻接表中，顶点vi的度恰好就是第i个边链表上结点的个数。有向图的出度/入度：在有向图的邻接表中，第i个边链表上顶点的个数是顶点vi的出度。在有向图的逆邻接表中，第i个边链表上顶点的个数是顶点vi的入度。３（有向图的）十字链表(OrthogonalList)４（无向图的）邻接多重链表(AdjacencyMulti_list)7.３图的遍历图的遍历(TraversingGraph)从图中的某个顶点出发，按某种方法对图中的所有顶点访问且仅访问一次。7.3.1深度优先搜索深度优先搜索（Depth_FirstSearch）是指按照深度方向搜索，它类似于树的先根遍历。基本思想：（1）访问出发点v0。（2）依次以v0的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与v0有路径相通的顶点都被访问。若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。1图的深度优先搜索的递归算法：intvisited[MAX_VERTEX_NUM];/*访问标志数组*/voidDFSTraverseGraph(Graphg){/*对图g进行深度优先搜索，Graph表示图的一种存储结构，如数组表示法或邻接表等*/for(vi=0;vig.vexnum;vi++)visited[vi]=False;//访问标志数组初始化for(vi=0;vig.vexnum;vi++)/*调用深度遍历连通子图的操作*//*若图g是连通图，则此循环只执行一次*/if(!visited[vi])DFS(g，vi)；}/*TraverseGraph*/voidDFS（Graphg,intv0）{/*深度遍历v0所在的连通子图*/visit（v0）；visited[v0]=True；/*访问顶点v0，并置访问标志数组相应分量值*/w=FirstAdjVertex(g,v0);while(w!=-1){/*邻接点存在*/if(!visited[w])DFS(g,w);w=NextAdjVertex(g,v0,w);/*找下一个邻接点*/}}/*DFS*/有了（具体的存储结构）邻接表，深度优先序列是唯一的3）用非递归过程实现深度优先搜索voidDFS(Graphg,intv0)/*从v0出发深度优先搜索图g*/{InitStack(S);Push(S,v0)；while(!Empty(S)){v=Pop(S);if(!visited(v)){/*栈中可能有重复结点*/visit(v);visited[v]=True;w=FirstAdj(g,v);/*求v的第一个邻接点*/while(w!=-1){if(!visited(w))Push(S,w);w=NextAdj(g,v,w);}}}｝7.3.2广度优先搜索广度优先搜索（Breadth_FirstSearch）是指按照广度方向搜索，它类似于树的按层次遍历。基本思想：（1）从图中某个顶点v0出发，首先访问v0。（2）依次访问v0的各个未被访问的邻接点。（3）分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新的端结点）。访问时应保证：如果Vi和Vk为当前端结点，且Vi在Vk之前被访问，则Vi的所有未被访问的邻接点应在Vk的所有未被访问的邻接点之前访问。重复（3），直到所有端结点均没有未被访问的邻接点为止。若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。intvisited[MAX_VERTEX_NUM];/*访问标志数组*/voidBFSTraverseGraph(Graphg){/*对图g进行深度优先搜索，Graph表示图的一种存储结构，如数组表示法或邻接表等*/for(vi=0;vig.vexnum;vi++)visited[vi]=False;//访问标志数组初始化for(vi=0;vig.vexnum;vi++)/*调用深度遍历连通子图的操作*//*若图g是连通图，则此循环只执行一次*/if(!visited[vi])BreadthFirstSearch(g，vi)；}/*TraverseGraph*/voidBreadthFirstSearch(Graphg,intv0){/*广度优先搜索图g中v0所在的连通子图*/visit(v0);visited[v0]=True;InitQueue(Q);/*初始化空队*/EnQueue(Q,v0)；/*v0进队*/wh