数据结构授课教案第7章

1、山东轻工业学院教师授课教案课程名称：数据结构（计科）课程代码：0301306学分：4.5课程类别：必修开课单位：信息科学与技术学院授课班级：授课教师：杨春花山东轻工业学院教务处制授课时间日星期第节年年年:月日星期1月日星期授果内既第七章图第一节图的定义和术语图的定义；有向图和无向图、完全图、顶点的度、路径、连通分量、生成树等基本术语。第二节图的存储结构邻接矩阵、邻接表、十字链表和邻接多重表。第二节图的遍历深度优先搜索的定义及实现和广度优先搜索的定义及实现。第四节图的连通性问题无向图的连通分量和生成树，最小生成树的定义以及构造最小生成树的算法PPrim算法和Kruskal算法）。第五节扃何尢环图

2、及其取用有向无环图的定义；拓扑排序、AOV网的定义和拓扑排序的算法；AOE网的定义、关键路径的定义和求法。第六节最短路径单源最短路径问题：Dijkstra算法；各顶点之间的最短路径问题：Floyd算法。目*目的：理解图的定义和实现。基本要求：理解拓扑排序的概念和算法，理解关键路径问题、最短路径问题；掌握图的基本概念、邻接矩阵和邻接表存储结构、深度和广度优先遍历、最小生成树的概念、普里姆算法和克鲁斯卡尔算法求最小生成树的方法。王占八、图的邻接矩阵和邻接表存储结构；深度和广度优先遍历方法；最小生成树。推占八、图的深度和广度优先遍历方法；关键路径；最短路径。作业布置习题7-CVR则vx,y表7K从顶

3、点x到顶点y的一,条弧(arc),并称x为弧尾(tail)或起始点(Initialnode),称y为弧头(head)或终端点(Terminalnode)。此时的图称为有向图(Digraph)。无向图：若CVR必有vy,xCVR,即VR是对称关系，这时以无序对(x,y)来代替两个有序对，表7Kx和y之间的一条边(edge),此时的图称为无向图(Undigraph)。7.1.2 图的应用举例例1交通图(公路、铁路)顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生

4、产流程图顶点：工序边：各道工序之间的顺序关系7.1.3 图的基本术语设用n表示图中顶点的个数，用e表示图中边或弧的数目，并且不考虑图中每个顶点到其自身的边或弧。无向完全图：有n(n-1)/2条边(图中每个顶点和其余n-1个顶点都有边相连)的无向图为完全图(Completedgraph)。有向完全图：有n(n-1)条边(图中每个顶点和其余n-1个顶点都有弧相连)的有向图为(1)有向完全图。稀疏图(Sparsegraph):对于有很少条边的图(enlogn)称为稀疏图，反之称为稠密图(Densegraph)。权与网：在实际应用中，有时图的边或弧上往往与具有一定意义的数有关，即每一条边都有与它相关的

5、数，称为权(Weight),这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图叫做赋权图或网(NetWork)。子图：设有两个图G=(V,E)和图G=(V,E),若VV且EE,则称图G为G的子图(Subgraph)o例下面(b)、(c)是(a)的子图邻接点及关联边：对于无向图G=(V,E),如果边(v,v)CE,则称顶点v,v互为邻接点(Adjacent),即v,v相邻接。边(v,v)依附(Incident)于顶点v和v,或者说边(v,v)与顶点v和v相关联。对于有向图G=(V,A)而言，若弧CA,则称顶点v邻接到顶点v,顶点v邻接自顶点v,或者说弧与顶点v,v相关联。

