图本章说明课件.ppt

《图本章说明课件.ppt》由会员分享，可在线阅读，更多相关《图本章说明课件.ppt（129页珍藏版）》请在三一办公上搜索。

1、本 章 说 明7.1 图的定义和术语7.2 图的存储结构 7.3 图的遍历 7.4 生成树7.5 拓扑排序7.6 最短路径 本 章 小 结,数据结构,返回主目录,学习目标领会图的类型定义。熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。熟练掌握图的两种遍历算法。理解各种图的应用问题的算法。,本章说明,重点和难点图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。知识点图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径,本章说明,7.1 图的定义和术语,图

2、(Graph)图G是由两个集合V和VR组成的，记为G=(V,VR)其中：V是顶点的有穷非空有限集 VR是两个顶点之间关系的有限集合，即边集合，边是顶点的无序对或有序对,有向图有向图G是由两个集合V和VR组成的 其中：V是顶点的有穷非空有限集 VR是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头,7.1 图的定义和术语,例如:,G1=(V1,VR1),其中V1=1,2,3,4VR1=,7.1 图的定义和术语,无向图由顶点集和边集构成的图。若VR 必有VR,则称(v,w)为顶点 v 和顶点 w 之间存在一条边。,例如:G2=(V2,VR2)V2=A,B,C,D

3、,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),7.1 图的定义和术语,有向完全图有n个顶点，n(n-1)弧的有向图 无向完全图有n个顶点，n(n-1)/2条边的无向图,7.1 图的定义和术语,稀疏图有很少条边和弧(enlogn)的图 稠密图与稀疏图相反 权与图的边或弧相关的数 网带权的图 有向网弧带权的图 无向网边带权的图,15,9,7,21,11,3,2,子图如果图G(V，E)和图G(V，E)，满足：V V 且 E E，则称G为G的子图 邻接点在无向 图中一条边连起来 的两个顶点(v,v)，互称邻接点，称边(v,v)依附于顶点 v和v,7

4、.1 图的定义和术语,B,7.1 图的定义和术语,顶点的度(TD)=出度(OD)+入度(ID),例如:,ID(B)=2,OD(B)=1,TD(B)=3,顶点的度 无向图中顶点的度为与每个顶点相连的边数 有向图中顶点的度为:入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目,7.1 图的定义和术语,路径路径是一个顶点的序列V=Vi,0,Vi,1,Vi,n，满足(Vi,j-1,Vi,j)E 或 E,(1jn)路径上边的数目称作“路径长度”回路（环）第一个顶点和最后一个顶点相同的路径 简单路径序列中顶点不重复出现的路径 简单回路除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路,7.1

5、 图的定义和术语,连通从顶点V到顶点W有一条路径，则说V和W是连通的连通图图中任意个顶点都是连通的,路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3,连通分量指的是无向图中的极大连通子图强连通图有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj 和从Vj到 Vi都存在路径强连通分量指的是有向图中的极大强连通子图,7.1 图的定义和术语,7.1 图的定义和术语,生成树是连通图的一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的n-1条边生成森林对非连通图，各个连通分量的生成树的集合,一个有向图及其生成森林,

6、7.2 图的存储结构,图的数组(邻接矩阵)存储表示,图的邻接表存储表示,有向图的十字链表存储表示,无向图的邻接多重表存储表示,7.2 图的存储结构,邻接矩阵表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵,图的数组(邻接矩阵)存储表示,7.2 图的存储结构,7.2 图的存储结构,特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中:顶点Vi的出度是A中第i行元素之和顶点Vi的入度是

7、A中第i列元素之和网的邻接矩阵可定义为：,7.2 图的存储结构,7.2 图的存储结构,邻接矩阵的优缺点 优点：容易实现图的创建、销毁、查找顶点v和返回v的值操作。容易判定顶点间有无边（弧），容易计算顶点的度（出度、入度）缺点：所占空间只和顶点个数有关，和边数无关，在边数较少时，空间浪费较大,邻接矩阵的存储表示#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef enum DG,DN,AG,AN GraphKind;/有向图，有向网，无向图，无向网,7.2 图的存储结构,typedef struct ArcCell/邻接矩阵 VRTyp

