《《数据结构与算法》PPT课堂课件-第13章-图.pdf》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课堂课件-第13章-图.pdf（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2021/6/131第第十十三三章章 图图v13.1 图图的的定定义义和和术术语语v图图(Graph)图图G是是由由两两个个集集合合V(G)和和E(G)组组成成的的,记记为为G=(V,E)其其中中：V(G)是是顶顶点点的的非非空空有有限限集集 E(G)是是边边的的有有限限集集合合，边边是是顶顶点点的的无无序序对对或或有有序序对对v有有向向图图有有向向图图G是是由由两两个个集集合合V(G)和和E(G)组组成成的的 其其中中：V(G)是是顶顶点点的的非非空空有有限限集集 E(G)是是有有向向边边（也也称称弧弧）的的有有限限集集合合，弧弧是是顶顶点点的的有有序序对对，记记为为，v,w是是顶顶点点，v
2、为为弧弧尾尾，w为为弧弧头头v无无向向图图无无向向图图G是是由由两两个个集集合合V(G)和和E(G)组组成成的的 其其中中：V(G)是是顶顶点点的的非非空空有有限限集集 E(G)是是边边的的有有限限集集合合，边边是是顶顶点点的的无无序序对对，记记为为 （v,w）或或（w,v)，并并且且（v,w)=(w,v)2021/6/132例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)2021/6/133v有向完备
3、图n个顶点的有向图最大边数是n(n-1)v无向完备图n个顶点的无向图最大边数是n(n-1)/2v权与图的边或弧相关的数叫v网带权的图叫v子图如果图G(V,E)和图G(V,E),满足：VVEE 则称G为G的子图v顶点的度无向图中，顶点的度为与每个顶点相连的边数有向图中，顶点的度分成入度与出度v入度：以该顶点为头的弧的数目v出度：以该顶点为尾的弧的数目v路径路径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1jn)2021/6/134v路径长度沿路径边的数目或沿路径各边权值之和v回路第一个顶点和最后一个顶点相同的路径叫v简单路径序列中顶点不重复出现的路径叫v简单回
4、路除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫v连通从顶点V到顶点W有一条路径，则说V和W是连通的v连通图图中任意两个顶点都是连通的叫v连通分量非连通图的每一个连通部分叫v强连通图有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是2021/6/135例213213有向完备图无向完备图356例245136图与子图例245136G1顶点2入度：1 出度：3顶点4入度：1 出度：0例157324G26顶点5的度：3顶点2的度：42021/6/136例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2
5、，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，12021/6/137连通图例245136强连通图356例非连通图连通分量例2451362021/6/138v13.2 图的存储结构多重链表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V32021/6/139邻接矩阵表示顶点间相联关系的矩阵v定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵例G12413例15324G22021/6/13
6、10v特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，v顶点Vi的出度是A中第i行元素之和v顶点Vi的入度是A中第i列元素之和网络的邻接矩阵可定义为：2021/6/1311例14523753186422021/6/1312邻接表v实现：为图中每个顶点建立一个单链表，第i个单链表存放顶点Vi的所有邻接顶点。2021/6/1313v特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中v顶点Vi的出度为第i个单链表中的结点个数v顶点
7、Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为终点的边的单链表求解麻烦！例 1 3 11342 2 42021/6/1314 紧紧缩缩邻邻接接表表将将图图G的的每每个个顶顶点点的的邻邻接接表表紧紧凑凑地地存存储储在在2个个一一维维数数组组List和和h中中。其其中中一一维维数数组组List依依次次存存储储顶顶点点1,2,n的的邻邻接接顶顶点点。数数组组单单元元hi存存储储顶顶点点i的的邻邻接接表表在在数数组组List中中的的起起始始位位置置。紧缩邻接表如如图图G2G2和和G1G1的的紧紧缩缩邻邻接接表表表表示示分分别别如如下下图图(a)(a)和和(b)
8、(b)：2021/6/1315v13.3 图的遍历深度优先遍历(DFS)v方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止（问题：什么时候会出现这种情况？）V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7类似于：树的前序遍历！2021/6/1316V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V
9、3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V72021/6/1317V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V52021/6/1318v深度优先遍历算法递归算法开始访问v,置标志求v邻接点有邻接点u求下一邻接点uvu访问过结束NYNYDFS开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi=Vexnums结束NNYY2021/6/1319V1V2V4V5V3V7V6V8例深度遍历：V112341342vexdata firstarc 2 7 8 3adjvex next55 6 4 1 5 1 2 8 2678678 7
10、 3 6 3 5 4V3 V7 V6 V2 V5 V8 V42021/6/1320V1V2V4V5V3V7V6V8例12341342vexdata firstarc 2 7 8 3adjvex next55 6 4 8 2678678 7深度遍历：V1V3 V7 V6 V2 V4 V8 V52021/6/132113.3 图的遍历广度优先搜索(BFS)v方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接顶点；然后分别从这些邻接顶点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上
11、述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8类似于：树的层次遍历！2021/6/1322V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V82021/6/1323V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V52021/6/1324v广度优先遍历算法开始标志数组初始化Vi=1Vi访问过BFSVi=Vi+1Vi=Vexnums结束NNYY2021/
12、6/1325开始访问v置标志求w邻接点uu存在吗w下一邻接点uu访问过结束NYNYBFS初始化队列v入队队列空吗队头w出队访问u,置标志u入队NaaY2021/6/1326例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍历序列：10 1 2 3 4 54fr遍历序列：1 40 1 2 3 4 54 3fr遍历序列：1 4 32021/6/1327例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20
13、 1 2 3 4 54 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍历序列：1 4 3 2 52021/6/13280 1 2 3 4 5 2 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 fr遍历序列：1 4 3 2 5例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 22021/6/1329v13.4 最短路径问题提出用带权的有向图表示一个交通运输网，图
14、中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径单源最短路径51643208562301371732913长度最短路径8131921202021/6/1330vDijkstra算法思想按路径长度递增次序产生最短路径算法：把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 从V0到T中任何顶点的最短路径长度 （2）每个顶点对应
15、一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和2021/6/1331v求最短路径步骤初使时令 S=V0,T=其余顶点，T中顶点对应的距离值v若存在，距离值为弧上的权值v若不存在，距离值为从T中选取一个其距离值为最小的顶点W，加入S对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值重复上述步骤，直到S中包含所有顶点，即S=V为止2021/6/1332迭迭代
16、代S Su udist2dist2dist3dist3dist4dist4dist5dist5初初始始11-1010 30301001001 11,21,22 21010606030301001002 21,2,41,2,44 410105050303090903 31,2,4,31,2,4,33 310105050303060604 41,2,4,3,51,2,4,3,55 510105050303060602021/6/1333v算法描述v算法分析：T(n)=O(n)v算法实现图用带权邻接矩阵存储a 数组dist存放当前找到的从源点V0到每个终点的最短路径长度，其初态为图中直接路径权值数组
17、pre表示从V0到各终点的最短路径上，此顶点的前一顶点的序号；若从V0到某终点无路径，则用0作为其前一顶点的序号2021/6/1334所有顶点对之间的最短路径v方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次 T(n)=O(n)v方法二：Floyd算法算法思想：逐个顶点试探法求最短路径步骤v初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为v逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值v所有顶点试探完毕，算法结束2021/6/1335例ACB2643110 4 116 0 23 0初始：路径：AB ACBA BC
18、CA0 4 66 0 23 7 0加入B：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入A：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入C：路径：AB ABCBCA BCCA CAB0 0 00 0 00 0 0path=0 0 00 0 00 1 0path=0 0 20 0 00 1 0path=0 0 23 0 00 1 0path=2021/6/1336算法实现v图用邻接矩阵存储v二维数组c存放最短路径长度vpathij是从Vi到Vj的最短路径上Vj前一顶点序号算法描述算法分析：T(n)=O(n)实际上，从实现代码来看：Floy
19、d算算法法的的代代码码比比用用Dijkstra算算法法要要简简明明得得多多！这样看来，Floyd算法似乎没带来更多的好处？！2021/6/1337v13.5 生成树生成树v定义：所有顶点均由边连接在一起，但不存在回路的图叫v说明：一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：v生成树的顶点个数与图的顶点个数相同v生成树是图的极小连通子图v一个有n个顶点的连通图的生成树有n-1条边v生成树中任意两个顶点间的路径是唯一的v在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树GHKI2021/6/1338最小生成树v问题提出要在n个城市间建立通信联络网，顶点表示城市权城
20、市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小代价生成树v问题分析1654327131791812752410n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路问题转化为：如何在可能的线路中选择n-1条，能把 所有城市（顶点）均连起来，且总耗费 （各边权值之和）最小2021/6/1339最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的PrimPrim算算法法和KruskalKruskal算算法法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪
21、心选择的方式不同，它们都利用了下面的最最小小生生成成树树性性质质：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MSTMST性性质质。2021/6/1340MST性质证明 图示 含边(u,v)的圈假设G的任何一棵最小生成树都不含边(u,v)。将边(u,v)添加到G的一棵最小生成树T上，将产生含有边(u,v)的圈，并且在这个圈上有一条不同于(u,v)的边(u,v)，使得uU,vV-U，如下图所示。将边(u,v)删去，得到G的另一棵生成树T
22、。由于cuvcuv，所以T的耗费T的耗费。于是T是一棵含有边(u,v)的最小生成树，这与假设矛盾。2021/6/1341v构造最小生成树方法方法一：Prim算法v算法思想：设G=(V,E)是连通网，T是N上最小生成树中边的集合Y初始令U=u0,(u0V),T=Y在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)Y将(u0,v0)并入集合T，同时v0并入UY重复上述操作直至U=V为止，则T=(V,T)为N的最小生成树v算法实现：图用邻接矩阵表示v算法描述v算法评价：T(n)=O(n)2021/6/1342例1654326513566425131163141643142116
23、4321425165432142532021/6/1343方法二：Kruskal算法v算法思想：设G=(V,E)，令最小生成树Y初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量Y在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边Y依此类推，直至T中所有顶点都在同一连通分量上为止例1654326513566425165432123452021/6/1344v算法描述：uPrim算法与Kruskal算法的比较 从算法的时间复杂性看:当e=(n2)时，Kruskal算法比Prim算法差，但当e=o(
24、n2)时，Kruskal算法却比Prim算法好得多。u算法分析：设输入的连通赋权图有e条边，则将这些边依其权值组成优先队列需要O(e)时间；while循环中，DeleteMin运算需要O(loge)时间，因此关于优先队列所作运算的时间为O(eloge)。实现UnionFind所需的时间为O(eloge)。Kruskal算法所需的计算时间是O(eloge)。2021/6/1345v13.8 拓扑排序问题提出：学生选修课程问题顶点表示课程有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序定义vAOV网用顶点表示活动，用弧表示
25、活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继AOV网中不允许有回路，这意味着某项活动以自己为先决条件2021/6/1346v拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环拓扑排序的方法v在有向图中选一个没有前驱的顶点且输出之v从图中删除该顶点和所有以它为尾的弧v重复上述两步，直至全部顶点均已输出；或者当图中不存
26、在无前驱的顶点为止2021/6/1347例课程代号 课程名称 先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C122021/6/1348C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C
27、5-C7-C8一个AOV网的拓扑序列不是唯一的2021/6/1349C1C2C3C4C5C6C7C8C9C10C11C122021/6/1350C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2（2）2021/6/1351C4C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3（3）C5C6C7C8C9C10C11C12拓扑序列：C1-C2-C3-C4（4）2021/6/1352C6C8C10C11C12拓扑序列：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）2021/6/1353C6C8C12拓扑序列：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）拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12-C8（12）