《数据结构与算法》第七章图资料课件.ppt

《《数据结构与算法》第七章图资料课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构与算法》第七章图资料课件.ppt（102页珍藏版）》请在三一办公上搜索。

1、第七章 图,7.1 图的定义7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径,71图的定义,一、有向图和无向图顶点VertexV:顶点的有穷非空集合VR两个顶点之间的关系的集合若VR 则表示从v到w有一条弧Arc v称作弧尾或初始点，Tail w称作弧头或终端点, Head,有向图,无向图,稀疏图稠密图网Network,子图,邻接点相关联顶点的度、入度、 出度,图中边/弧的数目与顶点度的关系,路径,路径的长度,连通图,回路或环Cycle简单路径简单回路,强连通图,完全图,有向完全图,由顶点的集合和弧的集合构成的图称为有向图,G1=(V1,A1

2、)V1=v1,v2,v3,v4A1=,若VR必有VR则用无序对(v,w)代替和称作边Edge由顶点的集合和边的集合构成的图称作无向图,G2=(V2,E2)V2=v1,v2,v3,v4,v5E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),二、完全图 Completed Graph完全图 有n*（n-1）/2条边的无向图有向完全图 有n*（n-1）条弧的有向图稀疏图 有很少条边或弧的图稠密图网Network 带权的图,三、子图Subgraph若有两个图G =（V，E）,G1=（V1，E1）如果V1 V , E1 E,则称G1为G的子图,子图,四

3、、度1.无向图G =（V，E）若边（v，v1）E，则称顶点v和v1互为邻接点 边（v，v1）依附于顶点v和v1 或边（v，v1）与顶点v、v1相关联顶点v的度是和v相关联的边的数目,记作TD（v）2.有向图G =（V，A）弧v，v1A， 则称v邻接到v1 或v1邻接自v 弧v，v1和顶点v、v1相关联以顶点v为头的弧的条数称作v的入度,记作ID（v） 以顶点v为尾的弧的条数称作v的出度,记作OD（v） 顶点v的度TD（v）=ID（v）+OD（v）,图中边/弧的数目与顶点度的关系,(若图中有n个顶点，e条边/弧),五、路径1.无向图G=（V，E）中 从顶点v到v1的路径是一个顶点序列: v=Vi

4、,0, Vi,1,Vi,m =v1 其中（Vi,j-1，Vi,j）E， 1jm,3.路径的长度是路径上边或弧的数目,2.有向图G=（V，A） 从顶点v到v1的路径是一个有向顶点序列: v=Vi,0, Vi,1,Vi,m=v1 其中Vi,j-1，Vi,jA， 1jm,4.第一个顶点与最后一个顶点相同的路径称为回路或环Cycle5.序列中顶点不重复出现的路径称为简单路径 除第一个和最后一个顶点外，其余顶点不重复出现的回路称为简单回路,六、连通图 Connected Graph1.无向图 v到v1有路径，称v和v1是连通的 若图中任意两个顶点vi、vjV都是连通的 则称G是连通图,2.若一个无向图中

