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

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

2、小生成树的算法（Prim算法和Kruskal算法）。第五节 有向无环图及其应用有向无环图的定义；拓扑排序、AOV-网的定义和拓扑排序的算法；AOE-网的定义、关键路径的定义和求法。第六节 最短路径单源最短路径问题：Dijkstra算法；各顶点之间的最短路径问题：Floyd算法。目的要求目的：理解图的定义和实现。基本要求：理解拓扑排序的概念和算法，理解关键路径问题、最短路径问题；掌握图的基本概念、邻接矩阵和邻接表存储结构、深度和广度优先遍历、最小生成树的概念、普里姆算法和克鲁斯卡尔算法求最小生成树的方法。重 点图的邻接矩阵和邻接表存储结构；深度和广度优先遍历方法；最小生成树。难点图的深度和广度优

3、先遍历方法；关键路径；最短路径。作业布置习题7参考书1. 数据结构题集(C语言版), 严蔚敏，清华大学出版社，2002。3. 数据结构、算法与应用C+语言描述，(美)Sartaj Sahni著，汪诗林等译，机械工业出版社，2002。课 型理论课学时分复 习 分钟配主要教具投影、黑板讲 授 分钟教学方法讲解、提问、示例指 导 分钟教学手段板书、课件总 结 分钟备注共8学时注：课型一栏填写理论课、实验课、习题课等授 课 内 容备 注第7章 图7.1图的定义和术语7.1.1 图的定义图（Graph）是一种网状数据结构，其形式化定义如下：Graph=（V，VR）其中V是顶点（Vertex）的非空有限集

4、合，VR是顶点间关系的集合。弧：若<x，y>VR，则<x，y>表示从顶点x到顶点y的一条弧（arc），并称x为弧尾（tail）或起始点(Initial node)，称y为弧头（head）或终端点(Terminal node)。此时的图称为有向图(Digraph)。无向图：若<x，y>VR，必有<y，x>VR，即VR是对称关系，这时以无序对（x，y）来代替两个有序对，表示x和y之间的一条边（edge），此时的图称为无向图(Undigraph)。 7.1.2 图的应用举例例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双

5、行道，分别用有向边、无向边表示；例2 电路图 顶点：元件 边：连接元件之间的线路例3 通讯线路图 顶点：地点 边：地点间的连线例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系7.1.3 图的基本术语设用n表示图中顶点的个数，用 e表示图中边或弧的数目，并且不考虑图中每个顶点到其自身的边或弧。无向完全图：有n（n-1）/2条边（图中每个顶点和其余n-1个顶点都有边相连）的无向图为完全图(Completed graph)。有向完全图：有n（n-1）条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为（1）有向完全图。稀疏图(Sparse graph)：对于有很少条

6、边的图（e < n log n）称为稀疏图，反之称为稠密图(Dense graph)。 权与网:在实际应用中，有时图的边或弧上往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为权(Weight)，这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图叫做赋权图或网(NetWork)。子图：设有两个图G=（V，E）和图G¢=（V¢，E¢）,若V¢ÍV且E¢ Í E，则称图G¢为G的子图(Subgraph)。例 下面 (b)、(c) 是 (a) 的子图邻接点及关联边：对于无向图 G=

7、（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的

8、度有出度和入度两部分：以顶点v为弧头的弧的数目称为该顶点的入度(InDegree)，记作ID（v），以顶点v为弧尾的弧的数目称为该顶点的出度(OutDegree)，记作OD（v）则顶点v的度为： TD（v）= ID（v）+ OD（v）。一般地，若图G中有n个顶点，e条边或弧，则图中顶点的度与边的关系如下：路径与回路无向图G=（V，E）中从顶点v到v/的路径(Path)是一个顶点序列(V=vi0，vi1，vi2，vim= v/),其中（vij-1，vij）E，1jm。如果图G是有向图，则路径也是有向的，顶点序列应满足<vij-1，vij>E，1jm。 路径长度：指路径上经过的弧或边的

9、数目。 回路或环：在一个路径中，若其第一个顶点和最后一个顶点是相同的，即v =v/，则称该路径为一个回路或环。简单路径：若表示路径的顶点序列中的顶点各不相同，则称这样的路径为简单路径。简单回路：除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为简单回路。 连通图：在无向图G=（V，E）中，若从vi到vj有路径相通，则称顶点vi与vj是连通的。如果对于图中的任意两个顶点vi、vjV，vi，vj都是连通的，则称该无向图G为连通图(Connected Graph)。 连通分量：无向图中的极大连通子图称为该无向图的连通分量(Connected Component)。 强连通图：在有向图G=（V