6、度、入度和出度：对于无向图而言，顶点v的度(Degree)是指和v相关联的边的数目，记作TD(v)。对于有向图而言，顶点v的度有出度和入度两部分：以顶点v为弧头的弧的数目称为该顶点的入度(InDegree),记作ID(v),以顶点v为弧尾的弧的数目称为该顶点的出度(OutDegree),记作OD(v)则顶点v的度为：TD(v)=ID(v)+OD(v)。般地，若图G中有n个顶点，e条边或弧，则图中顶点的度与边的关系如下:ne(TD(Vi)/2i1路径与回路无向图G= (V, E) 中从顶点 v 至 ij v/ 的路径 (Path) 是一个顶点序列(V=v i0, vi1 , vi2,，vim=

7、v/),其中 (vij-1 , 如果图vij) ? E, 1WjWm 。G是有向图，则路径也是有向的，顶点序列应满足? E, 1 w jw m 。路径长度：指路径上经过的弧或边的数目。回路或环：在一个路径中，若其第一个顶点和最后一个顶点是相同的，即 v =v/, 则称该路径为一个回路或环。简单路径：若表示路径的顶点序列中的顶点各不相同，则称这样的路径简单回路：除了第一个和最后一个顶点外，其余各顶点均不重复出现的连通图：在无向图 G= (V, E) 中，若从vi 至 ij vj 有路径相通，则称顶对于图中的任意两个顶点是连通的，则称该无向图G为连通图(Connected Graph)。连通分量：

8、无向图中的极大连通子图称为该无向图的连通分量vi 、 vjCV, v i,为简单路径。回路为简单回路。点 vi 与 vj 是连通的。如果vj 都(ConnectedComponent)。强连通图：在有向图G=(V,A)中，若对于每对顶点vi、vjCV且viwvj,从vi到vj和vj到vi都有路径，则称该有向图为强连通图。强连通分量：有向图的极大强连通子图称作有向图的强连通分量。生成树一个连通图的生成树是指一个极小连通子图，它含有图中的全部顶点，但只有足已构成一棵树的n-1条边。7.2 图的存储结构图的存储结构方法有：邻接矩阵表示法；邻接表；邻接多重表；十字链表1邻接矩阵表示法图的邻接矩阵表示法

9、(AdjacencyMatrix)也称作数组表示法。它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。邻接矩阵法的特点：1 .存储空间：需要n2个存储空间。2 .便于运算：便于判定图中任意两个顶点之间是否有边相连；便于求得各个顶点的度。2邻接表(AdjacencyList)邻接表是图的链式存储结构1 )无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储2 )有向图的邻接表和逆邻接表有向图的邻接表顶点：用一维数组存储(按编号顺序)以同一顶点为起点的弧：用线性链表存储

10、有向图的逆邻接表顶点：用一维数组存储(按编号顺序)以同一顶点为终点的弧：用线性链表存储邻接表的特点：存储空间：对于有n个顶点，e条边的无向图而言，若采取邻接表作为存储结构，则需要n个表头结点和2e个表结点。无向图的度：在无向图的邻接表中，顶点vi的度恰好就是第i个边链表上结点的个数。有向图白八出度/入度：在有向图的邻接表中，第i个边链表上顶点的个数是顶点vi的出度。在有向图的逆邻接表中，第i个边链表上顶点的个数是顶点vi的入度。3 (有向图的)十字链表(OrthogonalList)4 (无向图的)邻接多重链表(AdjacencyMulti_list)7.3图的遍历图的遍历(Traversin

11、gGraph)从图中的某个顶点出发，按某种方法对图中的所有顶点访问且仅访问一次。7.3.1 深度优先搜索深度优先搜索(Depth_FirstSearch)是指按照深度方向搜索，它类似于树的先根遍历。基本思想：(1) 访问出发点V0。(2) 依次以V0的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与V0有路径相通的顶点都被访问。若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。1 图的深度优先搜索的递归算法：intvisitedMAX_VERTEX_NUM;/*访问标志数组*/voidDFSTraverseGr

12、aph(Graphg)/*对图g进行深度优先搜索，Graph表示图的一种存储结构，如数组表示法或邻接表等*/for(vi=0;vig.vexnum;vi+)visitedvi=False;访问标志数组初始化for(vi=0;vig.vexnum;vi+)/*调用深度遍历连通子图的操作*/*若图g是连通图，则此循环只执行一次*/if(!visitedvi)DFS(g,vi);/*TraverseGraph*/voidDFS(Graphg,intv0)/*深度遍历v0所在的连通子图*/visit(v0);visitedv0=True;/*访问顶点v0,并置访问标志数组相应分量值*/w=FirstA

13、djVertex(g,v0);while(w!=-1)/*邻接点存在*/if(!visitedw)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)/*栈中可能有重复结点*/* 求 v 的第一个邻接点 */visit(v);visitedv=True;w=FirstA

14、dj(g,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),直到所有端结点均没有

15、未被访问的邻接点为止。若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。intvisitedMAX_VERTEX_NUM;/*访问标志数组*/voidBFSTraverseGraph(Graphg)/*对图g进行深度优先搜索，Graph表示图的一种存储结构，如数组表示法或邻接表等*/for(vi=0;vig.vexnum;vi+)visitedvi=False;访问标志数组初始化for(vi=0;vig.vexnum;vi+)/*调用深度遍历连通子图的操作*/*若图g是连通图，则此循环只执行一次*/if(!visitedvi)BreadthFi