5、有n个顶点和少于n-1条边 则该图是非连通图 若它有多于n-1条边，则一定有环,3.有向图 对于每一对vi、vjV,从vi到vj和vj到vi 都存在路径,则称 G为强连通图,七、图的ADTADT Graph数据对象V:V是具有相同特性的数据元素的集合，称为顶点。 数据关系R： R=VR VR=|v,wV且p(v,w), 表示从v到w的弧， 谓词P(v,w)定义了弧的意义或信息 基本操作P： CreateGraph( 初始条件:图G存在. 操作结果:销毁图G。,LocateVex(G,u); 初始条件：图G存在，u和G中顶点有相同特征。 操作结果: 若G中存在顶点u，则返回该点在图中的位置,否则

6、返回其它信息。,GetVex(G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果: 返回v的值,PutVex( 初始条件：图G存在，v是G中某个顶点。 操作结果: 对v赋值 value。,FirstAdjVex(G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果:返回v的第一个邻接顶点。 若顶点在G中没有邻接顶点，则返回“空”。,NextAdjVex(G,v,w); 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果: 返回v的（相对于w的）下一个邻接顶点。 若w是v 的最后一个邻接点则返回“空”。,InsertVex( 初始条件：图G存在，v和图中顶点有相

7、同特征。 操作结果: 在图G中增添新顶点v。,DeleteVex( 初始条件：图G存在，v是G中某个顶点 操作结果：删除G中顶点v及其相关的弧。,InsertArc( 初始条件：图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是顶点

8、的应用函数。 操作结果: 从顶点v起广度优先遍历图G， 并对每个顶点调用visit 一次且仅一次。 一旦visit()失败，则操作失败。ADT Graph,7.2 图的存储结构,在图中，无法用数据元素在存储区的物理位置表示元素之间的关系。,一、数组表示法(邻接矩阵表示法) 用一个数组存储顶点的信息， 用另一个数组存储边或弧的信息-邻接矩阵,15,10,5,30,12,20,3,2,1,0,4,1.图的数组存储表示/ _ _ _ _ _ _图的数组（邻接矩阵）存储表示 _ _ _ _ _ _ _#define INFINITY INT_MAX / 最大值#define MAX_VERTEX_NU

9、M 20 /最大顶点个数typedef enum DG,DN,UDG,UDNGraphKind; /有向图，有向网，无向图，无向网typedef struct ArcCellVRType adj; /VRType是顶点关系类型.对无权图,用1或0 /表示相邻否；对带权图，则为权值类型。 InfoType *Info; /该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,typedef structVertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexn

10、um, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志MGraph;,Mgraph G1; G1.vexnum=4G1. arcnum=4 G1.kind=DG,G1.arcs01.adj=1,G1.arcs,2图的构造方法Status CreateGraph( MGraph / CreateGraph,Status CreateUDN(MGraph /adj,info,for (k=0; k的权值 if (IncInfo) Input(* G.arcsij.info); / 若弧含有相关信息,则输入 G.arcsji =G.arcsij; / 置的

11、对称弧 return OK; / CreateUDN,二、邻接表Adjacency List方法：对每个顶点建立一个单向链表 链接与vi有边相连的顶点（无向图） 或从vi出发到达的顶点（有向图）,指向该点出发到达的第一条弧,每个顶点对应一个头结点,每条边/弧对应一个结点,无向图,边结点,有向图,/- - - - - - - 图的邻接表存储表示 - - - - - - - #define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode * nextarc; / 指向下一条弧的指针 I

12、nfoType * info; / 该弧相关信息的指针ArcNode ;,typedef struct VNode VertexType data; / 顶点信息 ArcNode * firstarc; / 指向第一条依附顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM ;,typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph;,# define MAX_VERTEX_NUM 20typedef struct ArcBox int tailv

13、ex, headvex ; / 该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; /分别为弧头相同和弧尾相同的弧的链域 Info type *info; / 该弧相关信息的指针ArcBox;,typedef struct VexNode VertexType data; ArcBox * firstin, * firstout; /分别指向该顶点第一条入弧和出弧 VexNode ;typedef struct VexNode xlist MAX_VERTEX_NUM ; / 表头向量 int vexnum, arcnum; / 有向图的当前顶点数和弧数 OLG

14、raph ;,Status CreateDG(OLGraph / 初始化指针 ,for(k=0; kinfo); /若弧含有相关信息，则输入 / CreateDG,四、邻接多重表 Adjancency Multilist 顶点和边分别用一个结点表示 边：,该边是否搜索过,顶点i在图中的位置(编号),下一条与i有关的边,有关边的信息,# define MAX_VERTEX_NUM 20typedef enum unvisited, visitedVisitIf ;typedef struct EBox VisitIf mark; / 访问标记 int ivex, jvex; / 该边依附的两个顶

15、点的位置0 struct EBox * ilink, * jlink; /分别指向依附这两个顶点的下一条边 InfoType * info; / 该边信息指针 EBox;typedef struct VexBox VertexType data; EBox * firstedge ; / 指向第一条依附该顶点的边 VexBox;,typedef struct VexBox adjmulist MAX_VERTEX_NUM ; int vexnum, edgenum; / 无向图的当前顶点数和边数AMLGraph ;,73图的遍历Traversing Graph,图的遍历： 从图中某个顶点出发访

16、问遍图中每个顶点， 且图中每个顶点仅被访问一次。遍历过程中每个顶点可能被访问多次， 因此，每个顶点被访问后需作一个标记 一般用一个数组标记某个结点是否被访问遍历方法：深度优先搜索、广度优先搜索,一、深度优先收索Depth-First-Search(DFS)方法： 从图中某个顶点出发（设为v1），访问v1， 从v1出发,选择一个未被访问的邻接点vk,访问vk， 从vk出发，选择一个未被访问的邻接点, 若vk的所有邻接顶点都被访问过了， 回到vk-1,再选择的一个未被访问的邻接点, 若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程 直到所有顶点均被访问过为止。,从v1出发,选择一个未

17、被访问的邻接点vk,访问vk， 从vk出发，选择一个未被访问的邻接点, 若vk的所有邻接顶点都被访问过了， 回到vk-1,再选择的一个未被访问的邻接点, 若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程 直到所有顶点均被访问过为止。,Boolean visitedMAX; / 访问标志数组Status (* VisitFunc)(int v); / 函数指针变量void DFSTraverse(Graph G, Status(* Visit)(int v) / 对图G作深度优先遍历VisitFunc = Visit; /使用全局变量VisitFunc，使DFS不必设函数指针参数

18、for(v=0; vG.vexnum; +v) visitedv = FALSE ; / 访问标志数组初始化 for(v=0; vG.vexnum; +v ) if(!visitedv) DFS (G,v ); /对尚未访问的顶点调用DFS,/从第v个顶点出发递归地深度优先遍历图G void DFS(Graph G, int v)visitedv=TRUE; VistFunc(v); /访问第v个顶点 for(w=FirstAdjVex(G,v);w0; w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); /对v的尚未访问的邻接顶点w递归调用DFS prin

19、tf(v); /起什么作用,1,2,3,4,5,6,7,8,9,搜索,回退,二、广度优先收索Breadth-First-Search(BFS)方法： 从图中某个顶点出发（设为vi），访问vi， 从vi出发，依次访问vi的所有未被访问的邻接点， 再从这些邻接点出发， 依次访问它们的所有未被访问的邻接点, 若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程 直到所有顶点均被访问过为止。,void BFSTraverse(Graph G,Status(* Visit)(int v) / 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。 for(v=0; v0;w=N

20、extAdjVex(G,u,w) if(!visitedw) visitedw = TRUE; Visit(w); EnQueue(Q,w); / u的尚未访问的邻接顶点w入队列Q /while / if / BFSTraverse,搜索,1,2,3,4,5,6,7,8,9,74图的连通性问题,一、无向图的连通分量和生成树1.连通分量 无向图的极大连通子图。即:子图中不能再增加一个顶点,已有顶点的边均包含在内。 无向图的连通分量的产生-多次调用DFS2.生成树 一个连通图的生成树是一个极小连通子图,且含有图中全部顶点,无向图,连通分量,连通图,生成树,3.无向图的生成树 对一个连通图G，从图中

21、任意一个顶点出发遍历图时，把E分为E1和E2，E1为遍历过程中经过的边的集合，E2为剩余边的集合，则E1与V构成G的极小连通图，即连通图的一棵生成树 若遍历为DFS，则称为深度优先生成树 若遍历为BFS，则称为广度优先生成树,对于非连通图，每个连通分量中的顶点集合,加上遍历时经过的边，构成了非连通图的生成森林。,生成森林,4.无向非连通图的深度优先生成森林void DFSForest(Graph G,CSTree /建立以p为根的生成树 /DFSForest,void DFSTree(Graph G, int v, CSTree /从第w个顶点出发深度优先遍历图G,建立子生成树q / if/

22、DFSTree,二、最小生成树Mininum Cost Spanning Tree问题： 设有n个城市，两个城市之间都可以有一条路线，如何从最多n(n-1)/2条边中选择代价和最小的n-1条边(要包含所有顶点),就是连通图的最小代价生成树问题，简称最小生成树。,1.普里姆算法Prim 设N=（V，E）为连通网 用TE表示N上最小生成树边的集合 (1)从V中选一顶点u0加入U，TE= (2)对所有uU，vV-U，（u，v）E,找一条代价最小的边（u0，v0）加入TE,并把v0加入U (3)重复(2)，直到U=V为止,则（V，TE）为N的最小生成树,U,V-U,v4,v6,v1,v2,v3,v5,

23、1,5,5,5,6,6,6,3,4,2,2MST性质(Prime算法正确性证明）设N=(V,E)是一个连通图, U是V的一个非空子集若(u,v)是一个具有最小代价的边,uU，vV-U则必存在一棵包含边(u ,v)的最小生成树,u,v,u,v,U,V-U,证明： 假设网N的任何一棵最小生成树都不包含(u ,v) 设T是N上的一棵最小生成树，把(u ,v)加入到T中 则T中必存在一条包含(u ,v)的回路 同时,T中必存在另一条边(u,v)， 其中uU vV-U 并且u和u ,v和v之间均存在路径相通 删去边(u,v)，则可削去回路， 得到另一棵生成树T 显然,T的代价不高于T,且包含边(u ,v

24、),矛盾。,设N=（V，E）为连通网用TE表示N上最小生成树边的集合(1)从V中选一顶点u0加入U，TE=(2)对所有uU，vV-U，（u，v）E,找一条代价最小的边（u0，v0）加入TE,并把v0加入U (3)重复(2),直到U=V为止,则（V,TE）为N的最小生成树,图-邻接矩阵最小的边（u0，v0）（ u0U，v0V-U）用矩阵closedge表示,struct VertexType adjvex; /最短的边对应u中的顶点 VRType lowcost;/记录u中顶点到顶点j的最短的边 closedgeMAX_VERTEX_NUM;,void MiniSpanTree_PRIM(MGr

25、aph G,VertexType u)k = LocateVex(G, u ); for(j=0;jG.vexnum; +j ) / 辅助数组初始化 if(j!=k) closedgej=u,G.arcskj.adj; /adjvex,lowcost closedgek.lowcost = 0; / 初始，U = u,for(i=1; iG.vexnum;+i) / 选择其余G.vexnum-1个顶点 k =minimum(closedge); /求出T的下一个结点:第k顶点 printf(closedgek.adjvex,G.vexsk); /输出生成树的边 closedgek.lowcos

26、t = 0; /第k顶点并入U集 for (j=0; jG.vexnum; +j) if(G.arcskj.adjclosedgej.lowcost) closedgej=G.vexsk,G.arcskj.adj; / MiniSpanTree,3.克鲁斯卡尔算法 设连通图N=（V，E） (1)构造非连通图T=(V,),图中每个顶点自成一个连通分量 (2)在E中选择代价最小的边（u，v），并删去该边。若(u,v)落在T中不同的连通分量上,则将此边加入T中 (3)重复(2），直到T中只有一个连通分量为止,2,4,5,3,6.5有向无环图及其应用,一、DAG图 -Directed Acycline

27、 Graph 一个无环的有向图称为有向无环图,二、拓扑排序 Topological Sort1AOV网 Activity On Vertex Network 用顶点表示活动， 用弧表示活动之间的优先关系的有向图 称为顶点表示活动的网，简称AOV网。 在网中,若顶点i到顶点j有一条路径,则i为前驱, j为后继。若A，则vi为vj的直接前驱，vj为vi直接后继,在AOV网中不能出现环，判定网中是否出现环的办法是拓扑排序。若所有的顶点都在拓扑有序序列中，则AOV网中无环，否则有环。,C语言程序设计,数据结构与算法,面向对象程序设计,计算机网络原理,信息科学导论,电路原理,大学物理,数字逻辑电路实验,

28、组成原理实验,操作系统,汇编语言程序设计,高等数学1,离散数学,数据库原理,线性代数,基础物理实验B,高等数学2,高等数学3,C程序设计实验,数据结构实验,电路原理实验,概率与数理统计,数字逻辑电路,计算机组成原理,网络原理实验,操作系统实验,面向对象实验,2拓扑次序 设AOV网中有n个顶点V1，V2，Vn， 将顶点排成这样一个线性次序：Vi1，Vi2，Vin， 其中i1，i2，in是1到n的一个排列 且若V ij，V ikA，则jk,对AOV网给出拓扑次序的过程称为拓扑排序,3拓扑排序算法(1)在网中选一个没有前驱的顶点且输出它(2)从图中删去该顶点及所有以它为尾的弧(3)重复(1)(2)直

29、到所有顶点被输出 或图中不存在无前驱的顶点为止,。采用邻接表作存储结构。用一个数组indegree存放顶点的入度。用一个栈存放入度为0的顶点,Status TopologicalSort( ALGraph G) /有向图G采用邻接表存储结构。 /若G无回路,则输出G的顶点的一个拓扑序列并返回OK, /否则ERROR FindInDegree(G,indegree); /对各顶点求入度indegree InitStack(S); / 建零入度顶点栈S for(i=0; iG.vexnum; +i ) if(!indegreei) Push(S, i); / 入度为0者进栈 count = 0;

30、/ 对输出顶点计数,while(!StackEmpty(S) Pop(S,i); printf(i,G.verticesi.data); +count; / 输出i号顶点并计数 for(p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex; /对i 号顶点的每个邻接的入度减1 if(!(- -indegreek)Push(S, k); /若入度减为0，则入栈 / for DestroyStack(S); if(countG.vexnum) return ERROR; /该有向图有回路 else return OK;/ TopologicalS

31、ort,。还可以利用深度优先遍历过程进行拓扑排序，按退出DFS的逆序为拓扑次序,1,2,3,4,5,6,拓扑次序为：v6、v1、v4、v3、v5、v2,4.关键路径 AOE网Activity On Edge 顶点-事件 边-活动 权-活动持续的时间 用AOE网估计工程的完工时间,Vi表示在此之前的活动已完成，在此之后的活动可以开始,1,2,3,4,5,买面粉3,买鸡蛋3,买白菜4,买熟食6,6,7,剁馅5,切2,和面2,煮鸡蛋1,包饺子4,最短要多久才能包好饺子,开始聚餐?,在一般情况下,AOE网中只有一个入度为0的顶点,称为源点只有一个出度为0的顶点，称为汇（聚）点？完成整个工程至少需要多少

32、时间 -从源点到汇点的最长路径？哪些活动是影响工程进度的关键,路径长度最长的路径叫做关键路径 Critical Path从源点到Vi的最长路径叫做事件的最早发生时间,也就是所有以Vi为尾的弧所表示活动的最早开始时间,令e(i)表示ai的最早开始时间 l(i)表示ai的最迟开始时间 l(i)-e(i)为时间余量关键路径上的所有活动有：l(i)=e(i) 把所有e(i)=l(i)的活动叫做关键活动。,设ai由弧表示 ve(j)表示事件j的最早发生时间 vl(j)表示事件j的最迟发生时间 ai的持续时间为dut() 则：e(i)=ve(j) l(i)=vl(k)-dut(),最早开始时间:前驱活动都

33、按期完成情况下的开始时间最迟开始时间:保证所有活动都能按期完成情况下最晚开始时间关键路径上的所有活动最早=最迟,计算的方法：（1）ve(0)=0（2）按拓扑顺序计算：,其中T是所有以第j个顶点为头的弧的集合,（3）vl(n-1)=ve(n-1)（4）按逆拓扑顺序计算：,其中S是所有以第i个顶点为尾的弧的集合,（5）根据各顶点的ve和vl的值 计算每条弧s的e(s)和l(s),ve(3)=5,ve(4)=7,ve(7)=14,ve(8)=18,vl(8)=18,vl(7)=14vl(6)=16,vl(4)=7,ve(0)=0,vl(1)=6vl(2)=6,vl(0)=0,ve(5)=7,ve(6

34、)=16,vl(5)=10,vl(3)=8,ve(2)=4ve(1)=6,Status TopologicalOrder(ALGraph G, Stack / 初始化,while (! StackEmpty(S) Pop(S, j); Push(T,j); +count; /j号顶点入T栈并计数 for(p=G.verticesj.firstarc;p;p=p-nextarc) k = p-adjvex; / 对j号顶点的每个邻接点的入度减1 if(-indegreek=0)Push(S, k); /若入度减为0，则入栈 if(vej+*(p-info)vek)vek=vej+*(p-info

35、); / *(p-info)= dut() / while DestroyStack(S); if(countG.vexnum) return ERROR; /该有向网有回路 else return OK;/ TopologicalOrder,Status CriticalPath(ALGraph G) /G为有向网，输出G的各项关键活动 if(!TopologicalOrder(G,T) return ERROR; vl0.G.vexnum-1=veG.vexnum-1; /初始化顶点事件的最迟发生时间 while (! StackEmpty(T) /按拓扑逆序求各顶点的v1值 for(Po

36、p(T,j),p=G.verticesj.firstarc; p; p=p-nextarc) k=p-adjvex; dut = * (p-info); / dut if(vlk-dutv1j) vlj = vlk-dut; / for,for(j=0;jnextarc) k = p-adjvex; dut = * (p-info) ; ee=vej; el=vlk-dut; tag=(ee=e1)? * : ; printf ( j,k, dut, ee, el, tag); / 输出关键活动 / CriticalPath,76最短路径 用顶点表示城市， 用边表示城市之间的交通状况 用边上的

37、权表示城市之间的耗费（距离、时间、各种费用等）一、从一点到另一点，经过的结点最少二、从某个源点到其余各个顶点的最短路径 给定带权的有向图G和源点v， 求从v到G中其余各点的最短路径方法：按路径长度递增序产生最短路径 -迪杰斯特拉Dijksta方法,v0,v5,60,v1,v2,v3,v4,100,30,10,10,50,5,20,v0,v5,v1,v2,v3,v4,存储结构用带权的邻接矩阵arcs表示带权有向图arcsij= A 上的权值 A,算法(1)设S为已找到从v出发的最短路径的终点集合, 初值S= Di表示从v到Vi的最短路径的长度 若A,Di为从v到Vi上的权,否则为 即：Di=ar

38、csLocateVex(G,v),i, ViV,(2)选择Vj，使得 Dj=minDi| ViV-S 并修改S: S=Sj Vj就是一条从v出发的最短路径的顶点,(3)修改从v出发到集合V-S上任一点Vk可到达的最短路径 即如果 Dj+arcsjk, 或者是从v到Vk加上弧,其中 VkS）,(4)重复(2)(3)共n-1次,求得从v到图中其余各顶点的最短路径,终点,从V0到各终点D值和最短路径的求解过程,V1,V2,V3,V4,Vj,V5,S,for(v=0; vG.vexnum; +v) finalv = FALSE; Dv = G.arcsv0v; for(w=0; wG.vexnum;

39、+w) Pvw = FALSE; / 设空路径 if (DvINFINITY) pvv0=TRUE; pvv = TRUE; / forDv0 = 0; finalv0 = TRUE; / 初始化，v0顶点属于S集,void ShortesPath_DIJ(MGraph G, int v0, PathMatrix &P, ShortPathTable &D ),若w是从v0到v最短路径上的顶点,则pvw为TRUE已经求得从v0到v的最短路径,finalv为TRUE,/ 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集for (i=1; iG.vexnum; +i) / 其余G.ve

40、xnum-1个顶点 min = INFINITY; /当前所知离v0顶点的最近距离 for(w=0;wG.vexnum; +w) if (! finalw) / w顶点在V -S中if(Dwmin) v = w; min = Dw; / w顶点离v0顶点更近 finalv = TRUE; / 离v0顶点最近的v加入s集 for(w=0; wG.vexnum; +w) /更新当前最短路径及距离 if(! finalw / Pw = Pv + w / if / for/ ShortestPath_DIJ,三、每一对顶点之间的最短路径方法一:每次以一个顶点为源点,重复执行迪杰斯特拉方法方法二：Flo

41、yd 算法,求顶点对的最短路径：(1)的路径长度与比较，小者为从Vi到Vj的中间顶点序号不大于0的最短路径,(2) 加入顶点V1, 设和为 中间顶点序号不大于0的最短路径， 比较和， 小者为从Vi到Vj的中间顶点序号不大于1的最短路径,定义n阶方阵序列：,表示从Vi到Vj的中间顶点序号不大于k的最短路径的长,(3)依次加入V2,V3,Vn-1, 共经过n次比较后，求得Vi到Vj的最短路径,void ShortestPath_FLOYD(Mgraph G, PathMatrix / for,for (u=0;uG.vexnum; +u) for (v=0; vG.vexnum; +v) for (w=0; wG.vexnum; +w) if (Dvu+DuwDvw) /从v经u到w的一条路径更短 Dvw = Dvu + Duw; for (i=0; iG.vexnum; +i) Pvwi = Pvui | Puwi; / if / ShortestPath_FLOYD,A,B,C,6,4,11,3,2,7,6,5,