8、e adj;/顶点关系类型 InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点向量 AdjMatrix arcs;/弧的信息 int vexnum,arcnum;/顶点数和弧数 GraphKind kind;/图的种类MGraph;,7.2 图的存储结构,建立无向图邻接矩阵的算法 算法中：G.vexs，一维，顶点向量.arcs，二维，邻接矩阵.vexnum，顶点数.arcnum，边数,7.2 图的存储结构,图

9、的邻接表存储表示,邻接表是图的一种链式存储结构，为依附每个顶点的边（或弧）建立一个单链表 顶点结构,顶点位置,下一条弧,相关信息,顶点数据,第一条弧,7.2 图的存储结构,7.2 图的存储结构,图的邻接表存储表示,#define MAX_VERTEX_NUM 20Typedef struct ArcNode/表结点 int Adjvex;/与vi邻接的顶点的下标位置 struct ArcNode*nextarc;/与vi邻接的下一个顶点 InfoType*info;/ArcNode;Typedef struct Vnode/头结点 VertexType data;ArcNode*firstar

10、c;Vnode,AdjListMAX_VERTEX_NUM;Typedef struct/图 AdjList vertices;int vexnum,arcnum,kind;ALGraph;,7.2 图的存储结构,邻接表是顶点的向量结构和边（弧）的单链表结构 每个顶点结点包括两个域，将n个顶点放在一个向量中（称为顺序存储的结点表）；一个顶点的所有邻接点链接成单链表，该顶点在向量中有一个指针域指向其第一个邻接点。邻接表的优缺点 空间较省；无向图容易求各顶点的度；表中结点个数是边的两倍；有向图容易求顶点的出度；不容易求顶点的入度，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点

11、链接成单链表）,7.2 图的存储结构,建立邻接表的算法,逆邻接表 第i(下标i-1)链表的结点个数即为Vi顶点的入度。,7.2 图的存储结构,有向图的十字链表存储表示,十字链表结点结构,弧尾位置,弧头位置,弧尾相同的下一条弧指针,弧相关信息的指针,弧头相同的下一条弧指针,指向该顶点第一条入弧,指向该顶点第一条出弧,7.2 图的存储结构,例,7.2 图的存储结构,有向图十字链表存储表示,#define MAX_VERTEX_NUM 20typedef struct ArcBox/弧结点 int tailvex,hesdvex;struct ArcBox*hlink,*tlink;infoType

12、*info;ArcBox;Typedef struct VexNode/顶点结点 VertexType data;ArcBox*firstin,*firstout;VexNode;Typedef struct/顶点表 VexNode xlistMAX_VERTEX_NUM;/表头向量 int vexnum,arcnum;OLGraph;,7.2 图的存储结构,建立有向图十字链表算法 思想：（1）初始化表头向量、数据、指针（2）输入一条弧，确定在G中位置，申请结点空间，赋值（3）插入到十字链表中（4）若InInfo=1，输入其信息（5）重复（2）至（4），直到所有弧输入完为止。,7.2 图的存储

13、结构,无向图的邻接多重表存储表示,邻接多重表结点结构,i顶点,下一个依附于i顶点的边,j顶点,下一个依附于j顶点的边,第1个依附于该顶点的边,7.2 图的存储结构,例,指向下一个依附于v1的边,指向下一个依附于v2的边,7.2 图的存储结构,无向图邻接多重表存储表示,#define MAX_VERTEX_NUM 20Typedef emnu unvisited,visited VisitIf;typedef struct ArcBox/弧结点 VisitIf mark;int ivex,jvex;struct EBox*ilink,*jlink;infoType*info;EBox;Typed

14、ef struct VexBox/顶点结点 VertexType data;EBox*firstedge;/指向第1条依附该顶点的边VexBox;Typedef struct/顶点表 VexBox adjlistMAX_VERTEX_NUM;int vexnum,arcnum;AMLGraph;,7.3 图的遍历,从图的某顶点出发，对图中的每个顶点进行一次访问且使每个顶点仅被访问一次的过程。,深度优先遍历,广度优先遍历,7.3 图的遍历,思想：（1）从图的某一顶点V0出发，访问该顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；（2）若此时图中

15、尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止,深度优先遍历,7.3 图的遍历,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,V1,V2,V4,V5,V3,V7,V6,V8,7.3 图的遍历,例2：V1 V2 V4 V8 V5 V6 V3 V7,例3：V1 V2 V4 V8 V5 V6 V3 V7,例4：V1 V2 V4 V8 V3 V6 V7 V5,7.3 图的遍历,从上面例可见:,1.从深度优先搜索遍历连通图的过程类似于树的先根遍历;,解决的办法是:为每个顶点设立一个“访问标志 visitedw”;,2.如何判别V的邻接点是否被