10、，A）中，若对于每对顶点vi、vjV且vivj，从vi到vj和vj到vi都有路径，则称该有向图为强连通图。强连通分量：有向图的极大强连通子图称作有向图的强连通分量。生成树一个连通图的生成树是指一个极小连通子图，它含有图中的全部顶点，但只有足已构成一棵树的n-1条边。7.2 图的存储结构图的存储结构方法有：邻接矩阵表示法；邻接表；邻接多重表；十字链表 1 邻接矩阵表示法 图的邻接矩阵表示法（Adjacency Matrix）也称作数组表示法。它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。 邻接矩阵法的特点

11、：1. 存储空间：需要n2个存储空间。2. 便于运算：便于判定图中任意两个顶点之间是否有边相连; 便于求得各个顶点的度。 邻接表 (Adjacency List)邻接表是图的链式存储结构1） 无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储2） 有向图的邻接表和逆邻接表l 有向图的邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储l 有向图的逆邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储邻接表的特点：存储空间：对于有n个顶点，e条边的无向图而言，若采取邻接表作为存储结构，则需要n个表头结点和

12、2e个表结点。 无向图的度：在无向图的邻接表中，顶点vi的度恰好就是第i个边链表上结点的个数。 有向图的出度/入度：在有向图的邻接表中，第i个边链表上顶点的个数是顶点vi的出度。在有向图的逆邻接表中，第i个边链表上顶点的个数是顶点vi的入度。 （有向图的）十字链表(Orthogonal List) （无向图的）邻接多重链表(Adjacency Multi_list)7.图的遍历图的遍历(Traversing Graph)从图中的某个顶点出发，按某种方法对图中的所有顶点访问且仅访问一次。 7.3.1深度优先搜索深度优先搜索（Depth_First Search）是指按照深度方向搜索 ，它类似于树

13、的先根遍历。基本思想： （1）访问出发点v0。 （2）依次以v0的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与v0有路径相通的顶点都被访问。若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。 1 图的深度优先搜索的递归算法：int visitedMAX_VERTEX_NUM; /*访问标志数组*/void DFSTraverseGraph (Graph g) /*对图g进行深度优先搜索，Graph 表示图的一种存储结构，如数组表示法或邻接表等*/for (vi=0;vi<g.vexnum;vi+) v

14、isitedvi=False;/访问标志数组初始化for( vi=0;vi<g.vexnum;vi+)/*调用深度遍历连通子图的操作*/*若图g是连通图，则此循环只执行一次*/ if (!visitedvi ) DFS (g，vi)；/* TraverseGraph */ void DFS（Graph g, int v0） /*深度遍历v0所在的连通子图*/visit（v0）；visitedv0 =True；/*访问顶点v0，并置访问标志数组相应分量值*/w=FirstAdjVertex(g,v0);while ( w!=-1) /*邻接点存在*/if(! visited w ) DFS

