图的定义和基本术语图的存储结构图的遍历生成树最短路径.PPT

《图的定义和基本术语图的存储结构图的遍历生成树最短路径.PPT》由会员分享，可在线阅读，更多相关《图的定义和基本术语图的存储结构图的遍历生成树最短路径.PPT（76页珍藏版）》请在三一办公上搜索。

1、图的定义和基本术语 图的存储结构 图的遍历 生成树 最短路径,第七章 图,图的定义和基本术语,一、图的定义,本章介绍另一种非线性数据结构 图,主要学习图的存储结构以及若干图的操作的实现。,图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。,图G由两个集合构成，记作G=(V,A)其中V是顶点的非空有限集合，A 是边的有限集合，其中边是顶点的无序对或有序对(此时的图称为无向图或有向图)。,无向图G1=(V1,A1)，V1=v0,v1,v2,v3,v4，A1=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4),无序对(vi,v

2、j)：用连接顶点vi、vj的线段表示，称为无向边；,有序对：用以为vi起点(弧尾)、以vj为终点(弧头)的有向线段表示，称为有向边或弧；,有向图G2=(V2,A2)，V2=v0 v1,v2,v3，A2=,例1 交通图（公路、铁路）顶点：地点 边：连接地点的路 交通图中的有单行道、双行道，分别用有向 边、无向边表示；例2 电路图 顶点：元件 边：连接元件之间的线路例3 通讯线路图 顶点：地点 边：地点间的连线例4 各种流程图(如生产流程图)顶点：工序 边：各道工序之间的顺序关系,图的实例,ADT Graph 数据对象V:V是具有相同特性的数据元素的集合，称为顶点集。,ADT 图 的 定 义,基本

3、操作:,CreateGraph(&G,V,V R)/按定义构造图 初始条件:V是图的顶点集,V R 是图中弧的集合。操作结果:按V和V R的定义构造图G。,数据关系R:R=VR VR=v,w V，且p(v,w),表 示从v到w 的弧，谓词p(v,w)定义 了弧的意义或信息。,DestroyGraph(&G)/销毁 初始条件:图G存在。操作结果:销毁图G。,LocateVex(G,u)/定位 初始条件:图G存在，u 和G中顶点有相同特性。操作结果:若G中存在顶点u，则返回该顶点在 图中位置；否则返回其它信息。,GetVex(G,v)/求值 初始条件:图G存在，v 是G中某个顶点。操作结果:返回v