16、rstSearch(g,vi);/*TraverseGraph*/voidBreadthFirstSearch(Graphg,intv0)/*广度优先搜索图g中v0所在的连通子图*/visit(v0);visitedv0=True;InitQueue(Q);/*初始化空队*/EnQueue(Q,v0);/*v0进队*/while(!Empty(Q)DeQueue(&Q,&v);/*队头元素出队*/w=FirstAdj(g,v);/*求v的第一个邻接点*/while(w!=-1)if(!visited(w)visit(w);visitedw=True;EnterQueue(Q,w);w=Next

17、Adj(g,v,w);7.4图的连通性问题7.4.1 无向图的连通分量和生成树1 无向图的连通分量在对图遍历时，对于连通图，无论是广度优先搜索还是深度优先搜索，仅需要调用一次搜索过程，即从任一个顶点出发，便可以遍历图中的各个顶点。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰为各连通分量中的顶点集。调用搜索过程的次数就是该图连通分量的个数。例2 无向图的生成树生成树是一个连通图G的一个极小的连通子图。包含图G的所有顶点，但只有n-1条边，并且是连通的。生成树可由遍历过程中所经过的边组成。深度优先遍历得到的生成树称为深度优先生成树；广度优先遍历得到的生成树称为广度优先生成树

18、。3 .4.3最小生成树在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树(MinimumCostSpanningTree),简称为最小生成树。例要在n个城市间建立交通网，要考虑的问题如何在保证n点连通的前题下最节省经费？求解：连通6个城市且代价最小的交通线路？最小生成树的重要性质如下：设N=（V,E）是一连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值的边，其中uCU,vCV-U,则存在一棵包含边（u,v）的最小生成树。用反证法来证明这个最小生成树（MST）的性质：假设不存在这样一棵包含边（u,v）的最小生成树。任取一棵最小生成树T,将（

19、u,v）加入T中。根据树的性质，此时T中必形成一个包含（u,v）的回路，且回路中必有一条边（u,v）的权值大于或等于（u,v）的权值。删除（u,v）,则得到一棵代价小于等于T的生成树V,且为一棵包含边（u,v）的最小生成树。这与假设矛盾。1 普里姆（prime）算法假设N=（V,E）是连通网，TE为最小生成树中边的集合。（1）初始U=u0（u06V）,TE=4;（2）在所有uCU,vCV-U的边中选一条代价最小的边（u0,v0）并入集合TE,同时将v0并入U;（3）重复（2），直至UU=V为止。此时，TE中必含有n-1条边，则T=（V,TE）为N的最小生成树。例：求下图的最小生成树。2 .克鲁

20、斯卡尔算法假设N=（V,E）是连通网，将N中的边按权值从小到大的顺序排列；将n个顶点看成n个集合；（2） 按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；（3） 重复（2）,直到所有的顶点都在同一个顶点集合内。7.5有向无环图的应用有向无环图（directedacyclinegraph）:一个无环的有向图，简称DAG0o有向无环图是描述一项工程或系统的进行过程的有效工具。如描述工程流程、生产过程中各道工序的流程、程序流程、课程的流程等。7.5.1 拓扑排序1 AOV网：用顶点表示活动，用弧表示活动间的优先

21、关系的有向无环图，称为顶点表示活动的网（ActivityOnVertexNetwork）,简称为AOV网。例：某工程可分为7个子工程，若用顶点表示子工程（也称活动），用弧表示子工程间的顺序关系。工程流程可用右图的AO网表示表示课程之间优先关系的AO网2 拓扑排序（TopologicalSort）对工程问题，人们至少关心如下两类问题：1） 工程能否顺序进行，即工程流程是否合理”2） 完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键子工程为求解工程流程是否含理”，通常用AO网的有向图表示工程流程，通过检测AO网中是否存在环来实现。拓扑排序是检测AO网中是否存在环的有效方法。某个集合上的

22、一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。AOVR所代表的一项工程中活动的集合显然是一个偏序集合。为了保证该项工程得以顺利完成，必须保证AOV网中不出现回路；否则,意味着某项活动应以自身作为能否开展的先决条件，这是荒谬的。3 拓扑排序方法1) 在有向图选一无前趋的顶点v,输出；2)从有向图中删除v及以v为尾的孤；3)重复1、2、直接全部输出全部顶点或有向图中不存在无前趋顶点。后一情况则说明有向图中存在环。拓扑排序算法：算法思想：选择一入度为0顶点V,输出；(2) 将v邻接到的顶点的入度减1;(3) 重复1、2直到输出全部顶点或有向图没有入度为0的顶点；算法：p1827.5.2关键