16、访问？,7.3 图的遍历,深度优先遍历算法,7.3 图的遍历,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例如:,a,c,h,d,k,f,e,7.3 图的遍历,广度优先搜索,思想（1）从图的某一顶点V0出发，访问该顶点后，依次访问V0的各个未被访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到（2）若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止,7.3 图的遍历,广度遍历：V1 V2 V3 V4

17、V5 V6 V7 V8,V1,V4,V5,V3,V7,V8,V2,V6,7.3 图的遍历,例2：V1 V2 V3 V4 V5 V6 V7 V8,例3：V1 V2 V3 V4 V5 V6 V7 V8,例4：V1 V2 V3 V4 V6 V7 V8 V5,7.3 图的遍历,广度优先遍历算法 思想：借助队列,7.3 图的遍历,7.4 生成树,生成树,最小生成树,构造最小生成树,7.4 生成树,生成树 定义：所有（n个）顶点均由边（n-1个）连接在一起，但不存在回路的图 深度优先生成树：由深度优先遍历得到的生成树 广度优先生成树：由广度优先遍历得到的生成树 生成森林：非连通图每个连通分量的生成树一起组

18、成非连通图,7.4 生成树,说明 一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路 含n个顶点n-1条边的图不一定是生成树,7.4 生成树,深度：V1 V2 V4 V8 V5V3 V6 V7,广度：V1 V2 V3 V4 V5V6 V7 V8,7.4 生成树,例,深度优先生成森林,7.4 生成树,最小生成树问题提出 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的

19、前提下建立这个通讯网？顶点表示城市权城市间建立通信线路所需花费代价 最小（代价）生成树：希望找到一棵生成树，它的每条边上的权值之和即建立该通信网所需花费的总代价）最小,7.4 生成树,问题分析 n个城市间，最多可设置n(n-1)/2条线路 n个城市间建立通信网，只需n-1条线路 该问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。,7.4 生成树,构造最小生成树方法方法一：普里姆(Prim)算法（选点法）思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合（1）初始令U=u0,(u0V),TE=（2）在所有uU,vV-U的边(

20、u,v)E中，找一条代价最小的边(u0,v0)（3）将(u0,v0)并入集合TE，同时v0并入U（4）重复上述操作直至U=V为止，则 T=(V,TE)为N的最小生成树树存储结构：邻接矩阵表示算法实现算法评价：O(n),7.4 生成树,例,1,7.4 生成树,方法二：克鲁斯卡尔算法（选边法）思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合（1）初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分（2）在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边（3）依此类推，直至T中所有顶点都在同

21、一连通分量上为止,7.4 生成树,例,7.4 生成树,算法描述：构造非连通图 ST=(V,);k=i=0;/k 计选中的边数 while(kn-1)+i;检查边集 E 中第 i 条权值最小的边(u,v);若(u,v)加入ST后不使ST中产生回路，则 输出边(u,v);且 k+;,7.4 生成树,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(eloge),稠密图,稀疏图,算法名,适应范围,比较两种算法,7.5 拓扑排序,有向无环图,拓扑排序,关键路径,7.5 拓扑排序,有向无环图：一个无环的有向图（DAG）是描述一项工程或系统的进行过程的有效工具。,7.5 拓扑排序,问题提出：学生选修

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

23、序列中，则该AOV网必定不存在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止,7.5 拓扑排序,例,7.5 拓扑排序,拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一个AOV网的拓扑序列不是唯一的,7.5 拓扑排序,7.5 拓扑排序,7.5 拓扑排序,7.5 拓扑排序,7.5 拓扑排序,C8,7.5 拓扑排序,算法实现 以邻接表作存储结构 把邻接表中所有入度为0的顶

24、点进栈 栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕,7.5 拓扑排序,1,6,算法描述,入度,7.5 拓扑排序,输出序列：6,7.5 拓扑排序,输出序列：6,7.5 拓扑排序,输出序列：6,7.5 拓扑排序,输出序列：6,7.5 拓扑排序,输出序列：6,7.5 拓扑排序,输出序列：6,7.5 拓扑排序,输出序列：6 1,7.5 拓扑排序,输出序列：6 1,7.5 拓扑排序,输出序列：6 1,4,7.5 拓扑排序,输出序列：6 1,4,7.5

