数据结构课件第七章图无答案

1、警 示2011年9月 2013年11月 2014年6月就要毕业了。回头看自己所谓的大学生活，我想哭，不是因为离别，而是因为什么都没学到。我不知，简历该怎么写，若是以往我会让它空白。最大的收获也许是对什么都没有的忍耐和适应第 七 章 图第七章 图图的定义和术语图的存储结构图的基本操作-遍历应用最小生成树 拓扑排序 关键路径 最短路7.1图的定义和术语线性表、树和图：从关系、结构两个角度区分 AB E C D B CA D F E图Graph;顶点Vertex;序偶;弧Arc;弧头B/弧尾ADigraph;Undigraph;无序对(A,B):;Edge网NetWork:弧或边含权的图,分有向网D

2、N、无向网UDN(无向)完全图:边数最大的无向简单图,满足e=n*(n-1)/2有向完全图:弧数最大的有向简单图, e=n*(n-1)稀疏图(如enlogn) 稠密图ABECF1597211132BECBBC子图Subgraph 邻接点:无向图如A与B互为邻接点,有向图如A邻接到B无向图顶点的度,如TD(A)=2；有向图分入/出度,度为两者之和 ID(A)=1,OD(A)=2,TD(A)=3路径、简单路径、回路(环)、路径长度术语 B CA D F EABECF若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图。如能找到一条含全部顶点的路径则说明是连通图无向图中的极大连通子图称作此图的

3、连通分量。极大指顶点尽量多,顶点连同其关联的边构成连通分量.图本身连通则连通分量唯一,是自身BACDFEBACDFE连通图,连通分量 (无向图)若任意两顶点间都存在一条有向路径，则称此有向图为强连通图。ABECFABECF有向图的极大强连通子图称作它的强连通分量。强连通图、强连通分量(有向图)连通图的一个含有全部顶点的子图,如果连通且极小，则它必是一颗树(边数为n-1)，称该树为原连通图的生成树。破圈法可得生成树 对非连通图，由各个连通分量的生成树组成的集合称为此非连通图的生成森林。BACDFE生成树与生成森林（无向图）注:树是含边数最小的连通图(n-1);图中若边少于n-1则必不连通；若图连