23、路径1AOE-网：在有向图中，用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间。我们把用这种方法构造的有向无环图叫做边表示活动的网(ActivityOnEdgeNetwork),简称AOE网。AOE网用在工程计划和管理中，人们最关心的是：哪些活动是影响工程进度的关键活动？至少需要多长时间能完成整个工程？AOE网中的基本概念：源点：存在唯一的、入度为零的顶点，叫源点。汇点：存在唯一的、出度为零的顶点，叫汇点。关键路径：从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。关键活动：关键路径上的活动叫做关键活动。V1开始事件，V6结束事件事件vj的最早发生时间v

24、ej:事件vj的最迟发生时间vli:指在不推迟整个工期的前提下，事件vj的最晚发生时间活动ak的最早开始时间ek活动ak的最晚开始时间1i:指在不推迟整个工期的前提下，事件akj的最晚发生时间活动ak的延迟时间diffk1 事件vj的最早发生时间vejve1=0vej=Maxve(i)+dut()vej=从源点到顶点vj的最长路径的长度2 事件vj的最迟发生时间vlivln=venvlj=Minvl(k)-dut()3 活动ak的最早开始时间ek设ak=,ek=vei4 活动ak的最晚开始时间1i1k=vlj-dur()5 活动ak的延迟时间diffkdiffk=1k-ek把活动ai的最晚开始

25、时间1i与最早开始时间ei之差定义为活动ai的延迟时间6 关键活动对于活动ai,若有1i-ei=0为关键活动，由关键活动组成的路径就是关键路径。7 .6最短路径问题的提出：作为图的最普通的应用，是在交通运输和通信网络中寻找两个结点间的最短路径。比如说，我们可以用图来表示一个省或一个国家的公路结构，图的顶点表示城市，边表示公路段。并且我们对边加权，用以表示两个城市之间的距离，或者表示通过这段公路所需要的时间或所需要支付的花费。这对于一个驾驶员来说，若想从A城驾驶汽车到B城，他就会想得到下列问题的解答:从A到B有公路吗？若从A到B的路不止一条，那么走哪一条路径最短或花费最小？7.6.1单源最短路径

26、问题问题的提出：给定一个带权有向图G与源点v,求从v到G中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。算法的基本框架：1、设置并逐步扩充一个集合S,存放已求出的最短路径的顶点，则尚未确定最短路径的顶点集合是V-S。引进辅助向量dist,它的每一个分量disti表示已经找到的且从开始点v0到每一个终点vi的当前最短路径的长度(该路径只经过S中顶点最后到达vi)。它的初态为:如果从v

27、0到vi有弧，则disti为弧的权值；否则disti为8。2、取distj=Mindisti|vi6v则distj是从v0到vj的最短路径长度。将vj加入S集合3、修改从v0出发到集合VS上任一顶点vi的最短路径的长度。即如果distk+arcskidisti则将disti修改为:distk+arcski4、重复(2)、(3)n-1、次,即可按最短路径长度的递增顺序，逐个求出v0到图中其它每个顶点的最短路径。为了同时得到路径，另设置一个路径向量pathn,其中pi存放从v0?vi的最短路径上的前驱结点。例：求下图从V0到其余各顶点的最短路径。floatDn;intPn,Sn;DIJKSTRA(

28、floatCn,intv)inti,j,k,v1,pre;intmin,max=60,inf=80;v1=v-1;for(i=0;in;i+)Di=Cv1i;if(Di!=max)Pi=v;elsePi=0;for(i=0;in;i+)Si=0;Sv1=1;Dv1=0;for(i=0;in-1;i+)Sk=1；for(j=0;jDk+Ckj)Dj=Dk+Ckj;P昨k+1；for(i=0;in;i+)printf(fn%d，Di,i+1);pre=Pi；while(pre!=0)printf(-%d”,pre);pre=Ppre-1;printf( %f ,Aij);next=pathij;7.6.2任意一对顶点间的最短路径佛罗依德(Floyd)算法的基本思想设图g用邻接矩阵法表示，求图g中任意一对顶点vi、Vj间的的最短路径。(-1)将Vi到Vj的最短的路径长度初始化为g.arcsij,然后进彳T如下n次比较和修正：(0)在vi、vj间加入顶点V0,比较(vi,v0,vj)和(vi,vj)的路径的长度，取其中较短的路径作为Vi到Vj的且中间顶点号不大于0的最短路径。在vi、vj