15、 (g,w); w=NextAdjVertex(g,v0,w); /*找下一个邻接点*/ /*DFS*/ 有了（具体的存储结构）邻接表，深度优先序列是唯一的3）用非递归过程实现深度优先搜索void DFS (Graph g, int v0) /*从v0出发深度优先搜索图g*/ InitStack(S); Push(S, v0)；while ( ! Empty(S) v=Pop(S); if (!visited(v) /*栈中可能有重复结点*/ visit(v); visitedv=True; w=FirstAdj(g, v); /*求v的第一个邻接点*/while (w!=-1 ) if (!

16、visited(w) Push(S, w);w=NextAdj(g, v, w); 7.3.2广度优先搜索广度优先搜索（Breadth_First Search）是指按照广度方向搜索，它类似于树的按层次遍历。基本思想：（1）从图中某个顶点v0出发，首先访问v0。（2）依次访问v0的各个未被访问的邻接点。 （3）分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新的端结点）。访问时应保证：如果Vi和Vk为当前端结点，且Vi在Vk之前被访问，则Vi的所有未被访问的邻接点应在Vk的所有未被访问的邻接点之前访问。重复（3），直到所有端结点均没有未被访问的邻接点为止。 若此时还有顶点未

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

18、dthFirstSearch (g，vi)；/* TraverseGraph */ void BreadthFirstSearch(Graph g, int v0) /*广度优先搜索图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

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

20、过的边组成。深度优先遍历得到的生成树称为深度优先生成树；广度优先遍历得到的生成树称为广度优先生成树。7.4. 最小生成树在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树（Minimum Cost Spanning Tree），简称为最小生成树。例要在 n 个城市间建立交通网，要考虑的问题如何在保证 n 点连通的前题下最节省经费? 求解: 连通6个城市且代价最小的交通线路? 最小生成树的重要性质如下：设N=(V,E) 是一连通网，U 是顶点集V的一个非空子集。若（u , v）是一条具有最小权值的边，其中uU，vV-U，则存在一棵包含边（u , v）的最小生成

21、树。 用反证法来证明这个最小生成树（MST）的性质：假设不存在这样一棵包含边（u , v）的最小生成树。任取一棵最小生成树T，将（u , v）加入T中。根据树的性质，此时T中必形成一个包含（u , v）的回路，且回路中必有一条边（u , v）的权值大于或等于（u , v）的权值。删除（u , v），则得到一棵代价小于等于T的生成树T，且T为一棵包含边（u , v）的最小生成树。这与假设矛盾。 1普里姆(prime)算法假设N=(V,E)是连通网，TE为最小生成树中边的集合。（1）初始U=u0(u0V),TE=； （2）在所有uU, vV-U的边中选一条代价最小的边（u0，v0）并入集合TE，同

22、时将v0并入U； （3）重复（2），直到U=V为止。 此时，TE中必含有n-1条边，则T=（V，TE）为N的最小生成树。 例：求下图的最小生成树。2. 克鲁斯卡尔算法假设N=(V,E)是连通网，将N中的边按权值从小到大的顺序排列；（1）将n个顶点看成n个集合； （2）按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；（3）重复（2），直到所有的顶点都在同一个顶点集合内。 7. 有向无环图的应用有向无环图(directed acycline graph)：一个无环的有向图，简称DAG图。有向无环图是描述一项工

23、程或系统的进行过程的有效工具。如描述工程流程、生产过程中各道工序的流程、程序流程、课程的流程等。7.5.1 拓扑排序1 AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网（Activity On Vertex Network），简称为AOV-网。 例：某工程可分为7个子工程，若用顶点表示子工程（也称活动）， 用弧表示子工程间的顺序关系。工程流程可用右图的AOV网表示表示课程之间优先关系的AOV网2 拓扑排序(Topological Sort)对工程问题，人们至少关心如下两类问题：1）工程能否顺序进行，即工程流程是否“合理”2）完成整项工程至少需要多少时间，哪

24、些子工程是影响工程进度的关键子工程为求解工程流程是否“合理”，通常用AOV网的有向图表示工程流程，通过检测AOV网中是否存在环来实现。拓扑排序是检测AOV网中是否存在环的有效方法。某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。AOV网所代表的一项工程中活动的集合显然是一个偏序集合。为了保证该项工程得以顺利完成，必须保证AOV网中不出现回路；否则，意味着某项活动应以自身作为能否开展的先决条件，这是荒谬的。 3 拓扑排序方法1）在有向图选一无前趋的顶点v，输出；2）从有向图中删除v及以v为尾的孤；3）重复1、2、直接全部输出全部顶点或有向图中不存在无前趋顶点。后一情况则说明有

25、向图中存在环。拓扑排序算法：算法思想：（1）选择一入度为 0 顶点 v，输出；（2） 将 v 邻接到的顶点的入度减1；（3）重复1、2 直到输出全部顶点或有向图没有入度为0的顶点；算法：p1827.5.2 关键路径1 AOE-网：在有向图中，用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间。 我们把用这种方法构造的有向无环图叫做边表示活动的网（Activity On Edge Network）,简称AOE-网。 AOE-网用在工程计划和管理中，人们最关心的是：哪些活动是影响工程进度的关键活动？至少需要多长时间能完成整个工程？AOE-网中的基本概念：源点：存在唯一的、入度为零的顶点，叫

26、源点。汇点：存在唯一的、出度为零的顶点，叫汇点。关键路径：从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。关键活动：关键路径上的活动叫做关键活动。 V1 开始事件,V6 结束事件 事件vj的最早发生时间vej: 事件vj的最迟发生时间vli: 指在不推迟整个工期的前提下，事件vj 的最晚发生时间 活动ak的最早开始时间ek活动ak 的最晚开始时间1i:指在不推迟整个工期的前提下，事件ak j 的最晚发生时间活动ak 的延迟时间diffk 1事件vj的最早发生时间vej ve1=0 vej=Maxve(i)+dut(<i,j>) vej=从源点到顶点v

27、j 的最长路径的长度2事件vj的最迟发生时间vlivln=venvlj=Minvl(k)-dut(<j,k>)3 活动ak的最早开始时间ek设ak=<i,j>, ek=vei4 活动ak 的最晚开始时间1i1k=vlj-dur(<i,j>)5 活动ak 的延迟时间diffk diffk= 1k- ek把活动ai的最晚开始时间1i与最早开始时间ei之差定义为活动ai的延迟时间6 关键活动对于活动ai，若有1i-ei=0 为关键活动，由关键活动组成的路径就是关键路径。7.6 最短路径问题的提出：作为图的最普通的应用，是在交通运输和通信网络中寻找两个结点间的最短路

28、径。比如说，我们可以用图来表示一个省或一个国家的公路结构，图的顶点表示城市，边表示公路段。并且我们对边加权，用以表示两个城市之间的距离，或者表示通过这段公路所需要的时间或所需要支付的花费。这对于一个驾驶员来说，若想从A城驾驶汽车到B城，他就会想得到下列问题的解答： 从A到B有公路吗？ 若从A到B的路不止一条，那么走哪一条路径最短或花费最小?7.6.1单源最短路径问题 问题的提出： 给定一个带权有向图 G与源点v， 求从v到G中其它顶点的最短路径。 限定各边上的权值大于或等于0。 为求得这些最短路径，Dijkstra 提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路

29、径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。 算法的基本框架：1、设置并逐步扩充一个集合S，存放已求出的最短路径的顶点，则尚未确定最短路径的顶点集合是V-S。引进辅助向量dist ，它的每一个分量disti表示已经找到的且从开始点v0到每一个终点vi的当前最短路径的长度（该路径只经过S中顶点最后到达vi ）。它的初态为：如果从v0到vi有弧，则disti为弧的权值；否则disti为。2、取distj=Mindisti | viV 则distj是从v0到vj 的最短路径长度。 将vj加入S集合3、修改从v0出发到集合VS上任一顶点vi的最短路

30、径的长度。即如果 distk+ arcski<disti则将disti修改为：distk+ arcski4、重复(2)、(3) n-1次，即可按最短路径长度的递增顺序，逐个求出v0到图中其它每个顶点的最短路径。为了同时得到路径，另设置一个路径向量pathn，其中pi存放从v0vi的最短路径上的前驱结点。例：求下图从V0到其余各顶点的最短路径。float Dn;intPn,Sn;DIJKSTRA(float Cn,int v)int i,j,k,v1,pre;int min,max=60,inf=80;v1=v-1;for (i=0;i<n;i+) Di=Cv1i;if (Di!=m

31、ax) Pi=v;else Pi=0;n n for (i=0;i<n;i+) Si=0;n Sv1=1; Dv1=0;n for (i=0;i<n-1;i+)n min=inf;q for (j=0;j<n;j+)q if (!Sj)&&(Dj<min)q min=Dj; k=j; Sk=1;for (j=0;j<n;j+)if (!Sj)&&(Dj>Dk+Ckj) Dj=Dk+Ckj;Pj=k+1;for (i=0;i<n;i+) printf(“%fn%d”,Di,i+1);pre=pi;while (pre!=0

32、) printf(“<-%d”,pre);pre=Ppre-1;7.6.2 任意一对顶点间的最短路径佛罗依德(Floyd)算法的基本思想设图g用邻接矩阵法表示，求图g中任意一对顶点vi、vj间的的最短路径。 （-1）将vi到vj 的最短的路径长度初始化为g.arcsij，然后进行如下n次比较和修正： （0）在vi、vj间加入顶点v0，比较（vi,v0,vj）和(vi,vj)的路径的长度，取其中较短的路径作为vi到vj 的且中间顶点号不大于0的最短路径。 （1）在vi、vj间加入顶点v1，得（vi,， v1）和(v1,， vj)，其中（vi,v1）是vi到v1 的且中间顶点号不大于0的最短路径，(v1,vj) 是v1到vj 的且中间顶点号不大于0的最短路径，这两条路径在上一步中已求出。将（vi,v1,vj）与上