数据结构培训.pptx

《数据结构培训.pptx》由会员分享，可在线阅读，更多相关《数据结构培训.pptx（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、例245136G1图G1中：V(G1)=1,2,3,4,5,6 E(G1)=,例157324G26图G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)第1页/共54页有向完全图n个顶点的有向图边数是n(n-1)无向完全图n个顶点的无向图边数是n(n-1)/2权与图的边或弧相关的数叫网带权的图叫子图如果图G(V,E)和图G(V,E),满足：VVEE 则称G为G的子图顶点的度无向图中，顶点的度为与每个顶点相连的边数有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目出度：以该顶点为尾的弧的数目路径路

2、径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1jn)第2页/共54页路径长度沿路径边的数目或沿路径各边权值之和回路第一个顶点和最后一个顶点相同的路径叫简单路径序列中顶点不重复出现的路径叫简单回路除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫连通无向图中,从顶点V到顶点W有一条路径，则说V和W是连通的连通图无向图中,图中任意两个顶点都是连通的叫连通分量无向图中,非连通图的每一个连通部分叫强连通图有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是第3页/共54页例213213有向完全图无向完全图356例

3、245136图与子图例245136G1顶点2入度：1 出度：3顶点4入度：1 出度：0例157324G26顶点5的度：3顶点2的度：4第4页/共54页例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1第5页/共54页连通图例245136强连通图356例非连通图连通分量例245136第6页/共54页7.2 图的存储结构多重链表例G12413例15324G2

4、V1V2 V4 V3 V1 V2 V4 V5 V3按度数最大的顶点设计顶点结构第7页/共54页邻接矩阵表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵例G12413例15324G2第8页/共54页特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和网络的邻接矩阵可定义为：第9页/共54页例145237531864

5、2第10页/共54页邻接表实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）typedef struct node int adjvex;/邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *next;/链域，指示下一条边或弧JD;adjvex next表头结点：typedef struct tnode int vexdata;/存放顶点信息 struct node *firstarc;/指示第一个邻接点TD;TD gaM;/ga0不用vexdata firstarc第11页/共54页例G1bdac例aecbdG21

6、234acdbvexdata firstarc 3 2 4 1adjvex next1234acdbvexdata firstarc 4 2 1 2adjvex next5e 4 3 5 1 5 3 2 3第12页/共54页例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 2第13页/共54页V1V2V4V5V3V7V6V8例12341342vexdata firstarc 2 7 8 3adjvex next55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4第14页/共54页V1V2V4V

7、5V3V7V6V8例12341342vexdata firstarc 2 7 8 3adjvex next55 6 4 8 2678678 7第15页/共54页特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表例G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex next第16页/共54页无向图的邻接多重表表示法顶点结点：typedef struct dnode int data;/存与顶点有关的信息 st

8、ruct node *firstedge;/指向第一条依附于该顶点的边DD;DD gaM;/ga0不用data firstedge边结点：typedef struct node int mark;/标志域 int ivex,jvex;/该边依附的两个顶点在表头数组中位置 struct node *ilink,*jlink;/分别指向依附于ivex和jvex的下一条边JD;mark ivex ilink jvex jlink第17页/共54页例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2mark ivex ilink jvex jlink第18页/共54页7.3

9、 图的遍历深度优先遍历(DFS)方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7第19页/共54页V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V7第20页/共54页V1V2V4V5V3

10、V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V5第21页/共54页V1V2V4V5V3V7V6V8例深度遍历：V1V3 V7 V6 V2 V5 V8 V4第22页/共54页V1V2V4V5V3V7V6V8例深度遍历：V1V3 V7 V6 V2 V4 V8 V5第23页/共54页广度优先遍历(BFS)方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V

11、1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8第24页/共54页V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8第25页/共54页V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V5第26页/共54页7.4 生成树生成树定义：所有顶点均由边连接在一起，但不存在回路的图叫深度优先生成树与广度优先生成树说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点

12、个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树GHKI第27页/共54页V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8第28页/共54页例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林第2

13、9页/共54页最小生成树问题提出要在n个城市间建立通信联络网，顶点表示城市权城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小代价生成树问题分析1654327131791812752410n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路问题转化为：如何在可能的线路中选择n-1条，能把 所有城市（顶点）均连起来，且总耗费 （各边权值之和）最小第30页/共54页构造最小生成树方法普里姆(Prim)算法算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合Y从任一顶点出发，将此点包含在生成树

