《数据结构与算法》第七章地图资料
icve智慧职教首页
第七章图
7.1图的定义
7.2图的记忆结构
7.3遍历图
7.4图的连接性问题
7.5有向无环图及其应用
7.6最短路线
7.1图的定义
一.有向图和有向图
顶点Vertex
V:顶点的穷非空集
VR—两个顶点之间关系的集合
(VR
表示从v到w有弧Arc
v称为弧尾或初始点，Tail
w称为弧头或端点，Head
有向图有向图
稀疏图
稠密图
网络
子图
邻接点
相关
顶点的度、入度、出度
图中边/弧的数量与顶点度的关系
路径长度
连通图
或循环周期
简单路径
简单的电路
强连通图
完全图朝向完全图
由顶点的集合和弧的集合构成的图被称为有向图
G1=(V1，A1 ) ) ) ) )。
V1={v1，v2，v3，v4}
A1={，
如果是VR的话一定会有VR
用无序对(v，w )代替边缘Edge来称呼
由顶点的集合和边的集合构成的图称为无向图
G2=(V2，E2 ) ) ) )。
V2={v1，v2，v3，v4，v5}
E2={(V1，v2 )、v1，v4 )、v2，v3 )、v2，v5 )、v3，v4 )、v3，v5 ) }
二.完整图Completed Graph
完整图
有n*(n-1 )/2边的有向图
有向完全图
有n*(n-1 )条弧的有向图
稀疏图
边和弧少的图
稠密图
网络
有权利的图
三.子图Subgraph
曲线g=(v，e )，g1=) v1，E1 )有两个的情况
在v1v、e1e的情况下，将G1称为g的子图
子图
四.度
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，v1〉A，
v称为v1或与v1相邻的自己v
弧〈v，v1〉与顶点v、v1相关联
以顶点v为开头的弧线的条数称为v的进入度，表示为id(v )
以顶点v为尾的弧线的条数称为v的出度，表示为od(v )
顶点v的度TD(v )=id ) v ) od ) v ) )。
=
=
=
=
=
=
n
I
I
n
I
I
n
I
I
e OD v
e ID v
e TD v
1
1
1
（）
（）
（）
2
1
图中边/弧的数量与顶点度的关系
(图中有n个顶点时，为e条边/圆弧)
五.路径
1 .有向图g=(v，e )中
从顶点v到v1的路径是顶点序列：
v=Vi，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，j〉a，1jm
4 .第一个顶点和最后一个顶点相同的路径称为环或
环形循环
5 .序列中顶点不重复的路径称为简单路径
除了第一个和最后一个顶点外，剩下的顶点不重复
电路称为简单电路
六.连通图Connected Graph
1 .无向图
据说从v到v1有路径，v和v1是相连的
图中任意两个顶点vi、vjv相连的情况
把g叫做连通图
2 .无向图有n个顶点和小于n-1条边的情况
该图为非连通图
只要有n-1以上的边，就一定有环
3 .有向图
对于每对vi、vjv，都存在从vi到vj、从vj到vi的路径。
g叫强连通图
七.图中ADT
ADT Graph
{数据对象V:V是具有相同特性的数据元素集合，称为顶点。
数据关系r :
R={VR} VR={|v，wV且p(v，w )，
表示从v到w的弧，
谓词p(v，w )定义弧的含义和信息}
基本操作p :
creategraph(g，v，VR；
初始条件： v是图表的顶点集，VR是图表内的弧的集合。
操作结果：按照v和VR的定义构建图g。
Estroygraph(g )；
存在初始条件：图表g。
操作结果：销毁图g。
位置vex (g，u )；
初始条件：存在图g，u和g的顶点有相同的特征。
如果操作结果：中有顶点u，则返回该点在图中的位置，否则返回其他信息。
getvex(g，v )；
初始条件：存在图g，v是有g的顶点。
操作结果：返回v的值
putvex(g，v，value )；
初始条件：存在图g，v是有g的顶点。
操作结果：将value代入v。
第一个adjvex (g，v )；
初始条件：存在图g，v是有g的顶点。
操作结果：返回v的第一个相邻顶点。
如果顶点没有与g相邻的顶点，则返回“天空”。
nextadjvex(g，v，w )；
初始条件：存在图g，v是g中的某个顶点，w是v的邻接顶点。
操作结果：返回v的(针对w的)下一个邻接顶点。
如果w是v的最后一个相邻点，则返回“空”。
insertvex(g，v )；
初始栏
件：图G存在，v和图中顶点有相同特征。操作结果: 在图G中增添新顶点v。DeleteVex(&G,v);初始条件：图G存在，v是G中某个顶点操作结果：删除G中顶点v及其相关的弧。InsertArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧 操作结果：在G中删除弧 初始条件：图G存在，v是G某个顶点，Visit是顶点的应用函数。操作结果:从顶点v起深度优先遍历图G，并对每个顶点调用visit一次且仅一次。一旦visit()失败，则操作失败。BFSTraverse(G,v,Visit());初始条件：图G存在，v是G某个顶点，visit是顶点的应用函数。操作结果: 从顶点v起广度优先遍历图G，并对每个顶点调用visit 一次且仅一次。一旦visit()失败，则操作失败。}ADT Graph 7.2 图的存储结构 在图中，无法用数据元素在存储区的物理位置表示元素之间的关系。一、数组表示法(邻接矩阵表示法)用一个数组存储顶点的信息，用另一个数组存储边或弧的信息----邻接矩阵0123v1 v2v3v401234 南校区，105号北一区，83号北二区，56号东一区，甲23东二区，5号15105 30122032 104 1.图的数组存储表示 // _ _ _ _ _ _图的数组（邻接矩阵）存储表示 _ _ _ _ _ _ _#define INFINITY INT_MAX // 最大值∞#define MAX_VERTEX_NUM 20 //最大顶点个数typedef enum {DG,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网}typedef struct ArcCell {VRType adj; //VRType是顶点关系类型.对无权图,用1或0//表示相邻否；对带权图，则为权值类型。InfoType *Info; //该弧相关信息的指针}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM];// 顶点向量AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧数GraphKind kind; // 图的种类标志}MGraph;Mgraph G1;G1.vexnum=4G1. arcnum=4G1.kind=DG0 123 v1v2v3v4G1.vexs G1.arcs[0][1].adj=1G1.arcs2．图的构造方法 Status CreateGraph( MGraph &G){// 采用数组（邻接矩阵）表示法，构造图Gscanf(&G.kind);switch (G.kind) { case DG: return CreateDG(G); // 构造有向图Gcase DN: nretur CreateDN(G); // 构造有向网Gcase UDG: return CreateUDG(G); // 构造无向图Gcase UDN: return CreateUDN(G); // 构造无向网Gdefault : return ERROR;} }// CreateGraph Status CreateUDN(MGraph &G){//采用数组（邻接矩阵）表示法，构造无向网Gscanf(&G.vexnum, &G.arcnum, &IncInfo); // IncInfo 为0则各弧不含其它信息for (i=0; i Input(* G.arcs[i][j].info); // 若弧含有相关信息,则输入G.arcs[j][i] =G.arcs[i][j]; // 置 } // CreateUDN 二、邻接表Adjacency List方法：对每个顶点建立一个单向链表链接与vi有边相连的顶点（无向图）或从vi出发到达的顶点（有向图）data firstarc指向该点出发到达的第一条弧adjvex nextarc info每个顶点对应一个头结点 每条边/弧对应一个结点 到达顶点 下一条边/弧 边的信息无向图边结点有向图 //- - - - - - - 图的邻接表存储表示 - - - - - - -#define MAX_VERTEX_NUM 20typedef struct ArcNode{int adjvex; // 该弧所指向的顶点的位置 struct ArcNode * nextarc; // 指向下一条弧的指针InfoType * info; // 该弧相关信息的指针}ArcNode ;typedef struct VNode { VertexType data; // 顶点信息 ArcNode * firstarc; // 指向第一条依附顶点的弧的指针}VNode, AdjList[MAX_VERTEX_NUM ];typedef struct { AdjList vertices; int vexnum, arcnum; // 图的当前顶点数和弧数int kind; // 图的种类标志 } ALGraph;ALGraph G1;G1.kind=DG;G1.vexnum=4G1.arcnum=4G1.verticesdata firstarcadjvex info nextarc三、十字链表 Orthogonal List方法：图中的每个顶点用一个结点表示：图中的每一弧也用一个结点表示：data firstin firstout tailvex headvex hlink tlink info# define MAX_VERTEX_NUM 20typedef struct ArcBox{ int tailvex, 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; // 有向图的当前顶点数和弧数} OLGraph ;Status CreateDG(OLGraph &G){ //采用十字链表存储表示， //构造有向图G, IncInfo为0则各弧不含其它信息 scanf(&G.vexnum, &G.arcnum, &IncInfo);for(i=0; i for(k=0; k } // CreateDG 四、邻接多重表 Adjancency Multilist顶点和边分别用一个结点表示边： mark ivex ilink jvex jlink info该边是否搜索过顶点i在图中的位置(编号)下一条与i有关的边 有关边的信息data firstedge顶点： 242342 # define MAX_VERTEX_NUM 20 typedef enum { unvisited, visited}VisitIf ;typedef struct EBox{ VisitIf mark; // 访问标记 int ivex, jvex; // 该边依附的两个顶点的位置0struct 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 ; 7．3图的遍历Traversing Graph•图的遍历： 从图中某个顶点出发访问遍图中每个顶点，且图中每个顶点仅被访问一次。•遍历过程中每个顶点可能被访问多次，因此，每个顶点被访问后需作一个标记一般用一个数组标记某个结点是否被访问•遍历方法：深度优先搜索、广度优先搜索一、深度优先收索Depth-First-Search(DFS)方法： 从图中某个顶点出发（设为v1），访问v1，从v1出发,选择一个未被访问的邻接点vk,访问vk，从vk出发，选择一个未被访问的邻接点,…………若vk的所有邻接顶点都被访问过了，回到vk-1,再选择的一个未被访问的邻接点,………若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程直到所有顶点均被访问过为止。v1v2v3v4v5v6v7 从v 1出发 ,选择一个未被访问的邻接点vk ,访问vk， 从v k出发 ，选择一个未被访问的邻接点,…………若vk的所有邻接顶点都被访问过了，回到vk-1 ,再选择的一个未被访问的邻接点,………若图中仍有未被访问的顶点，从中选择一个作为起点，重复上述过程直到所有顶点均被访问过为 止。v 8 Boolean visited[MAX]; // 访问标志数组Status (* VisitFunc))(int v); // 函数指针变量void DFSTraverse(Graph G, Status(* Visit)(int v)) // 对图G作深度优先遍历{VisitFunc = Visit; //使用全局变量VisitFunc，使DFS不必设函数指针参数 for(v=0; v //从第v个顶点出发递归地深度优先遍历图Gvoid DFS(Graph G, int v){visited[v]=TRUE;VistFunc(v); //访问第v个顶点for(w=FirstAdjVex(G,v);w>0;w=NextAdjVex(G,v,w))if(!visited[w]) DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFSprintf(v); //起什么作用}AB DCE FHGK123456789 搜索回退ABDCEFHGK1 2345679 二、广度优先收索Breadth-First-Search(BFS)方法： 从图中某个顶点出发（设为vi），访问vi，从vi出发，依次访问vi的所有未被访问的邻接点，再从这些邻接点出发，依次访问它们的所有未被访问的邻接点,…………若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程直到所有顶点均被访问过为止。 void BFSTraverse(Graph G,Status(* Visit)(int v)){ // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。for(v=0; v for(w=FirtAdjVex(G,u);w>0;w=NextAdjVex(G,u,w))if(!visited[w]) {visited[w] = TRUE; Visit(w); EnQueue(Q,w); } // u的尚未访问的邻接顶点w入队列Q}//while }// if }// BFSTraverse搜索ABDCE FHGK1 24356789ABDCE FHGK124356789 7．4图的连通性问题 一、无向图的连通分量和生成树1.连通分量 无向图的极大连通子图。即:子图中不能再增加一个顶点,已有顶点的边均包含在内。无向图的连通分量的产生-----多次调用DFS2.生成树一个连通图的生成树是一个极小连通子图,且含有图中全部顶点无向图连 通分量 连通图 生成树3.无向图的生成树 对一个连通图G，从图中任意一个顶点出发遍历图时，把E分为E1和E2，E1为遍历过程中经过的边的集合，E2为剩余边的集合，则E1与V构成G的极小连通图，即连通图的一棵生成树若遍历为DFS，则称为深度优先生成树若遍历为BFS，则称为广度优先生成树v1 v2v3 v4 v5v6v7v8深度优先生成树v1v2v3v4 v5v6vv 7 8 广度优先生成树v1v2v3v4v5v6v7v8 对于非连通图，每个连通分量中的顶点集合,加上遍历时经过的边，构成了非连通图的生成森林。生成森林 4.无向非连通图的深度优先生成森林 void DFSForest(Graph G,CSTree &T){ //建立无向图的深度优先生成森林的(最左)孩子(右)兄弟链表T=NULL;for(v=0; v DFSTree(G,v,p); //建立以p为根的生成树}}//DFSForest void DFSTree(Graph G, int v, CSTree &T){ // 从第v个顶点出发深度优先遍历图G，建立以T为根的生成树。visited[v]=TRUE; first =TRUE;for(w=FisrtAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w]) {p=(CSTree)malloc(sizeof(CSNode)); // 分配孩子结点*p={GetVex(G,w), NULL, NULL };if(first) // w是v的第一个未被访问的邻接顶点 {T->firstchild=p; first= FALSE; } //是根的第一个孩子结点else // w是v的其它未被访问的邻接顶点{q->nextsibling = p; } //是上一邻接顶点的右兄弟结点q = p; DFSTree(G,w,q);//从第w个顶点出发深度优先遍历图G,建立子生成树q}// if}// DFSTree 二、最小生成树Mininum Cost SpanningTree问题： 设有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-Uv 4v6v1v2v3v51555666 3 42v 1v3 1v1v3 1v64v 42v25v53v 1v3 1v64v 42v 1v3 1v64v25v42v 1v3 1v64 假设网N的任何一棵最小生成树都不包含(u ,v)设T是N上的一棵最小生成树，把(u ,v)加入到T中则T中必存在一条包含(u ,v)的回路同时,T中必存在另一条边(u’,v’)，其中u’U v’V-U并且u和u’ ,v和v’之间均存在路径相通删去边(u’,v’)，则可削去回路，得到另一棵生成树T’ 显然,T’的代价不高于T,且包含边(u ,v),矛盾。设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的最短的边}closedge[MAX_VERTEX_NUM];void MiniSpanTree_PRIM(MGraph G,VertexType u){k = LocateVex(G, u );for(j=0;j v1 1 v1 5 {v1} {v2,v3, v4,v5,v6} 2 adjvex lowcost v3 5 0 v1 5 v3 6 v3 4 {v1,v3} {v2,v4, v5,v6} 5 adjvex lowcost v3 5 0 v6 2 v3 6 0 {v1,v3,v6} {v2,v4,v5} 3 adjvex lowcost v3 5 0 0 v3 6 0 {v1,v3, v6,v4} {v2,v5} 1 adjvex lowcost 0 0 0 v2 3 0 {v1,v3, v6,v4,v2} {v5} 4 A BCE D 2 5 6 3 4 4 2 4 1234UV-Ukadjvexlowcost A2A∞A6A4{A} {B,C,D,E}adjvex lowcost{A,} { }adjvexlowcostadjvexlowcostadjvexlowcost3.克鲁斯卡尔算法设连通图N=（V，E）(1)构造非连通图T=(V,),图中每个顶点自成一个连通分量 (2)在E中选择代价最小的边（u，v），并删去该边。若(u,v)落在T中不同的连通分量上,则将此边加入T中(3)重复(2），直到T中只有一个连通分量为止v 1v2v3v4v5v6v4v6v1v2v3v51555666 3421v1v2v3v4v5v612453v1v2v3v4v5v612v1v2v3v4v5v6123v1v2v3v4v5v614236.5有向无环图及其应用 一、DAG图 -----Directed Acycline Graph一个无环的有向图称为有向无环图二、拓扑排序 Topological Sort 1．AOV网 Activity On Vertex Network用顶点表示活动，用弧表示活动之间的优先关系的有向图称为顶点表示活动的网，简称AOV网。 在网中,若顶点i到顶点j有一条路径,则i为前驱, j为后继。若 数据结构与算法面向对象程序设计计算机网络原理 信息科学导论 电路原理 大学物理数字逻辑电路实验 组成原理实验操作系统 汇编语言程序设计高等数学1离散数学数据库原理线性代数基础物理实验B高等数学2高等数学3 C程序设计实验数据结构实验电路原理实验概率与数理统计数字逻辑电路计算机组成原理 网络原理实验操作系统实验面向对象实验2．拓扑次序 设AOV网中有n个顶点V1，V2，Vn，将顶点排成这样一个线性次序：Vi1，Vi2，Vin，其中i1，i2，in是1到n的一个排列且若〈V ij，V ik〉A，则j (1)在网中选一个没有前驱的顶点且输出它(2)从图中删去该顶点及所有以它为尾的弧(3)重复(1)(2)直到所有顶点被输出或图中不存在无前驱的顶点为止。采用邻接表作存储结构。用一个数组indegree存放顶点的入度。用一个栈存放入度为0的顶点 Status TopologicalSort( ALGraph G){ //有向图G采用邻接表存储结构。//若G无回路,则输出G的顶点的一个拓扑序列并返回OK,//否则ERROR FindInDegree(G,indegree); //对各顶点求入度indegreeInitStack(S); // 建零入度顶点栈Sfor(i=0; i {Pop(S,i); printf(i,G.vertices[i].data); ++count; // 输出i号顶点并计数 for(p=G.vertices[i].firstarc; p; p=p->nextarc){ k = p->adjvex; //对i 号顶点的每个邻接的入度减1if(!(- -indegree[k]))Push(S, k); //若入度减为0，则入栈}// for} DestroyStack(S); if(count 3 456 拓扑次序为：v6、v1、v4、v3、v5、v24.关键路径AOE网—Activity On Edge顶点----事件边------活动 权------活动持续的时间用AOE网估计工程的完工时间Vi表示在此之前的活动已完成，在此之后的活动可以开始a2=4a6=212345 6 7剁馅5 煮鸡蛋1 包饺子4 最短要多久才能包好饺子,开始聚餐? 在一般情况下,AOE网中只有一个入度为0的顶点,称为源点 只有一个出度为0的顶点，称为汇（聚）点？完成整个工程至少需要多少时间------从源点到汇点的最长路径？哪些活动是影响工程进度的关键路径长度最长的路径叫做关键路 直径 危机路径 从源到Vi的最长路径称为事件的最早发生 时间，也就是以Vi为尾的所有弧所表示的活动的最 早开始时间 e(I )表示ai的最早开始时间 L(I )表示ai的最晚开始时间 L(I )-E )为时间富馀 关键路径上的所有活动都是l(I )=e ) ) 所有e(I )=L )的活动都称为关键活动。 假设用弧表示ai ve(j )表示事件j最早发生时刻 VL(j )表示事件j的最晚发生时刻 ai的持续时间为dut () )。 (e ) I )=ve ) j ) L(I )=VL(k )-dut ) ) a2 =4 a6=2 最早起始时间：前体活动按时完成时的起始时间 最晚的开始时间：保证在所有活动都能按期完成的情况下最晚 开始时间 关键路径上的所有活动最早=最慢 计算方法： (1) ve )0)=0 )2)按拓扑顺序计算： () )，) } 1，2，1 ， = = ve j Max ve i dut i j j n i j T I 在此，t是以第j个顶点为开头的所有弧的集合 i1 i2 i3 j (3) VL(n-1 ) VL(n-1 ) ) ) ) )。 (4)按逆拓扑顺序计算： 在这里，s是以第I个顶点为尾部的所有弧的集合 () )，) } 2，3，0 ， = = vl i Min vl j dut i j i n n i j S j j1 j2 j3 I )5)根据各顶点的ve和vl的值 计算各弧s的e(s )和e(s ) ) a2 =4 a6=2 ve(3)=5 ve(4)=7 ve(7)=14ve ) )8)=18 VL(8)=18VL ) )7)=14 VL(6)=16 VL(4)=7 ve(0)=0 VL(1)=6 VL(2)=6VL(0)=0 ve(5)=7 VE(6)=16 VL(5)=10 vl(3) )3)=8 ve(2)=4 ve(1)=6 statustopologicalorder (algraphg，Stack T ) )。 {Findindegree(g，indegree )； //对各顶点求出入度indegree initstack(s )； //创建零线顶点堆栈s for(I=0； inextarc ) {k=p-adjvex； //j号顶点的每个相邻点减1 if(--indegree[k]==0) push(s，k )； //收入减少到0时，进入堆栈 if(ve(j ) ) p-info ) ve ) k ) )=ve ) j ) ) p-info )； ((/) (p-info )=dut ) ) ) ) ) ) ) ) )。 }//while Estroystack(s )； 联合外部任务(if ) {k=p-adjvex； dut=*(p-info； //dut (VL [ k ]-dutnextarc ) )。 { k=p-adjvex； dut=*(p-info； ee=ve[j]； el=vl[k]-dut； tag=(ee==E1 )？ “*' : printf(j，k，dut，ee，el，tag )； //输出重要事件 } }//CriticalPath 7.6最短路线 用顶点表示城市 用边表示城市间的交通状况 以端权进行城市间的消费(距离、时间、各种 费用等) 一、从一点到另一点，通过的节点最少 二.从一个来源到其余各顶点的最短路径 给定权利的有向图g和源点v， 求出从v到g剩下的各点的最短路径 方法：按路径长度从长到短生成最短路径 ------------删除器Dijksta方法 v0 v5 60 v1 v2 v3 v4 100 30 10 10 50 5 20 v0 v5 v1 v2 v3 30 v4 10 10 20 存储结构 用加权邻接矩阵arcs表示加权有向图 arcs[i][j]= Vi，VJa 的权重Vi，VJa 演算法 )1)将s作为发现了距离v的最短路径的终点集合， 初始值s= D[i]表示从v到Vi的最短路径的长度 如果a，D[i]是从v到Vi的权利，否则 即D[i]=arcs[LocateVex(G，v )，i]，VIV (2)选择Vj以使d(j )=min ) d ) I )|VIV-s ) 然后修正S: S=S{j} Vj是从v出发的最短路径的顶点 )3)修正从v出发到集合V-S就任点Vk的可到达的最短路径 直径 也就是说，当从D[j] arcs[j][k]或v向Vk添加弧线时，其中 vks ) (4) ) )总计重复n-1次，从v到图表中剩下的各顶点的最大值 短传 终点 从V0到各终点的d值和最短路径的求解过程 V1 V2 V3 V4 Vj V5 i=1 V2 10 (V0，V2 ) ) ) ) ) )。 30 (V0，V4 ) ) ) ) )。 100 (V0，V5 ) ) ) ) ) )。 {V0，V2} s 30 (V0，V4 ) ) ) ) )。 100 (V0，V5 ) ) ) ) ) )。 60 (V0，V2，V3 ) )。 {V0、V2、V4} V4 i=2 i=5 50 (V0，V4，V3 ) )。 90 (V0，V4，V5 ) )。 V3 i=3 (V0，V4，V3，V5 ) )。 i=4 {V0，V2，V3，V4，V5} {for(v=0； v的最短路径： )1)的路径长度相比，较小的一方从Vi开始 到Vj的中间顶点编号为0以下的最短路径 )2)加上顶点V1， 和睦相处 中间顶点编号为0以下最短路径， 与相比， 较小的一方是从Vi到Vj的中间顶点编号为1以下的最短路径 定义n阶方阵的顺序： 表示从Vi到Vj中间顶点编号为k以下的最短路径 的长度、 [ ][ ] min{ [ ][ ]，[ ][ ] [ ][ ]} [ ][ ] [ ][ ] (1)1) )1) )。 0 1 （） (1) ) ) )。 D i j D i j D i k D k j D i j arcs i j NK k n K = = d (n1 ) ) )。 [i][j]是从vi到vj的最短路径长度 v0v1 v2 6 4 11 3 2 )3)按V2、V3、…、Vn-1的顺序加入， 合计n次比较后，求出从Vi到Vj的最短路径 voidshortestpath_Floyd(mgraphg， PathMatrix p[ ]，DistancMatrix D ) {for(v=0； v
报名招生
