图的定义和基本术语图的存储结构图的遍历生成树最短路径.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) ,

2、(v2,v3) , (v2,v4) ,无序对(vi ,vj)： 用连接顶点vi、vj的线段 表示，称为无向边；,有序对 ： 用以为vi起点(弧尾)、以vj为终点(弧头) 的有向线段表示，称为有向边或弧；,有向图G2=(V2, A2)， V2=v0 v1,v2,v3 ， A2= , , , ,例1 交通图（公路、铁路） 顶点：地点 边：连接地点的路 交通图中的有单行道、双行道，分别用有向 边、无向边表示； 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 例4 各种流程图(如生产流程图) 顶点：工序 边：各道工序之间的顺序关系,图的实例,ADT G

3、raph 数据对象V : V是具有相同特性的数据元素的集合， 称为顶点集。,ADT 图 的 定 义,基本操作 :,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中顶点有相同特

4、性 。 操作结果: 若G中存在顶点u ，则返回该顶点在 图中位置 ；否则返回其它信息。,GetVex(G, v)/ 求值 初始条件:图G存在，v 是G中某个顶点。 操作结果:返回v的值。,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中某个顶

5、点， w 是 v 的邻接点 。 操作结果: 返回 v 的（相对于 w 的）下一个邻接点。 若 w 是 v 的最后一个邻接点，则返回“空”。,InsertVex( / 插入顶点 初始条件:图G存在，v和G中顶点有相同特性 。 操作结果: 在图G中增添新顶点v。,DeleteVex(&G, v) /删除顶点 初始条件: 图G存在， v和G中顶点有相同特性 。 操作结果:删除G中顶点v及其相关的弧。,InsertArc(&G, v, w) /插入弧 初始条件:图G存在，v 和w是G中两个顶点。 操作结果:在G中增添弧，若G是无向的， 则还增添对称弧。,DeleteArc(&G, v, w) /删除弧

6、 初始条件:图G存在，v 和w是G中两个顶点。 操作结果:在G中删除弧，若G是无向的， 则还删除对称弧。,DFSTraverse(G, v, Visit() /深度优先遍历 初始条件:图G存在，v 是G中某个顶点， Visit是顶点的应用函数 。 操作结果: 从顶点v起深度优先遍历图G，并对每 个顶点调用函数Visit一次且仅一次。 一旦Visit（）失败，则操作失败。,BFSTraverse(G, v, Visit() /广度优先遍历 初始条件:图G存在，v 是G中某个顶点， Visit是顶点的应用函数 。 操作结果: 从顶点v起广度优先遍历图G，并对每 个顶点调用函数Visit一次且仅一次

7、。 一旦Visit（）失败，则操作失败。,2 顶点的度、入度、出度 顶点v的度 TD(v)= 与v相关联的边的数目。 在有向图中：顶点v的出度OD(v) =以v为起点有向边数； 顶点v的入度ID(v) =以v为终点有向边数； TD(v) = OD(v) + ID(v),二、图的基本术语,1 邻接点及关联边 邻接点：边的两个顶点； 关联边：若边e= (v, u), 则称边e与顶点 v和u 相关联；,设图G的顶点数为n，边数为e 则图的所有顶点的度数之和 = 2*e （每条边对图的所有顶点的度数之和 “贡献” 2度）,路径、回路(环) 无向图G1=（V1，E1）中的顶点序列v1,v2, ,vk,若

8、(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,则称该 序列是从顶点v到顶点u的路径；若v=u，则称该序 列为回路；在G2中， v0, v2, v3是v0到v3的路径 v0,v2,v3,v0是回路；,简单路径和简单回路 在一条路径中,若所有顶点各不相同,则称该路径为简单路径；若除起点和

9、终点外, 其余顶点各不相同的回路称为简单回路。,例,在图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）、G1= （V1，E1）， 若V1 V，E1 E，E1关联的顶点都在V1中， 则称 G1是G的子图；,(a),(b),(c),5 子图,例 下列 (b)、(c) 是 (a) 的子图,(强)连通分量 无向

10、图G的极大连通子图称为G的连通分量。 极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通；,非连通图,非连通分量,有向图D 的极大强连通子图称为D 的强连通分量。极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。,V1,非强连通图,7 生成树 包含无向图G 所有顶点的极小连通子图称为G 的生成树。极小连通子图意思是：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。,G的生成树,一棵n个顶点的生成树有且仅有足以构成树的n-1条边。,说明：,若在一棵生成树上删除一条边，就不再连通。,若在一棵生

11、成树上添加一条边，必定构成一个环。,不再连通,构成环,图的存储结构,由于图中任意两个顶点之间都可能存在联系，因此难以以数据元素在存储区中物理位置表示它们间的关系，仍可以借助数组表示之。 另一方面，用也可以多重链表示图。但由于图中顶点的度可能相差悬殊，会因此造成空间的浪费；反之，若按每个顶点的度设计不同的结点结构，又会造成操作上的不便。 应根据具体的图和需要，设计恰当的结点结构和表结构。,图的存储结构至少要保存两类信息： 1)顶点的数据； 2)顶点间的关系。,如何表示顶点间的关系？,？,常用图的存储表示,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,三、有向图的十字链表存储表示,四、

12、无向图的邻接多重表存储表示,邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：,一、数组表示法(邻接矩阵表示),在数组表示法中， 用邻接矩阵表示顶点间的关系,typedef struct ArcCell / 弧的定义 VRType adj;/VRType是顶点关系类型。对无权图， /用1或0表示相邻否；对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell , AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;,/ 图的数组(邻接矩阵)存储表示,#define INFINITY INT_MAX /最大值 #define MAX

13、_VERTEX_NUM 20/最大顶点个数 typedef enumDG,DN,UDG, UDN graphkind； /有向图，有向网，无向图，无向网,typedef struct /图的定义 VertexType vexsMAX_VERTEX_NUM; /顶点向量保存顶点数据 AdjMatrix arcs; /邻接矩阵保存顶点间关系 int vexnum, arcnum; /顶点数，弧数 GraphKind kind; /图的种类标志 MGraph;,无向图数组表示法特点： 1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；,对有向图的数组表示法 可做类似的讨论,2）顶点v的度：等于二维数

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

15、个数。无向图的总边数为非零元素个数的一半，而有向图的总弧数为非零元素个数。,图的构造操作的实现(采用数组表示法),Status CreateGraph(Mgraph / CreateGraph,无向网的构造算法,Status CreateUDN(Mgraph /弧的权值 if (IncInfo) input(* G.arcsij.info) /若弧含有相关信息,则输入 G.arcsji= G.arcsij /置的对称弧 return OK / CreateUDN,例,1 无向图的邻接表 顶点通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边用线性链表存储。,二、邻接表,该结点表示边（V

16、4, Vj）,其中的j是Vj在一维数组中的位置,可见，在有向图的邻接表中不易找到指向该顶点的弧。,2 有向图的邻接表,在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧。,3 有向图的逆邻接表,typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode; / 表结点,弧的结点结构,/ 图的邻接表存储表示,typedef struct VNode VertexType data; / 顶点信息 ArcNode

17、 *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）在G中增减边：在两个单链表插入、删除结

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

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

20、表示,typedef 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 adjm

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

22、相通的顶点都被访问到；,3）若图中尚有顶点未被访问，则另选一个未被访 问顶点作起始点，重复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

23、,V4,V2,V5,图G,由于没有规定访问邻接点的 顺序，深度优先序列不唯一,为保证每一个顶点只被访问一次，必 须对顶点进行标记。一般用一个辅助数组 visited作为对顶点的标记，当顶点vi未被访问，visitedi值为FALSE；当vi已被访问，则visitedi值为TRUE或被访问时的次序号。,说明：,从深度优先搜索遍历连通图的过程类 似于树的先根遍历;,如果将图的顶点的未被 访问邻接点看作树结点的孩子， 图的深度优先遍历与树的 先根遍历是类似的。,图的深度优先遍历 从图中某顶点v出发： （1）访问顶点v； （2）依次从v的未被访问的邻接点 出发，对图进行深度优先遍历。,树的先根遍历 若

24、树非空 （1）访问根结点； （2）依次先根遍历各 棵子树。,比较,类似,void DFSTraverse(Graph 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

25、(Graph G, int v) / 从顶点v出发，深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, 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）依次访问

26、 vi 的所有未被访问的邻接点； 3）从这些邻接点出发，访问它们的所有未被未被访问的邻接点; 依此类推，直到图中所有的顶点的邻接点都被访问。,由于没有规定 访问邻接点的顺序， 广度优先序列不唯一。你能 写出一个不同的序列吗？,例,求图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

27、。,w1,V,w2,w7,w6,w3,w8,w5,w4,说明：在广度优先遍历图时， “先被访问的顶点的邻接点” 先于“后被访问的顶点的邻 接点”被访问。即以V为起 始点，由近至远，依次访问 和V有路径相通且路径长度 为1，2，的顶点。,在广度优先遍历中,为使“先被访问的顶点,其邻接点亦先被访问” ,需附设队列Q保存被访问过的顶点，并控制遍历顶点的顺序。,V0,V1,V2,V3,V4,V5,V6,V7,V1,V2,V3,V0,V4,V5,V6,V7,算法开始时,将起始点访问后插入Q中,以后,当Q不空时就从Q中删除一个顶点,每删除一个顶点,就依次访问它的每一个未被访问过的邻接点,并令其进队。这样,

28、当Q为空时,表明所有与起始点有路径相通的顶点都已访问完毕。,void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志 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); / 队头元素出

29、队并置为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 到顶点 k 的 一条简单路径。,从顶点 b 出发进行深度优先搜索遍历,例如:,假设找到的第一个邻接点是a, 则得到的结点访问序列为: b a d h c e k f g,假设找到的第一个邻接点是c,则得到的结点访问序列为: b c h d a e k f g,遍历应用的

30、一个例子,无向连通图G的生成树 生成树是一个图G 的一个极小的连通子图，包含图G 的所有顶点，但只有n-1 条边。生成树可由遍历过程中所经过的边组成。深度优先遍历得到的生成树称为深度优先生成树；广度优先遍历得到的生成树称为广度优先生成树。,V0,深度优先生成树,(连通网的)最小生成树,广度优先生成树,在n个城市间建立通讯联络网，要考虑的问题是:如何在保证n点连通的前提下最节省经费,3,6,5,2,1,6,5,5,4,6,例,即要构造连通网N的最小生成树。 这应在 N的所有带权的边中选取 n1 条边 （不构成回路），使权值之和为最小。,？,最小生成树（最小支撑树） 最小生成树是无向连通网的所有生

31、成树中边的权值之和最小的一棵生成树。,最小生成树的构造算法,MST性质：,多数最小生成树的构造算法都利用了下述性质。,设N=（V，E）是一个连通网，U V，U。若（u , v）是一条具最小有权值的边，其中u U，v VU，则必存在一棵包含边（u , v）的最小生成树。,（可用反证法证之）,普里姆(Prim)算法和克鲁斯卡尔(Kruskal )算法是利用MST性质的两种构造最小生成树的算法。,1. 普里姆算法,普里姆算法的基本思想:,贪心算法,任取一图N中顶点v 作为生成树的根，之后不断往“生成树的顶点集”U上添加顶点 w (VU ) 。新添的顶点 w 和已在U的顶点v 之间必定存在一条边(v

32、, 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,v4),(v3,v2),(v2,v5),为实现此算法需设置辅助数组closedge ，对当前VU中每个顶点，记录从U到VU的代价最小的边：,struct VertexType adjvex; / U集中的

33、顶点序号 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,所得生成树权值和= 14+8+3+5+16+21 = 67,构造最小生成树的普里姆算法,void MiniSpantree_PRIM( mgraph G, VertexType u ) 辅助数组

34、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) / 输出生成树的边closedgek.lowcost=0; /第k顶点并入U,for (j=0; jG.vexnum; +j) / 重新选

35、择最小边 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,18,19,c,d,b,a,e,g,f,27,最短路径,一、从某个源点到各顶点的最短路径,V5,V4,100,

36、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到每个顶点vi的权值。按以下方法不断扩充S：每次从V S中取出具有最短特殊路径长度的顶点添

37、加到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集,迪杰斯特拉算法 之二,/开始主循环，每次求得v0到某个

38、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次。但较麻烦。

39、弗洛伊德 (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; ,弗洛伊德算法 之二,