14、里Y在这些一个顶点已在生成树里而另一顶点未在生成树里的边中，找一条代价最小的边Y将此边和那个顶点包含进生成树Y重复上述操作，每次加一个顶点和一个代价最小的边。直至所有的顶点包含进去，则得到最小生成树第31页/共54页例1654326513566425131163141643142116432142516543214253第32页/共54页10 1 2 3 4 50 1 2 3 4 51-21-41-1例16543265135664251-51-3165432651356642516543214253第33页/共54页7.5 拓扑排序问题提出：学生选修课程问题顶点表示课程有向弧表示先决条件，若课

15、程i是课程j的先决条件，则图中有弧学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序定义AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继AOV网中不允许有回路，这意味着某项活动以自己为先决条件第34页/共54页拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环拓扑排序的方

16、法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止第35页/共54页例课程代号 课程名称 先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C12第36页/共54页C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4-C5

17、-C7-C9-C10-C11-C6-C12-C8或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一个AOV网的拓扑序列不是唯一的第37页/共54页C1C2C3C4C5C6C7C8C9C10C11C12第38页/共54页C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2（2）第39页/共54页C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3（3）C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4（4）第40页/共54页C6C8C10C11

18、C12拓扑序列：C1-C2-C3-C4-C5-C7-C9C6C8C11C12拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10（8）C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4-C5（5）C6C8C9C10C11C12拓扑序列：C1-C2-C3-C4-C5-C7（6）第41页/共54页C6C8C12拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11（9）C8C12拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6（10）C8拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12（11）拓扑序列

19、：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12-C8（12）第42页/共54页7.6 最短路径问题提出用带权的有向图表示一个交通运输网，图中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径从某个源点到其余各顶点的最短路径51643208562301371732913长度最短路径813192120第43页/共54页迪杰斯特拉(Dijkstra)算法思想按路径长度递增次序产生最短路径算法：把V分成两组：（1）S：已求出最短路径的顶点的集合（2

20、）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）第44页/共54页求最短路径步骤初使时令 S=V0,T=其余顶点，T中顶点对应的距离值若存在，为弧上的权值若不存在，为从T中选取一个其距离值为最小的顶点W

21、，加入S对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值重复上述步骤，直到S中包含所有顶点，即S=V为止第45页/共54页1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329第46页/共54页7.7 关键路径问题提出把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始例 设一个工程有11项活动，9个事件事件 V

22、1表示整个工程开始事件V9表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第47页/共54页定义AOE网(Activity On Edge)也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间路径长度路径上各活动持续时间之和关键路径路径长度最长的路径叫Ve(j)表示事件Vj的最早发生时间Vl(j)表示事件Vj的最迟发生时间e(i)表示活动ai的最早开始时间l(i)表示活动ai的最迟开始时间l(

23、i)-e(i)表示完成活动ai的时间余量关键活动关键路径上的活动叫，即l(i)=e(i)的活动第48页/共54页问题分析如何找e(i)=l(i)的关键活动？设活动ai用弧表示，其持续时间记为：dut()则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()jkai如何求Ve(j)和Vl(j)？(1)从Ve(1)=0开始向前递推(2)从Vl(n)=Ve(n)开始向后递推第49页/共54页求关键路径步骤求Ve(i)求Vl(j)求e(i)求l(i)计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V

24、2V3V4V5V6V7V8V9顶点 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e00002266046258377077071031616014140033第50页/共54页算法实现以邻接表作存储结构从源点V1出发，令Ve1=0,按拓扑序列求各顶点的Vei从汇点Vn出发，令Vln=Ven,按逆拓扑序列求其余各顶点的Vli根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动邻接表结点：typedef struct node int vex;/顶点域 int length;struct nod

25、e *next;/链域JD;表头结点：typedef struct tnode int vexdata;int in;/入度域 struct node *link;/链域TD;TD gM;/g0不用第51页/共54页算法描述输入顶点和弧信息，建立其邻接表计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的Vei将得到的拓扑序列进栈按逆拓扑序列求顶点的Vli计算每条弧的ei和li,找出ei=li的关键活动Ch6_20.c987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4第52页/共54页987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlinkvexnextvexdatalength123456789123456789011121122 26 34 45 79 51 62 51 87 84 910 94第53页/共54页感谢您的观看！第54页/共54页