4、的值。,PutVex(&G,v,value)/赋值 初始条件:图G存在，v 是G中某个顶点。操作结果:对 v 赋值value。,FirstAdjVex(G,v)/求第一个邻接点 初始条件:图G存在，v 是G中某个顶点。操作结果:返回 v 的第一个邻接点。若顶点v在 G 中没有邻接顶点，则返回“空”。,NextAdjVex(G,v,w)/求下一个邻接点 初始条件:图G存在，v 是G中某个顶点，w 是 v 的邻接点。操作结果:返回 v 的（相对于 w 的）下一个邻接点。若 w 是 v 的最后一个邻接点，则返回“空”。,InsertVex(/插入顶点 初始条件:图G存在，v和G中顶点有相同特性。操作

5、结果:在图G中增添新顶点v。,DeleteVex(&G,v)/删除顶点 初始条件:图G存在，v和G中顶点有相同特性。操作结果:删除G中顶点v及其相关的弧。,InsertArc(&G,v,w)/插入弧 初始条件:图G存在，v 和w是G中两个顶点。操作结果:在G中增添弧，若G是无向的，则还增添对称弧。,DeleteArc(&G,v,w)/删除弧 初始条件:图G存在，v 和w是G中两个顶点。操作结果:在G中删除弧，若G是无向的，则还删除对称弧。,DFSTraverse(G,v,Visit()/深度优先遍历 初始条件:图G存在，v 是G中某个顶点，Visit是顶点的应用函数。操作结果:从顶点v起深度优

6、先遍历图G，并对每 个顶点调用函数Visit一次且仅一次。一旦Visit（）失败，则操作失败。,BFSTraverse(G,v,Visit()/广度优先遍历 初始条件:图G存在，v 是G中某个顶点，Visit是顶点的应用函数。操作结果:从顶点v起广度优先遍历图G，并对每 个顶点调用函数Visit一次且仅一次。一旦Visit（）失败，则操作失败。,2 顶点的度、入度、出度 顶点v的度 TD(v)=与v相关联的边的数目。在有向图中：顶点v的出度OD(v)=以v为起点有向边数；顶点v的入度ID(v)=以v为终点有向边数；TD(v)=OD(v)+ID(v),二、图的基本术语,1 邻接点及关联边 邻接点

7、：边的两个顶点；关联边：若边e=(v,u),则称边e与顶点 v和u 相关联；,设图G的顶点数为n，边数为e则图的所有顶点的度数之和=2*e（每条边对图的所有顶点的度数之和“贡献”2度）,路径、回路(环)无向图G1=（V1，E1）中的顶点序列v1,v2,vk,若(vi,vi+1)E1(i=1,2,k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；在G1中，v0,v1,v2,v3 是v0到v3的路径；v0,v1,v2,v3,v0是回路；有向图G2=（V2，E2）中的顶点序列v1,v2,vk,E2(i=1,2,k-1),若v=v1,u=vk,则称该序列是从

8、顶点v到顶点u的路径；若v=u，则称该序列为回路；在G2中，v0,v2,v3是v0到v3的路径v0,v2,v3,v0是回路；,简单路径和简单回路 在一条路径中,若所有顶点各不相同,则称该路径为简单路径；若除起点和终点外,其余顶点各不相同的回路称为简单回路。,例,在图G1中，V0,V1,V2,V3 是简单路径；,V0,V1,V2,V4,V1不是简单路径；在图G2中，V0,V2,V3,V0是简单回路；,连通图（强连通图）在无（有）向图G=(V,E)中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图（强连通图）,非连通图,连通图,强连通图,非强连通图,设有两个图G=（V，E）、

9、G1=（V1，E1），若V1 V，E1 E，E1关联的顶点都在V1中，则称 G1是G的子图；,(a),(b),(c),5 子图,例 下列(b)、(c)是(a)的子图,(强)连通分量 无向图G的极大连通子图称为G的连通分量。极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通；,非连通图,非连通分量,有向图D 的极大强连通子图称为D 的强连通分量。极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。,V1,非强连通图,7 生成树 包含无向图G 所有顶点的极小连通子图称为G 的生成树。极小连通子图意思是：该子图是

10、G 的连通子图，在该子图中删除任何一条边，子图不再连通。,G的生成树,一棵n个顶点的生成树有且仅有足以构成树的n-1条边。,说明：,若在一棵生成树上删除一条边，就不再连通。,若在一棵生成树上添加一条边，必定构成一个环。,不再连通,构成环,图的存储结构,由于图中任意两个顶点之间都可能存在联系，因此难以以数据元素在存储区中物理位置表示它们间的关系，仍可以借助数组表示之。另一方面，用也可以多重链表示图。但由于图中顶点的度可能相差悬殊，会因此造成空间的浪费；反之，若按每个顶点的度设计不同的结点结构，又会造成操作上的不便。应根据具体的图和需要，设计恰当的结点结构和表结构。,图的存储结构至少要保存两类信息

11、：1)顶点的数据；2)顶点间的关系。,如何表示顶点间的关系？,？,常用图的存储表示,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,三、有向图的十字链表存储表示,四、无向图的邻接多重表存储表示,邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：,一、数组表示法(邻接矩阵表示),在数组表示法中，用邻接矩阵表示顶点间的关系,typedef struct ArcCell/弧的定义 VRType adj;/VRType是顶点关系类型。对无权图，/用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_

12、NUM MAX_VERTEX_NUM;,/图的数组(邻接矩阵)存储表示,#define INFINITY INT_MAX/最大值#define MAX_VERTEX_NUM 20/最大顶点个数typedef enumDG,DN,UDG,UDN graphkind；/有向图，有向网，无向图，无向网,typedef struct/图的定义 VertexType vexsMAX_VERTEX_NUM;/顶点向量保存顶点数据 AdjMatrix arcs;/邻接矩阵保存顶点间关系 int vexnum,arcnum;/顶点数，弧数 GraphKind kind;/图的种类标志 MGraph;,无向图数

13、组表示法特点：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；,对有向图的数组表示法可做类似的讨论,2）顶点v的度：等于二维数组对应行（或列）中1的个数；,3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否非零；,4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋非零值或清零；,5）用二维数组存储顶点数为 n的图,占用存储空间只与它的顶点数n有关，与边数e无关。适用于边稠密的图。,图的基本操作的实现(采用数组表示法)：1）求无向图某顶点vi的度：(或有向图vi的出度)Ai0 到Ain-1中的非零个数，即数组A第i行的非零元素的个数；,2）求有向图某顶点vi 的 入度：A0i

14、到An-1i 中的非零个数，即数组A中第i列的非零元素的个数；,3）求图中的总边数：扫描整个数组A，统计出数组中非零元素的个数。无向图的总边数为非零元素个数的一半，而有向图的总弧数为非零元素个数。,图的构造操作的实现(采用数组表示法),Status CreateGraph(Mgraph/CreateGraph,无向网的构造算法,Status CreateUDN(Mgraph/弧的权值 if(IncInfo)input(*G.arcsij.info)/若弧含有相关信息,则输入 G.arcsji=G.arcsij/置的对称弧 return OK/CreateUDN,例,1 无向图的邻接表 顶点通常

15、按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边用线性链表存储。,二、邻接表,该结点表示边（V4,Vj）,其中的j是Vj在一维数组中的位置,可见，在有向图的邻接表中不易找到指向该顶点的弧。,2 有向图的邻接表,在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧。,3 有向图的逆邻接表,typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode*nextarc;/指向下一条弧的指针 InfoType*info;/该弧相关信息的指针 ArcNode;/表结点,弧的结点结构,/图的邻接表存储表示,typedef struct

16、 VNode VertexType data;/顶点信息 ArcNode*firstarc;/指向第一条依附自该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;/头结点、头结点数组类型,data firstarc,顶点的结点结构,typedef struct AdjList vertices;int vexnum,arcnum;int kind;/图的种类标志 ALGraph;,图的结构定义(邻接表),无向图的邻接表的特点 1）在G邻接表中，同一条边对应两个表结点；2）顶点v的度：等于v对应线性链表的长度；3）判定两顶点v，u是否邻接：要看v对应线性链表中有无对应的结点u；4

17、）在G中增减边：在两个单链表插入、删除结点；5）设存储顶点的一维数组大小为m(m图的顶点数n),图的边数为e，G占用存储空间为：m+2e，与 G 的顶点数、边数均有关，适用于边稀疏的图。,0 1 2 3 4,V0V1V2V3V4,邻接表的空间代价与图的边及顶点数均有关,2,三、有向图的十字链表存储表示,弧的结点结构,指向下一个有相同弧尾的结点,指向下一个有相同弧头的结点,typedef struct ArcBox/弧的结构表示 int tailvex,headvex;InfoType*info;struct ArcBox*tlink,*hlink;ArcBox;,顶点的结点结构,顶点数据,指向

18、该顶点的第一条入弧,指向该顶点的第一条出弧,typedef struct VexNode/顶点的结构表示 VertexType data;ArcBox*firstin,*firstout;VexNode;,typedef struct VexNode xlistMAX_VERTEX_NUM;/顶点结点表头向量 int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;,有向图的结构表示(十字链表),v1v2v3v4,有向图的十字链表(图示）,若将有向图的邻接矩阵看成是稀疏矩阵的话，则十字链表也可以看成是邻接矩阵的链表存储结构。,四、无向图的邻接多重表存储表示,typede

19、f struct Ebox VisitIf mark;/访问标记 int ivex,jvex;/该边依附的两个顶点的位置 struct EBox*ilink,*jlink;/分别依附于这两个顶点的下一条边 InfoType*info;/该边信息指针 EBox;,边的结构表示,顶点的结构表示,typedef struct VexBox VertexType data;EBox*firstedge;/第一条依附该顶点的边的指针 VexBox;,顶点的数据 第一条依附该顶点的边的指针,typedef struct/邻接多重表 VexBox adjmulistMAX_VERTEX_NUM;int ve

20、xnum,edgenum;AMLGraph;,无向图的结构表示,在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。,图 的 遍 历,在图中，访问某个顶点后，可能沿着某条路径又回到该顶点。为保证每一个顶点只被访问一次，必须记下已被访问顶点，,有两种遍历方法：深度优先遍历和广度优先遍历,图的遍历算法是图的许多算法的基础。,一 深度优先遍历,1）从中某顶点v（起始点）出发，访问该顶点；2）依次从v的未被访问的邻接点出发，继续对图 进行深度优先遍历。直至图中所有和v有路径 相通的顶点都被访问到；,3）若图中尚有顶点未被访问，则另选一个

21、未被访 问顶点作起始点，重复1）、2），直至图中 所有顶点都被访问到为止。,步骤：,说明：(强)连通图的遍历只须执行1）和 2）两步。,V,w1,SG1,SG2,SG3,W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V;for(W1、W2、W3)若该邻接点Wi未被访问，则从它出发进行深度优先搜索遍历。,w2,w3,w2,V6,例,求图G以V0起始点的的深度优先序列,V0,V1,V4,V7,V3,V2,V5,V6,V0,V1,V3,V7,V4,V2,V5,图G,由于没有规定访问邻接点的顺序，深度优先序列不唯一,为保证每一个顶点

22、只被访问一次，必 须对顶点进行标记。一般用一个辅助数组 visited作为对顶点的标记，当顶点vi未被访问，visitedi值为FALSE；当vi已被访问，则visitedi值为TRUE或被访问时的次序号。,说明：,从深度优先搜索遍历连通图的过程类 似于树的先根遍历;,如果将图的顶点的未被访问邻接点看作树结点的孩子，图的深度优先遍历与树的先根遍历是类似的。,图的深度优先遍历 从图中某顶点v出发：（1）访问顶点v；（2）依次从v的未被访问的邻接点 出发，对图进行深度优先遍历。,树的先根遍历 若树非空（1）访问根结点；（2）依次先根遍历各 棵子树。,比较,类似,void DFSTraverse(G

23、raph G,Status(*Visit)(int v)/对图 G 作深度优先遍历 VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFS,Boolean visitedMAX；Status(*VisitFunc)(int v)；,void DFS(Graph G,int v)/从顶点v出发，深度优先搜索遍历连通图 G visitedv=TRUE;VisitFunc(v);for(w=FirstAdjVex(G

24、,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w，递归调用DFS/DFS,T,T,T,T,T,T,T,T,T,a,c,h,d,f,k,e,b,g,访问标志:,访问次序:,例如:,8,1,2,3,4,5,6,7,0,a,c,h,k,f,e,d,b,g,从图中某未访问过的顶点vi出发：1）访问顶点vi；2）依次访问 vi 的所有未被访问的邻接点；3）从这些邻接点出发，访问它们的所有未被未被访问的邻接点;依此类推，直到图中所有的顶点的邻接点都被访问。,由于没有规定访问邻接点的顺序，广度优先序列不唯一。你能写出一个不同的序

25、列吗？,例,求图G 的以V0起点的的广度优先序列,V0,V1,V2,V3,V4,V5,V6,V7,二 广度优先遍历（类似于树的按层遍历）,V,w1,w8,w3,w7,w6,w2,w5,w4,对连通图，从起始点V到其余各顶点必存在路径。,其中，V-w1,V-w2,V-w8 的路径长度为1;,V-w7,V-w3,V-w5的路径长度为2;,V-w6,V-w4 的路径长度为3。,w1,V,w2,w7,w6,w3,w8,w5,w4,说明：在广度优先遍历图时，“先被访问的顶点的邻接点”先于“后被访问的顶点的邻 接点”被访问。即以V为起 始点，由近至远，依次访问 和V有路径相通且路径长度 为1，2，的顶点。

26、,在广度优先遍历中,为使“先被访问的顶点,其邻接点亦先被访问”,需附设队列Q保存被访问过的顶点，并控制遍历顶点的顺序。,V0,V1,V2,V3,V4,V5,V6,V7,V1,V2,V3,V0,V4,V5,V6,V7,算法开始时,将起始点访问后插入Q中,以后,当Q不空时就从Q中删除一个顶点,每删除一个顶点,就依次访问它的每一个未被访问过的邻接点,并令其进队。这样,当Q为空时,表明所有与起始点有路径相通的顶点都已访问完毕。,void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问

27、标志 InitQueue(Q);/置空的辅助队列Q for(v=0;vG.vexnum;+v)if(!visitedv)/v 尚未访问 visitedv=TRUE;Visit(v);EnQueue(Q,v);/v入队列 while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为u for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/BFSTraverse,图的广度优先遍历算法,求一条从顶点 i 到顶点 s 的简单路径,求从顶点 b

28、到顶点 k 的 一条简单路径。,从顶点 b 出发进行深度优先搜索遍历,例如:,假设找到的第一个邻接点是a,则得到的结点访问序列为:b a d h c e k f g,假设找到的第一个邻接点是c,则得到的结点访问序列为:b c h d a e k f g,遍历应用的一个例子,无向连通图G的生成树 生成树是一个图G 的一个极小的连通子图，包含图G 的所有顶点，但只有n-1 条边。生成树可由遍历过程中所经过的边组成。深度优先遍历得到的生成树称为深度优先生成树；广度优先遍历得到的生成树称为广度优先生成树。,V0,深度优先生成树,(连通网的)最小生成树,广度优先生成树,在n个城市间建立通讯联络网，要考虑

29、的问题是:如何在保证n点连通的前提下最节省经费,3,6,5,2,1,6,5,5,4,6,例,即要构造连通网N的最小生成树。这应在 N的所有带权的边中选取 n1 条边（不构成回路），使权值之和为最小。,？,最小生成树（最小支撑树）最小生成树是无向连通网的所有生成树中边的权值之和最小的一棵生成树。,最小生成树的构造算法,MST性质：,多数最小生成树的构造算法都利用了下述性质。,设N=（V，E）是一个连通网，U V，U。若（u,v）是一条具最小有权值的边，其中u U，v VU，则必存在一棵包含边（u,v）的最小生成树。,（可用反证法证之）,普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是利

30、用MST性质的两种构造最小生成树的算法。,1.普里姆算法,普里姆算法的基本思想:,贪心算法,任取一图N中顶点v 作为生成树的根，之后不断往“生成树的顶点集”U上添加顶点 w(VU)。新添的顶点 w 和已在U的顶点v 之间必定存在一条边(v,w)：(v,w)权值在所有连通顶点 v(U)和 w(VU)之间的边中权值最小的，并将(v,w)并入“生成树的边集”TE中。直至U=V（TE中有 n-1条边）为止。,V3,V1,V4,V6,V5,V2,普里姆算法构造最小生成树的过程,V3,V1,V4,V6,V5,V2,U,V-U,TE,V3,V1,V4,V6,V5,V2,(v1,v3),(v3,v6),(v6

31、,v4),(v3,v2),(v2,v5),为实现此算法需设置辅助数组closedge，对当前VU中每个顶点，记录从U到VU的代价最小的边：,struct VertexType adjvex;/U集中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTEX_NUM;,显然，对vi VU有closedge i-1.lowcost=Mincost(u,vi)|u U,i,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,16,e,21,e,d,c,b,a,g,f,a b c d e f g,所得生成

32、树权值和=14+8+3+5+16+21=67,构造最小生成树的普里姆算法,void MiniSpantree_PRIM(mgraph G,VertexType u)辅助数组closedge的定义 k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.arj;closedgek.lowcost=0;/起始点u并入U(=u),for(i=1;iG.vexnum;+i)/,k=mininum(closedge);/求下一个顶点：第k顶点printf(closedgek.adjvex,G.vexsk)/输

33、出生成树的边closedgek.lowcost=0;/第k顶点并入U,for(j=0;jG.vexnum;+j)/重新选择最小边 if(G.arcskj.arj closedgej.lowcost)closedgej=G.vexsk,G.arcskj.arj,具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,克鲁斯卡尔算法的基本思想：,14,8,5,3,16,21,例如:,7,12

34、,18,19,c,d,b,a,e,g,f,27,最短路径,一、从某个源点到各顶点的最短路径,V5,V4,100,60,5,30,10,V1,V2,V0,V3,10,20,50,v0 v1 无,v2(v0,v2)10,v5(v0,v4,v3,v5)60,v4(v0,v4)30,v3(v0,v4,v3)50,迪杰斯特拉(Dijkstra)算法,迪杰斯特拉提出一个求按路径长度递增次序产生的最短路径算法。其基本思想为:设置S为已求得最短路径的终点的集合，并用数组D记录当前所找到的从源点v到每个终点的最短特殊路径长度（特殊路径或是弧，或是中间只经过S中顶点的路径）。初始时，S为空；Di值为源v到每个顶点

35、vi的权值。按以下方法不断扩充S：每次从V S中取出具有最短特殊路径长度的顶点添加到S中，同时对D作必要的修改(若Dj+arcsjk Dk，则 Dk=Dj+arcsjk)。一旦S=V-v(S共扩充n-1次)，D就记录了从源v到其他顶点vi的最短路径长度（若欲求相应的路径还应另设数组P）。,10 30 100,10,V2,V4,V3,V5,V4,V2,V0,V3,60,30,50,90,50,60,V5,V2,V4,V3,V5,V1,60,V1,源点,迪杰斯特拉算法 之一,void ShortPath_DIJ(mgraph G,int v0,PathMatrix/初始化，v0顶点属于S集,迪杰斯

36、特拉算法 之二,/开始主循环，每次求得v0到某个v顶点的最短路径，/并加v到S集。for(i=0;iG.vexnum;+i)/其余G.vexnum-1个 min=INFINITY/当前所知离v0的最近距离 for(w=0;wG.vexnum;+w)if(!final)/w在VS中 if(Dw min)v=w;min=Dw;/w离v0更近 finalv=TRUE;/离v0最近的加入S集 for(w=0;wG.vexnum;+w)/更新当前最短路径/及距离 if(!finalw,二、每一对顶点之间的最短路径,解该问题固然可用下述方法：每次以顶点为源点，重复执行Dijkstra算法n次。但较麻烦。弗洛伊德(Floyd)提出另一个较直接的算法。仍以邻接矩阵出发，其基本思想是：,假设求从顶点vi 到vj最短路径。若从vi到vj 有弧，但该路径未必最短，尚需n次试探：1),void ShortPath_FLoyD(mgraph G,PathMatrix,弗洛伊德算法 之一,for(u=0;uG.vexnum;+u)for(v=0;vG.vexnum;+v)for(w=0;wG.vexnum;+w)if(Dvu+Duw Dvw)/从v经u到w的一条路径更短 Dvw=Dvu+Duw;for(i=0;iG.vexnum;+i)Pvwi=Pvwi+Pvwi;,弗洛伊德算法 之二,