4、通则至少含n-1条边；若图中多于n-1条边则必然含有回路。含n-1条边的连通图必然是树ADT Graph 数据对象V：若干顶点组成的集合 数据关系R：R=VR VR| v,wV 且 表示从 v 到 w 有一条弧，可代表v认识w 或 v到w有路等) 基本操作图的抽象数据类型定义逻辑结构CreatGraph(&G, V, VR); / 按定义(V, VR) 构造图GDestroyGraph(&G); / 销毁图G结构的建立和销毁插入或删除顶点、弧InsertVex(&G, v); /在图G中增添新顶点v。DeleteVex(&G, v);/ 删除G中顶点v及其相关的弧。InsertArc(&G,

5、v, w); /在G中增添弧，若G是无向的，则还增添对称弧DeleteArc(&G, v, w); /在G中删除弧，若G是无向的，则还删除对称弧遍 历DFSTraverse(G, v, Visit(); /从顶点v起深度优先遍历图G,对每个顶点执行一次VisitBFSTraverse(G, v, Visit(); /从v起广度优先遍历图G，每个顶点调用一次函数Visit规则:访问起始顶点v,然后选取与v邻接的未访问的第一个顶点w,访问之，再选取与w邻接的未访问的第一个顶点，访问之。重复进行至当前节点的所有邻接点都被访问过，此时后退到最近访问过的顶点，找其下一个未访问的邻接点访问,依次类推.如A

6、BE FCD H说明:一次可遍历所有与v连通的顶点。若尚有顶点未访问(非连通图),则从其开始重复上述过程.对应树的先根遍历。可得深度优先生成树或森林以及连通分量递归描述：访问v, 逐个从v未访问的邻接点出发递归遍历.规则:访问v,访问v的全部未访问的邻接点,再逐个从这些邻接点出发重复.一次可遍历所有与v连通的顶点,若尚有顶点未访问则从其开始重复开始上述过程.如ABEHFCD对应树层序遍历,可得广度优先生成树/森林,可得连通分量,实现? B CA D F EH对顶点的访问操作LocateVex(G, u); / 若G中存在顶点与u”相等”，则返回该顶点在图中“位置”(下标或指针)GetVex(G

7、, v); / 返回G中顶点v的值。PutVex(&G, v, value);/为G中顶点v赋值value。对邻接点的操作FirstAdjVex(G, v); /返回G中顶点v的“第一个邻接点”。若该顶点/在 G 中没有邻接点，则返回“空”。NextAdjVex(G, v, w); / w是v的一个邻接点,返回v的“下一个邻接点”。/若w是v的最后一个邻接点，则返回“-1”。图的数组表示(p161)(邻接矩阵)图的邻接表表示(p163)有向图的十字链表表示(p164) 无向图的邻接多重表表示(p166)7.2 图的存储结构BACDFE邻接矩阵:行、列各对应一个顶点,若第i行对应的顶点到第j列对

8、应的顶点有弧相连则Aij=1,否则为0。n*n阶 A B C D E F ABCDEF1、图的数组表示-邻接矩阵adjacency matrix邻接矩阵举例ABECD无向图的邻接矩阵必为对称阵网的邻接矩阵Aij=wij或/-图的数组(邻接矩阵)存储表示-typedef char VertexType;#define INFINITY 10000 /最大值 #define MAX_VERTEX_NUM 20 /最大顶点个数typedef enumDG, DN, UDG, UDN GraphKind;/图类型 typedef struct ArcCell / 弧的定义 VRType adj; /邻

9、接数,0/1或w/。VRType为int/double InfoType *info; /弧的附加信息,InfoType可为charArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct / 图的定义 VertexType vexsMAX_VERTEX_NUM; /顶点信息 AdjMatrix arcs; / 邻接矩阵,存储弧信息,静态数组 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的类型标记 MGraph; /矩阵图 A B C D E FABCDEFStatus Crea

10、teGraph(Mgraph &G) /输入图的种类及顶点和边信息构造图G(邻接矩阵表示) scanf(“%d”,&G.kind);/枚举值DG,DN实输入0 1 switch (G.kind) case DG : return CreateDG(G); case DN : return CreateDN(G); case UDG : return CreateUDG(G); case UDN : return CreateUDN(G); default : return ERROR;图的创建Status CreateUDN(Mgraph &G) /建立无向网G 输入G.vexnum,G.ar

11、cnum, IncInfo;/IncInfo为0表各弧无附加信息 for (i=0 ; i G.vexnum; +i) scanf(“%c”,G.vexsi); for (i=0 ; i G.vexnum; +i) for(j=0 ; jvexnum; +j) G.arcsij=INFNITY,NULL; /各弧初始化 for (k=0;k G.arcnum;+k) scanf(“%c %c %lf”,&v1,&v2,&w); /输入一“边”及其权值 i=LocateVex(G,v1);j= LocateVex(G,v2) ;/确定顶点下标 G.arcsij.adj = w; if (IncI

12、nfo) 输入G.; G.arcsji= G.arcsij; /无向网需将对称弧加入 /ENDABECF1597211132ABCDEFBACDFE ABCDEF邻接矩阵优缺点：易于求顶点度(区分有/无向图)、求邻接点，易判断两点间是否有弧或边相连,但不利于稀疏图的存储，因弧不存在时也要存储相应信息，且要预先分配足够大空间1 4230 120 1 2 3 4 A B C D EABECDtypedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode;datafirsta

13、rcadjvexnextarcinfotypedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; GraphKind kind; ALGraph; /邻接表图2、邻接表存储表示Status CreateGraph(ALGraph &G) /建立图的邻接表的结构 scanf(“%d”, &G.kind); switch (G.kind) case DG : return Creat

14、eDG(G); case DN : return CreateDN(G); case UDG : return CreateUDG(G); case UDN : return CreateUDN(G); default : return ERROR;邻接表图的创建【补充】Status CreateDN(ALGraph &G) /建立有向网 scanf(“%d%d%d”,&G.vexnum,&G.arcnum,&IncInfo); for (i=0 ; i G.vexnum; +i) scanf(G.verticesi.data); G.verticesi.firstarc=NULL; for

15、(k=0;kadjvex=j; if (IncInf) 输入(arcn-info); arc-nextarc = G.verticesi.firstarc; /插入到开始位置 G.verticesi.firstarc=arcn;/邻接点与输入逆序排列P164,正序? /邻接点顺序依赖输入顺序和创建程序，“不给”默认正序 Return OK； /思考无向网的创建有何不同？4 1A0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 1 F 1 2 3 BACDFE顶点数组(头结点)邻接点链表无向图中每条边出现两次,n个顶点e条边需n个头结点和2e个表结点无向图的邻接表存储表示小

16、结：掌握图的概念和基本术语掌握图的邻接矩阵存储和邻接表存储结构，理解优缺点掌握图的深度优先遍历和广度优先遍历的规则会通过遍历求图的连通分量和深度优先、广度优先生成树、生成森林作业：1 5 B CA D F EH A B C D E FABCDEF/-图的数组(邻接矩阵)存储表示-typedef char VertexType;#define INFINITY 10000 /最大值 #define MAX_VERTEX_NUM 20 /最大顶点个数typedef enumDG, DN, UDG, UDN GraphKind;/图类型 typedef struct ArcCell / 弧的定义 V

17、RType adj; /邻接数,0/1或w/。VRType为int/double InfoType *info; /弧的附加信息,Info可为charArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct / 图的定义 VertexType vexsMAX_VERTEX_NUM; /顶点信息 AdjMatrix arcs; / 邻接矩阵,存储弧信息,静态数组 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的类型标记 MGraph; /矩阵图1 4230 120 1 2 3 4 A

18、 B C D E邻接表举例ABECDtypedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode;datafirstarcadjvexnextarcinfotypedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; GraphKind kind; ALGraph; /邻接表图

19、1 4230 120 1 2 3 4 A B C D E邻接表说明：ABECD稀疏图用邻接表存储相对节省空间对有向图易求顶点出度与邻接点,但求入度难.若只求入度可引入逆邻接表,也可结合邻接表与逆邻接表引入十字链表对无向图易求度,但边出现两次,为方便边操作可借助多重链表A B C D E 303420012343、“有向图”的十字链表存储表示【选】 ABDCE010A1B2C3D4E.tailvheadvhlinktlinkinfodatafirstinfirstout03VexNode:ArcBox:1224324041具体邻接点顺序依赖输入顺序和图的创建程序，如逆序3、“有向图”的十字链表存

20、储表示【选】 typedef struct ArcBox int tailvex, headvex; InfoType *info; struct ArcBox *hlink,*tlink;/指向同弧头/尾的下一弧 ArcBox;typedef struct VexNode / 顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; int vexnum, arcnum; OLGraph;Status CreateDG(OLGraph G)

21、scanf(&G.vexnum, &G.arcnum, &IncInf); for(i=0;i G.vexnum; +i) scanf(&G.xlisti.data); G.xlisti.firstin=NULL;G.xlisti.firstout=NULL; for(k=0;kinfo); /END 4、“无向图”的邻接多重表存储表示【选】无向图的邻接表存储中，一条边出现两次，分别在两个顶点对应的链表中，对边的操作复杂。为此，将每条边(Vi,Vj)只用一个如下结点表示:顶点表示为：markivexilinkjvexjlinkinfodatafirstedge0 1 2 3 A B C DAB

22、DC01031223e1e2e3 e4 将边看作有向的，如A-Btypedef struct Ebox VisitIf mark; / 访问标记 int ivex, jvex; /该边依附的两个顶点的位置 struct EBox *ilink,*jlink;/指向对应顶点为i,j的下一边 InfoType *info; EBox;4、“无向图”的邻接多重表存储表示【选】typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph; / 邻接多重表typedef struct VexBox VertexT

23、ype data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;7.3图的遍历深度优先遍历规则:访问v,逐个从v的邻接点出发，若其未访问则从其开始递归遍历，如此可遍历所有与v连通的顶点.若尚有顶点未访问(不连通),则从其开始重复上述过程.如ABEFCDH.void DFS(G，v) VisitFunc(v); visitedv=TRUE; for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w) if（!visitedw）DFS(G，w)；/执行DFS(G,A)时会遍历完所有与连通的顶点void DFSTraverse(Gr

24、aph G, Status (*Visit)(int v) VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v);/visited为全局数组，VisitFunc函数为全局函数指针每个顶点调用一次DFS,DFS主要操作是查找邻接点,当用邻接矩阵存储时查找某顶点的邻接点复杂度为O(n),总复杂度O(n2);当邻接表存储时查找邻接点总复杂度为O(e),总复杂度为O(n+e)DFSTraverse每调用一次DFS所访问的顶点连通这些顶

25、点关联的边构成一个连通分量.只保留走过的边得生成树或生成森林 B CA D F EHabchdekfgachkfedbgabcdefghk2345607070807812385547注意邻接点的顺序作题时若未给出则默认为正序,实际上应依赖创建程序和输入顺序。若给出存储结构则以存储结构为准。如上例既非正序也非逆序,如h、k对应的链表，画生成树时注意求图的连通分量、深度优先生成树或生成森林P171DFSTraverse每调用一次DFS所访问的顶点连同这些顶点关联的边构成一个连通分量.只保留走过的边得生成树或生成森林7.3 图的遍历广度优先遍历BFSTraverse(G, v, Visit(); 规

26、则:访问v, 访问v的各未访问的邻接点,之后逐个从这些邻接点出发重复上述操作。待与v连通的顶点访问毕再从另一顶点出发. 如ABEHFCD实现：对各个顶点v： 若其尚未访问则访问v,之后v入队。 【队顶元素出队，逐个访问其尚未访问的邻接点，每访问完一个便入队】。重复【】中内容到队空 B CA D F EHvoid BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v)visitedv = FALSE; InitQueue(Q); for ( v=0; v=0;w=NextAdjVex(G,v,w) if ( ! v

27、isitedw ) /注意NextAdjVex返回值约定 Visit(w); visitedw=TRUE; EnQueue(Q, w); 对各个顶点v： 若其尚未访问则访问v,之后v入队。【队顶元素出队，逐个访问其尚未访问的邻接点，每访问完一个便入队】。重复【】中内容到队空每个顶点进一次队,出队时主要操作是查找邻接点,当用邻接矩阵存储时查找某顶点的各邻接点复杂度的为O(n),总复杂度O(n2); 当用邻接表存储时查找邻接点复杂度为O(e),总复杂度为O(n+e)7.4.3 最小生成树P173假设要在 n 个城市之间建立通讯联络网，不同城市间建立通讯设施的代价不同，如何在最节省经费的前提下建立这

28、个通讯网？即找权值之和最小的极小连通子网，问题转换为在连通网中找一颗生成树，最小生成树abcdegf195141827168213ae12dcbgf7148531621Kruaskal算法:找权值最小的边,若并入后构成回路则舍弃Kruskal算法求最小生成树：设N=(V,E)是连通网,求最小生成树令T=(V,),各顶点自成一连通分量在E中找代价最小的边,若该边的顶点落在不同连通分量上，则将其并入,依次类推至所有顶点到一个连通分量上总O(eloge)，与n无关，适合稀疏图abcdegf195141827168213ae12dcbgf71485316217121819Kruskal算法是逐条边并入

29、，检查是否构成回路；Prim算法是逐个顶点并入，根据并入顶点找最小边；普里姆Prim算法求最小生成树：abcdegf195141827168213ae12dcb7aaa1914180e12ee8160d3dd7210c50e0gd0f0设U代表已并入最小生成树中的顶点的集合，最初任选一点放入U。之后找U到U最小边，将对应新顶点并入，共N-1轮即可从顶点u0开始,令U=u0, 初始化u0到其余各顶点距离找最小的边输出,并入新顶点,赋0+更新表使U到非U距离更小。如上重复n-1次构造下表对应的数组,每个元素对应一个顶点,元素取值是U中到当前点最近的点和边的权值,顶点被并入U后权值置0struct

30、VertexType adjvex; /中到当前点最近的点名称 VRType lowcost; /中点到当前点的最小代价closedgeMAX_VERTEX_NUM;aaa191418void MiniSpanTree_Prim(MGraph G, VertexType u) /用普里姆算法从u出发求网G(邻接矩阵表示) 最小生成树,输出各边 k=LocateVex (G, u); closedgek.lowcost = 0; /将u并入U,赋0 for ( j=0; jG.vexnum;+j ) /据u更新数组元素代价 if (j!=k)closedgej = u, G.arcskj.adj

31、 ; for (i=1; ik closedgek.lowcost=0; /将k号结点并入U，赋0 for(j=0;jG.vexnum;+j)/据k号结点更新数组元素代价 if (G.arcskj.adjclosedgej.lowcost） closedgej=G.vexsk,G.arcskj.adj; 将初始点u并入U,初始化表;之后找小边并入,赋0+更新重复复杂度为O(n2),与边数无关，适合稠密图作业：7.7prim算法注意画表，多张Kruscal算法，手工执行，直接给答案abcdegf195141827168213ae12dcbgf71485316217121819强连通图,强连通分量

32、 (有向图) （1）各顶点的入/出度；（2）邻接矩阵；（3）邻接表、逆邻接表、十字链表（4）强连通分量；1245361 4230 12 A B C D E邻接表画法:头结点两成员，是数组； 弧结点中存在的是下标，此例要减17.5.1 拓扑排序AOV-网:顶点表示活动,弧表示活动间先后(依赖)关系的有向图.AOV-网用以表示工程或系统的施工计划，可据此判断工程是否可以顺利进行AOV-网中应存在一个覆盖全部顶点的序列(全序),在该序列中顶点出现的顺序满足网中的先后关系(偏序)。一个全序就对应一个合法的完整工序BDACBDAC由某个集合上的一个偏序得到该集合上的一个全序,该操作称为拓扑排序。若得到一

33、个含全部顶点的拓扑有序序列(全序)则说明工程可顺利开展,不存在则说明图中存在有向回路,不合理何谓拓扑排序BDACABCD或ACBD均是含全部顶点的拓扑有序序列(DAG图)BDAC不存在含全部顶点的拓扑有序序列, 存在有向回路BCDB从有向图中选取一没有前驱的顶点并输出之；重复上述两步，至图空(得一全序)或图不空但不存在无前驱的顶点(得一有向环)。从图中“删除”此顶点及所有从其出发的弧如何进行拓扑排序abcghdfeabchdgfeBDACA入度0顶点入栈,删除(出栈并据此更新入度),零入度者入栈重复至栈空，若弹出的元素个数小于顶点数则说明存在回路，计划不合理3、拓扑排序算法的实现Status

34、TopologicalSort(ALGraph G)/G用邻接表存储,若G无回路则输出拓扑有序序列,返OK, 否则返ERROR. FindInDegree(G,indegree);/求各顶点入度存入数组indegree InitStack(S); for(i=0;iG.vexnum;+i) if(!indegreei) Push(s,i); count=0; /用以对输出的顶点进行计数 while (!StackEmpty(S) Pop(S,i); printf(G.verticesi.data); +count; if(countnextarc) k=p-adjvex; - -indegre

35、ek; /更新入度 if(!indegreek) Push(S,w);/新入度为零的顶点入栈 最初求入度O(n+e); 第一波顶点入栈O(n)；若为DAG图则每个顶点入栈、出栈各一次,O(n);入度减1的操作执行e次,故总复杂的度O(n+e)入度0顶点入栈,删除(出栈并据此更新入度),零入度者入栈重复至栈空，若弹出的元素个数小于顶点数则说明存在回路，计划不合理作业：9 执行教材中的拓扑排序算法，写出得到的拓扑有序序列7.5.2 关键路径AOE网：顶点表示状态，弧表示活动，弧权表示完成活动所需时间。用以估算工程的完成时间问:最短工期多长？哪些活动是影响工期的“关键活动”abcdefghk6452

36、1187244源点汇点174关键路径(长度最长的路径)决定工期关键活动:工程正常开展最早开始时间等于最迟开始时间的活动ee(act) =ve(头) 与 el(act)=vl(尾) - dur(act)ve(源点)=0.对普通顶点v,设W为其前驱顶点集则ve(v)=max ve(w)+dut(w,v) | wW 如何保证求ve(v)时ve(w)已经求出？关键活动求取求各点最早到达时间ve(x)abcdefghk64521187244作法:各顶点ve初始化为0,找无前驱顶点,据其ve值更新后继ve值, “删除”如此重复,至图空或发现回路.实际是按拓扑序00000000064571157151418

37、abcdefghk64521187244找无前驱顶点,据其ve值更新后继ve, “删除”重复也可先写出拓扑序列，后据序列求:a - d - f - c - b - e - h - g - kStatus TopologicalOrder(ALGraph G，Stack &T)/求个顶点最早到达时间计入全局数组ve,T按访问顺序存储各顶点,求vl用 ve0.G.vexnum-1=0; FindInDegree(G,indegree); InitStack(S); InitStack T; for(i=0;inextarc) k=p-adjvex; -indegree(k); if(indegre

38、ek= =0) Push(S, w); if(vej+*(p-info)vek)vek=vej+*(p-info) if(countnextarc) k=p-adjvex; dut=*(p-info); /对应活动的持续时间 if( vlk-dut vlj ) vlj= vlk-dut; for(j=0;jnextarc) k=p-adjvex; dut=*(p-info); ee=vej; el=vlk-dut/活动的最早/迟开始时间 if(ee=el) printf(j,k,dut,ee,el, ); else printf(j,k,dut,ee,el, ); 06457715141818

39、1416107866000064577715141416023668871002302630266302866302886630278866302107886630216107886630214161078866302ee作业题1：7.10 求关键活动a - d - f - c - b - e - h - g - kabcdefghk6452118724417400000000064571157151418181818181818181818161486610807回顾：06457715141818141610786600006457771514141602366887100230263026

40、6302866302886630278866302107886630216107886630214161078866302ee单源最短路径每一对顶点之间的最短路径7.6 最短路径（P187）集合S存放已找到最短路的顶点将源并入S,初始化源到V-S中各顶点的最短路径在V-S中找长度最小的顶点并入S,据此更新再找再更新,共重复n-1轮v0v1v2v4v5100301050510v36020终点路径长度v0v0-v00v1V2v0-v210V3V4v0-v430V5v0-v5100终点路径长度v0v0-v00v1V2v0-v210V3v0v2v360V4v0-v430V5v0-v5100终点路径距离

41、v0v0-v00v1V2v0-v210V304350V4v0-v430V5045907.6.1单源最短路径-Dijkstra算法迪杰斯特拉算法实现：设辅助数组D,Dk存储当前所得从源到顶点k的最短路长度finalk标记k号顶点已并入SPvw标记源到v的最短路上w是否出现for(v=0;vG.vexnum;+v) finalv=FALSE;/最初未得源点v0到v的最短路 for(w=0;wG.vexnum;+w) pvw=FALSE;/最短路最初为空,不含任何顶点 Dv=G.arcsv0v; /根据v0更新 if(Dvv00v1V2v0-v210V3V4v0-v430V5v0-v5100每次循环

42、都找距离最小未并入的顶点并入S，更新，重复n-1轮终点路径距离v0v0-v00v1V2v0-v210V3V4v0-v430V5v0-v5100v0v1v2v4v5100301050510v36020for(i=1;iG.vexnum;+i) min=INFINITY; for(w=0;wG.vexnum;+w) if(!finalw&Dwmin) v=w; min=Dw finalv=TRUE; for(w=0;wG.vexnum;+w) if( !finalw & (min+G.arcsvw)v00v1V2v0-v210V3v0v2v360V4v0-v430V5v0-v5100迪杰斯特拉算法

43、的实现 for(i=1;iG.vexnum;+i)/重n-1轮,每轮找最小的,并入更新 min=INFINITY; for(w=0;wG.vexnum;+w) if(!finalw&Dwmin) v=w; min=Dw finalv=TRUE; for(w=0;wG.vexnum;+w) if( !finalw & (min+G.arcsvwDw) ) Dw= min+G.arcsvw; Pw0.G.vexnum=Pv0.G.vexnum;Pww=TRUE; /复杂度O(n2),单源单终点问题也是O(n2)void ShortestPath_DIJ(MGraph G,int v0,PathMa

44、trix &P,ShortPathTable &D) for(v=0;vG.vexnum;+v) /初始化数组，并入v0并更新 finalv=FALSE; for(w=0;wG.vexnum;+w) pvw=FALSE; Dv=G.arcsv0v; if(DvInFINITY)pvv0=TRUE;pvv=TRUE; Dv0=0; finalv0=0;7.6.2 任意一对顶点间的最短路径每次以一个顶点为源点调用Dijkstra算法，复杂度O(n3)Floyd算法(复杂度同，但形式简单):D(k)ij表示从i顶点到j顶点的“某些”路径中最短路径的长度，这些路径中，内部各顶点的标号不超过kD(-1)

45、ij表示i直接到j(内部无顶点)的情况,值G.arcsijD(0)ij意味着i到j中间可含0号顶点;D(2)ij意味着i到j中间可含0、1、2号顶点; D(n-1)ij意味着什么？D(k)ij=minD(k-1)ij , D(k-1)ik+D(k-1)kj ACB461132Floyd算法求任意顶点间的最短路ACB461132D(k)ijk=-1,0,1,2P(k)ijk=-1,0,1,2D(-1)ij=G.arcsijD(k)ij=minD(k-1)ij, D(k-1)ik+D(k-1)kj . k=0,1,n-1Piju表示i到j最短路中u号顶点是否出现765Floyd算法void ShortestPath_FLOYD(MGraph G, PathMatrix &Pnnn,DistancMatrix &D) /初始化D(-1)与P(-1) for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j) Dij=G.arcsij; if(DijG.vexnum-1 for(k=0;kG.vexnum;+k) for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j) if(Dik+