25、 拓扑排序,输出序列：6 1,4,7.5 拓扑排序,输出序列：6 1,4,3,7.5 拓扑排序,输出序列：6 1,4,3,7.5 拓扑排序,输出序列：6 1,4,3,7.5 拓扑排序,输出序列：6 1,4,3,7.5 拓扑排序,输出序列：6 1,4,3,7.5 拓扑排序,输出序列：6 1 3,4,3,7.5 拓扑排序,输出序列：6 1 3,4,7.5 拓扑排序,输出序列：6 1 3,4,7.5 拓扑排序,输出序列：6 1 3,4,7.5 拓扑排序,输出序列：6 1 3,4,2,7.5 拓扑排序,输出序列：6 1 3,4,2,7.5 拓扑排序,输出序列：6 1 3,4,2,7.5 拓扑排序,输出

26、序列：6 1 3 2,4,2,7.5 拓扑排序,输出序列：6 1 3 2,4,7.5 拓扑排序,输出序列：6 1 3 2 4,4,7.5 拓扑排序,输出序列：6 1 3 2 4,7.5 拓扑排序,输出序列：6 1 3 2 4,5,7.5 拓扑排序,输出序列：6 1 3 2 4,5,7.5 拓扑排序,输出序列：6 1 3 2 4 5,5,7.5 拓扑排序,输出序列：6 1 3 2 4 5,7.5 拓扑排序,算法分析,建邻接表：T(n)=O(e)搜索入度为0的顶点的时间：T(n)=O(n)拓扑排序：T(n)=O(n+e),7.5 拓扑排序,问题提出,假设以有向网表示一个施工流图，弧上的权值表示完成

27、该项子工程所需时间。问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元进行化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。,例如：有一个工程有11项活动，9个事件(v1-v9)v1-表示整个工程开始v9-表示整个工程结束,7.5 拓扑排序,定义AOE网(Activity On Edge)即边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间路径长度路径上各活动持续时间之和关键路径路径长度最长的路径Ve(j

28、)表示事件Vj的最早发生时间Vl(j)表示事件Vj的最迟发生时间e(i)表示活动ai的最早开始时间l(i)表示活动ai的最迟开始时间l(i)-e(i)表示完成活动ai的时间余量关键活动关键路径上的活动，即l(i)=e(i)的活动,7.5 拓扑排序,整个工程完成的时间为：从有向图的源点到汇点的最长路径。,例如:,“关键活动”指的是：该弧上的权值增加 将使有向图上的最长路径的长度增加。,源点,汇点,6,1,7,4,7.5 拓扑排序,如何求关键活动？,该活动的最早开始时间=该活动的最迟开始时间,i,j,dut,问题分析,持续时间,7.5 拓扑排序,“事件(顶点)”的 最早发生时间 ve(j)ve(j

29、)=从源点到顶点j的最长路径长度;,“事件(顶点)”的 最迟发生时间 vl(k)vl(k)=从顶点k到汇点的最短路径长度;,7.5 拓扑排序,假设第 i 条弧为 则 对第 i 项活动言“活动(弧)”的 最早开始时间 ee(i)ee(i)=ve(j);“活动(弧)”的 最迟开始时间 el(i)el(i)=vl(k)dut();,7.5 拓扑排序,事件发生时间的计算公式:ve(源点)=0;ve(k)=Maxve(j)+dut()vl(汇点)=ve(汇点);vl(j)=Minvl(k)dut(),7.5 拓扑排序,拓扑有序序列:1-4-6-3-2-5-8-7-9,0,0,0,0,0,0,0,0,0,

30、6,4,5,7,11,5,7,15,14,18,18,18,18,18,18,18,18,18,18,16,14,8,6,6,10,8,0,7,7.5 拓扑排序,0,6,4,5,7,7,15,14,18,18,14,16,10,7,8,6,6,0,0,0,0,6,4,5,7,7,7,15,14,14,16,0,2,3,6,6,8,8,7,10,7.5 拓扑排序,求关键路径步骤求Ve(i)求Vl(j)求e(i)求l(i)计算l(i)-e(i),7.5 拓扑排序,算法实现以邻接表作存储结构从源点V1出发，令Ve1=0,按拓扑序列求各顶点的Vei从汇点Vn出发，令Vln=Ven,按逆拓扑序列求其余各

31、顶点的Vli根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动,要点：显然，求ve的顺序应该是按拓扑有序的次序;而 求vl的顺序应该是按拓扑逆序的次序;因为 拓扑逆序序列即为拓扑有序序列的逆序列，因此 应该在拓扑排序的过程中，另设一个“栈”记下拓扑有序序列。,7.5 拓扑排序,算法描述输入顶点和弧信息，建立其邻接表计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的Vei将得到的拓扑序列进栈按逆拓扑序列求顶点的Vli计算每条弧的ei和li,找出ei=li的关键活动,改写算法7.12,7.6 最短路径,每一对顶点 之间的最短路径,从某个源点到 其余各点的最短路径,7.6

32、最短路径,问题提出,用带权的有向图表示一个交通运输网图中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等,问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径,7.6 最短路径,从某个源点到其余各顶点的最短路径,7.6 最短路径,求从源点到其余各点的最短路径的算法的基本思想:,依最短路径的长度递增的次序求得各条路径,源点,v1,其中，从源点到顶点v1的最短路径是所有最短路径中长度最短者。,v2,7.6 最短路径,在这条路径上，必定只含一条弧，并且这条弧是所有从源点出发的弧中权值最小。,下一条路径长度次短的最短路径的特

33、点:,路径长度最短的最短路径的特点:,它只可能有两种情况:或者是直接从源点到该点(只含一条弧)；或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)。,7.6 最短路径,其余最短路径的特点：,再下一条路径长度次短的最短路径的特点:,它可能有三种情况：或者是，直接从源点到该点(只含一条弧)；或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是，从源点经过顶点v2，再到达该顶点。,它或者是直接从源点到该点(只含一条弧)；或者是，从源点经过已求得最短路径的顶点，再到达该顶点。,7.6 最短路径,求最短路径的迪杰斯特拉算法：,一般情况下:Distk=或者=+,设置辅助数组Dist，其中

34、每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径。,7.6 最短路径,1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。,2）修改其它各顶点的Distk值。假设求得最短路径的顶点为u，若 Distu+G.arcsukDistk则将 Distk 改为 Distu+G.arcsuk,V0和k之间存在弧,V0和k之间不存在弧,其中的最小值即为最短路径的长度。,7.6 最短路径,顶点 a 为源点，设定dist和path的初始值，顶点 a 并入集合 S,选出 dist 中的最小值在 i=2，求得第一条最短路径ac,顶点 c 并入集合 S,考察从顶点 c 出发的弧

35、，修正集合V-S中顶点的 dist 和path 的值,选出 dist 中的最小值在 i=5，求得第 2 条最短路径acf,顶点 f 并入集合 S,考察从顶点 f 出发的弧，修正集合V-S中顶点的 dist 和path 的值,选出 dist 中的最小值在 i=4，求得第 3 条最短路径acfe,顶点 e 并入集合 S,考察从顶点 e 出发的弧，修正集合V-S中顶点的 dist 和path 的值,选出 dist 中的最小值在 i=3，求得第 4 条最短路径ad,顶点 d 并入集合 S,考察从顶点 d 出发的弧，修正集合V-S中顶点的 dist 和path 的值,选出 dist 中的最小值在 i=6

36、，求得第 5 条最短路径adg,顶点 g并入集合 S,考察从顶点 g 出发的弧，修正集合V-S中顶点的 dist 和path 的值,选出 dist 中的最小值在 i=1，求得第 6 条最短路径adgb,顶点 b并入集合 S,a,c,f,e,d,g,b,7.6 最短路径,求每一对顶点之间的最短路径,方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次 T(n)=O(n),方法二：弗洛伊德(Floyd)算法算法思想：逐个顶点试探法求最短路径步骤,7.6 最短路径,依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。,若存在，则存在路径vi,vj/路径中不含其它顶点若,存在，则存在路径vi,v1,vj/路径中所含顶点序号不大于1若vi,v2,v2,vj存在，则存在一条路径vi,v2,vj/路径中所含顶点序号不大于2,本章小结,1.熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。2.熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。,本章小结,3.熟练掌握最小生成树的构造方法，选点法和选边法。4。熟练掌握拓扑排序方法4.理解求解关键路径和两顶点间最短路径问题。5.理解教科书中讨论的各种图的算法。,