《《数据结构》课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构》课件.ppt（110页珍藏版）》请在三一办公上搜索。
1、第7章 图,数据结构（C描述）,目录,7.1 图的基本概念,7.2 图的存储结构,7.3 图的遍历,7.4 图的生成树和最小生成树,7.5 图的应用,7.1 图的基本概念,图(Graph)是一种比线性表和树结构更复杂的数据结构。,在线性表中，数据元素之间仅有线性关系，每 个数据元素只有一个直接前驱和直接后继；在树形结构中，数据元素之间有着明显的层次 关系结点间具有分支层次关系，每一层上的结 点只能和上一层中的至多一个结点相关，但可 能和下一层的多个结点相关。,而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图状结构被用于描述各种复杂的数据对象，在自然科学、社
2、会科学和人文科学等许多领域有着非常广泛的应用。,7.1.1 图的定义,图(Graph)是由非空的顶点集合和一个描述顶点之间关系的边（或者弧）的集合组成，其形式化定义为：G（V，E）Vvi|viVertexTypeE(vi,vj)|vi,vj V 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。,无向图G1,有向图G2,例如：对于下图中的无向图G1,对应顶点集和边集为：V(G1)v1,v2,v3,v4,v5；E(G1)(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3
3、,v5),(v2,v5)对于下图中的有向图G2,对应顶点集和边集为：V(G2)v1,v2,v3,v4,v5；E(G2),7.1.2 图的基本术语,有向图和无向图完全图、稠密图、稀疏图 度、入度、出度子图路径连通图权和网,7.2 图的存储结构,图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，即图中顶点的信息以及描述顶点之间的关系（边或者弧）的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。下面介绍几种常用的图的存储结构。,7.2.1 邻接矩阵,1 图的邻接矩阵表示,在邻接矩阵
4、表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i,j）E(G)或i,jE(G),则矩阵中第i行第j列元素值为1，否则为0。,图的邻接矩阵定义为：1 若（i,j）E(G)或i,jE(G)Aij=0 其它情形,例如,对图7-8所示的无向图和有向图,它们的邻接矩阵见图7-9。,无向图,G3,G3的邻接矩阵,图,7,-,9,邻接矩阵表示,有向图,G4,G4,的邻接矩,图,7,-,9,邻接矩阵表示,2 从无向图的邻接矩阵可以得出如下结论,（1）矩阵是对称的;（2）第i行或第i 列1的个数为顶点i 的度;（3）矩阵中1的个数的一半为图中边的数目;（4）很容易判断顶点i 和顶点j之
5、间是否有边相连(看矩阵中i行j列值是否为1)。,3 从有向图的邻接矩阵可以得出如下结论,（1）矩阵不一定是对称的;（2）第i 行中1的个数为顶点i 的出度;（3）第i列中1的个数为顶点 i的入度;（4）矩阵中1的个数为图中弧的数目;（5）很容易判断顶点i 和顶点j 是否有弧相连.,4 网的邻接矩阵表示,类似地可以定义网的邻接矩阵为：wij 若（i,j）E(G)或i,jE(G)Aij=0 若i=j 其它情形,网及网的邻接矩阵见图7-10。,图,7,-,10,网及邻接矩阵示意图,(a)网G5,(b)网G5的邻接矩阵,3 图的邻接矩阵数据类型描述,用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关
6、系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：,#define n 6/*图的顶点数*/#define e 8/*图的边（弧）数*/typedef char vextype；/*顶点的数据类型*/typedef float adjtype；/*权值类型*/typedef structvextype vexsn；adjtype arcsnn；graph；,4 建立无向图的邻接矩阵,void creatadj(graph/初始化邻接矩阵,for(k=1;k=e;k+)scanf(“d%d”,该算法的时间复杂度为O（n2）。,5.建立有向图的邻接矩阵,void creatad
7、j(graph/初始化邻接矩阵,for(k=1;k g.arcsij=1;该算法的时间复杂度为O（n2）。,6.建立无向网的邻接矩阵,void creatadj(graph/初始化邻接矩阵,for(k=1;k=e;k+)scanf(“%d%d%f”,该算法的时间复杂度为O（n2）。,7.建立有向网的邻接矩阵,void creatadj(graph/初始化邻接矩阵,for(k=1;k 及权值w g.arcsij=w;该算法的时间复杂度为O（n2）。,7.2.2 邻接表,1 图的邻接表表示,将每个结点的边用一个单链表链接起来，若干个结点可以得到若干个单链表，每个单链表都有一个头结点，所有头结点组成
8、一个一维数组，称这样的链表为邻接表。例如，图7-8所示的无向图G3和有向图G4的邻接表见图7-11所示,(,(b),有向图,G4,的邻接表,(c),有向图,G4,的逆邻接表,图,7,-,11,邻接表示例,有向图,G4,(a)无向图G3,(b)无向图G3的邻接表,图711：邻接表示例,图711：邻接表示例,(a)有向图G4,(b)有向图G4的邻接表,(c)有向图G4的逆邻接表,1 从无向图的邻接表可以得到如下结论,（1）第i 个链表中结点数目为顶点i的度；（2）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为n+2e。,2 从有向图的邻接表可以得到如下结论,（1）第i 个链表中结点
9、数目为顶点i的出度；（2）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为n+e。,从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。逆邻接表在图7-11(c)中已经给出，从该图中可知。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。,3 图的邻接表数据类型描述,图的邻接表数据类型描述如下：const int n=maxn；/maxn表示图中最大顶点数const int e=maxe；/maxe图中最大边数struct link/定义链表类型 elemtype data;link*next;struc
10、t node/定义邻接表的表头类型 elemtype v;/顶点信息 link*next;an+1;,4.无向图的邻接表建立,void creatlink()int i,j,k;link*s;for(i=1;idata=j;s-next=ai.next;ai.next=s;,s=(link*)malloc(sizeof(link);s-data=i;s-next=aj.next;aj.next=s;该算法的时间复杂度为O（n+e）。,5.有向图的邻接表建立,void creatlink()int i,j,k;link*s;for(i=1;i,s=(link*)malloc(sizeof(lin
11、k);/申请一个动态存储单元 sdata=j;s-next=ai.next;ai.next=s;该算法的时间复杂度为O（n+e）。,6.网的邻接表的数据类型描述,网的邻接表的数据类型可描述如下：const int n=maxn；/maxn表示网中最大顶点数const int e=maxe；/maxe网中最大边数struct link/定义链表类型 elemtype data;float w;/定义网上的权值类型为浮点型 link*next;struct node/定义邻接表的表头类型 elemtype v;/顶点信息 link*next;an+1;,7 无向网的邻接表建立,void creat
12、link()float w;int i,j,k;link*s;for(i=1;i=n;i+)/建立邻接表头结点 ai.v=i;ai.next=NULL;for(k=1;k=e;k+)scanf(“%d%d%d”,/输入一条边(i,j)及该边上的权值,s=(link*)malloc(sizeof(link);/申请一个动态存储单元 sdata=j;s-w=w;s-next=ai.next;ai.next=s;s=(link*)malloc(sizeof(link);s-data=i;s-w=w;snext=aj.next;aj.next=s;该算法的时间复杂度为O（n+e）。,8 有向网的邻接表
13、建立,void creatlink()float w;int i,j,k;link*s;for(i=1;i及该弧上的权值,s=(link*)malloc(sizeof(link);/申请一个动态存储单元 sdata=j;s-w=w;s-next=ai.next;ai.next=s;该算法的时间复杂度为O（n+e）。,另外，请注意上面的算法中，建立的邻接表不是唯一的,与你从键盘输入边的顺序有关，输入的边的顺序不同，则得到的链表也不同。,7.2.3 邻接多重表,在无向图的邻接表中，每条边（Vi,Vj）由两个结点表示，一个结点在第i个链表中，另一个结点在第j个链表中，当需要对边进行操作时，就需要找到
14、表示同一条边的两个结点，这给操作带来不便，在这种情况下采用邻接多重表较方便。在邻接多重表中，每条边用一个结点表示，每个结点由五个域组成，其结点结构为：,其中mark为标志域，用来标记这条边是否被访问过，i和j域为一条边的两个顶点，next1 和next2为两个指针域，分别指向依附于i顶点的下一条边和j顶点的下一条边。而表头与邻接表的表头类似。邻接多重表的形式见图7-12。,(a),无向图,G6,（,b,）,G6,的邻接多重表,图,7,-,12,邻接多重表示例,7.3 图的遍历,图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是
15、图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。,在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。（我们可以设置一个全局型标志数组visited来标志某个顶点是否被访过，未访问的值为0，访问过的值为1。）在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后
16、，存在如何选取下一个要访问的顶点的问题。,图的遍历通常有深度优先搜索和广度优先搜索两种方式。,深度优先搜索遍历1 深度优先搜索思想,深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索遍历可定义如下：(1)首先访问顶点i，并将其访问标记置为访问过，即visitedi=1；,(2)然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visitedj=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点；(3)若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并
17、重复刚才过程，直到图中所有顶点都被访问完止。,例如，对图7-13所示无向图G7，从顶点1出发的深度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。在无向图G7中，从顶点1出发的深度优先搜索遍历序列举三种为：,1,2,4,8,5,6,3,71,2,5,8,4,7,3,61,3,6,8,7,4,2,5,7,-,13,无向图,G,7,2 连通图的深度优先搜索,若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点，否则只能访问到一部分顶点。另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不唯一的。但是,若我们给定图的存储结构,则从某一顶点出发的遍历结果应是唯
18、一的。,(1)用邻接矩阵实现图的深度优先搜索以图7-13中无向图G7 为例，来说明算法的实现，G7的邻接矩阵见图7-14。,图,7,-,15,邻接矩阵深度优先搜索示意图,算法描述为下面形式：,void dfs(int i)/从顶点i 出发遍历 int j;printf(“%d”,g.vexsi);/输出访问顶点 visitedi=1/全局数组访问标记置i表示已经访问 for(j=1;j=n;j+)if(g.arcsi j=1),用上述算法和无向图G7，可以描述从顶点1出发的深度优先搜索遍历过程，示意图见图7-15，其中实线表示下一层递归调用，虚线表示递归调用的返回。从图7-15中，可以得到从顶
19、点1的遍历结果为 1,2,4,8,5,6,3,7。同样可以分析出从其它顶点出发的遍历结果。,图7-15邻接矩阵深度优先搜索示意图,(2)用邻接表实现图的深度优先搜索仍以图7-13中无向图G7 为例，来说明算法的实现，G7的邻接表见图7-16，,7,-,17,邻接表深度优先搜索示意图,图7-13无向图G7,图716 G7的邻接表,7,-,17,邻接表深度优先搜索示意图,算法描述为下面形式：void dfs1(int i)link*p;printf(“%d”,ai.v);/输出访问顶点 visitedi=1;/全局数组访问标记置为i表示已访问 p=ai.next;while(p!=NULL)if(
20、!visitedp-data)dfs1(p-data);p=p-next;,用刚才算法及图7-16，可以描述从顶点7出发的深度优先搜索遍历示意图，见图7-17,其中实线表示下一层递归，虚线表示递归返回，箭头旁边数字表示调用的步骤。于是，从顶点7出发的深度优先搜索遍历序列，从图7-17中可得出为 7，3，1，2，4，8，5，6。从其它顶点出发的深度优先搜索序列，请读者自已写出。,图717 邻接表深度优先搜索示意图,7.3.2 广度优先搜索遍历1 广度优先搜索的思想,广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜索的基本思想是：(
21、1)首先访问顶点i，并将其访问标志置为 已被访问，即visitedi=1；(2)接着依次访问与顶点i有边相连的所有 顶点W1，W2，Wt；,(3)然后再按顺序（“先被访问的顶点的邻接点”先 于“后被访问的顶点的邻接点”被访问）访问与 W1，W2，Wt有边相连又未曾访问过的 顶点；依此类推，直到图中所有顶点都被访问完为止。,例如，对图7-13所示无向图G7，从顶点1出发的广度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。,在无向图G7中，从顶点1出发的广度优先搜索遍历序列举三种为：1,2,3,4,5,6,7,81,3,2,7,6,5,4,81,2,3,5,4,7,6,8,图7-13
22、无向图G7,2 连通图的广度优先搜索,(1)用邻接矩阵实现图的广度优先搜索遍历仍以图7-13中无向图G7及7-14所示的邻接矩阵来说明对无向图G7的遍历过程,图,7,-,15,邻接矩阵深度优先搜索示意图,根据该算法用及图7-14中的邻接矩阵，可以得到图7-13的无向图G7 的广度优先搜索序列，若从顶点1 出发，广度优先搜索序列为：1，2，3，4，5，6，7，8。若从顶点3出发，广度优先搜索序列为：3，1，6，7，2，8，4，5,从其它点出发的广度优先搜索序列可根据同样类似方法分析。,void bfs(int i)/从顶点i出发遍历 int Qn+1;/Q为队列 int f,r,j;/f,r分别
23、为队列头，尾指针 f=r=0;/设置空队列 printf(“%d”,g.vexsi);/输出访问顶点 visitedi=1;/全局数组标记置1表示已经访问 r+;qr=i;/入队列 while(fr)f+;i=qf;/出队列 for(j=1;j=n;j+)if(g.arcsij=1),算法描述如下：,（2）用邻接表实现图的广序优先搜索遍历仍以无向图G7及图7-16所示邻接表来说明邻接表上实现广度优先搜索遍历的过程,图7-13无向图G7,图716 G7的邻接表,7,-,17,邻接表深度优先搜索示意图,根据该算法及图7-16，可以得到图G7的广度优先搜索序列，若从顶点1出发，广度优先搜索序列为：1
24、，2，3，4，5，6，7，8，若从顶点7出发，广度优先搜索序列为：7，3，8，1，6，4，5，2，从其它顶点出发的广度优先搜索序列可根据同样类似方法分析。,void BFS1(int i)int qn+1;/定义队列 int f,r;link*p;/P为搜索指针 f=r=0;printf(“%d”,a.vi);visitedi=1;r+;qr=i;/进队 while(fdata)printf(“%d”,ap-data.v);visitedp-data=1;r+;qr=p-data;p=p-next;,算法描述如下：,1.对于下图G4和G5，按下列条件试分别写出从顶点v0出发按深度优先搜索遍历得
25、到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。,图,G4,图,G5,图,G4,图,G5,图,G4,图,G5,图,G4,图,G5,图G4,图G5,7.4 生成树和最小生成树,7.4.1 基本概念1 定义,生成树:所有顶点均由边连接在一起，但不存在回路的图叫生成树。生成森林：非连通图每个连通分量的生成树一起组成非连通图的生成森林。,2.特点：一个图可以有许多棵不同的生成树；生成树的顶点个数与图的顶点个数相同；生成树是图的极小连通子图；一个有n个顶点的连通图的生成树有n
26、-1条边；生成树中任意两个顶点间的路径是唯一的；在生成树中再加一条边必然形成回路；含n个顶点n-1条边的图不一定是生成树,通过图的遍历可以得到生成树：利用深度优先搜索遍历得到的生成树，称之为深度优先生成树。通过广度优先搜索遍历得到的，称之为广度优先生成树。,对于深度优先搜索算法DFS或DFS1，由 DFS（i）递归到DFS（j），中间必经过一 条边（i,j），因此，只需在DFS(j)调用前输 出这条边或保存这条边，即可求得生成树 的一条边，整个递归完成后，则可求得生 成树的所有边。对于广度优先搜索算法BFS或BFS1，若i 出队，j 入队，则(i,j)为一条树边。因此，可以在算法的if 语句中
27、输出这条边，算法完 成后，将会输出n-1条边，也可求得生成树。,(a),深度优先生成树,(b),广度优先生成树,图,7,-,1,9,两种生成树示意图,7,-,13,无向图,G,7,4 最小生成树,对于一个连通网,假定每条边上的权均为大于零的实数，生成树不同，每棵树的权（树中所有边上的权值总和）也可能不同。权值最小的生成树称为图的最小生成树。最小生成树的概念可以应用到许多实际问题中。例如有这样一个问题：以尽可能抵的总造价建造城市间的通讯网络，把十个城市联系在一起。,在这十个城市中，任意两个城市之间都可以建造通讯线路，通讯线路的造价依据城市间的距离不同而有不同的造价，可以构造一个通讯线路造价网络，
28、在网络中，每个顶点表示城市，顶点之间的边表示城市之间可构造通讯线路，每条边的权值表示该条通讯线路的造价，要想使总的造价最低，实际上就是寻找该网络的最小生成树。构造最小生成树常用的的方法通常有两种：普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。,7.4.2 普里姆算法,1 普里姆(prim)算法思想,下面仅讨论无向网的最小生成树问题。普里姆方法的思想是：在图中任取一个顶点K作为开始点，令U=k，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后
29、重新调整U中顶点到W中顶点的距离,使之保持最小，再重复此过程，直到W为空集止。求解过程参见图7-20。,假设开始顶点就选为顶点1，故首先有U=1，W=2，3，4，5，6,3,1,2,4,5,6,1,4,5,5,5,3,1,2,4,5,6,4,2,1,5,5,(c)u=1,3 w=2,4,5,6(d)u=1,3,6,w=2,4,5,(e)u=1,3,6,4 w=2,5(f)u=1,3,6,4,2,w=5,7.4.3 克鲁斯卡尔（kruskal）算法1 克鲁斯卡尔算法基本思想,克鲁斯卡尔算法的基本思想是：将图中所有边按权值递增顺序排列，依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构
30、成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。,例如，对图7-20（a）中无向网，用克鲁斯卡尔算法求最小生成树的过程见图7-22。,(a),选第,1,条边,(b),选第,2,条边,(a),选第,1,条边,(b),选第,2,条边,(a)选第1条边,(b)选第2条边,图,7,-,22,克鲁斯卡尔方法求最小生成树的过程,(e)选第5条边但不能选(1,4)边，否则会构成回路，但可选(2,3)或（5,3)之一,或者,图,7,-,22,克鲁斯卡尔方法求最小生成树的过程,7.5最短路径,最短路径:最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个
31、公路网，给定了该网内的n个城市以及这些城市之间的相通公路的距离，能否找到城市A到城市B之间一条距离最近的通路呢？如果将城市用点表示，城市间的公路用边表示，公路的长度作为边的权值，那么，这个问题就可归结为在网图中，求点A到点B的所有路径中，边的权值之和最短的那一条路径。,这条路径就是两点之间的最短路径，并称路径上的第一个顶点为源点（Sourse），最后一个顶点为终点（Destination）。在非网图中，最短路径是指两点之间经历的边数最少的路径。,单源点最短路径1 单源点最短路径,单源点最短路径是指：给定一个出发点(单源点)和一个有向网G=(V，E),求出源点到其它各顶点之间的最短路径。,那么怎
32、样求出单源点的最短路径呢?我们可以将源点到终点的所有路径都列出来,然后在里面选最短的一条即可。但是这样做,用手工方式可以,当路径特别多时,显得特别麻烦,并且没有什么规律,不能用计算机算法实现。,迪克斯特拉(Dijkstra)在做了大量观察后,首先提出了按路长度递增序产生各顶点的最短路径算法,我们称之为迪杰斯特拉算法。,2 迪克斯特拉算法的基本思想,该算法的基本思想是：设置两个顶点的集合S和TVS，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点
33、u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。,Dijkstra算法的正确性可以用反证法加以证明。假设下一条最短路径的终点为x，那么，该路径必然或者是弧（v0，x），或者是中间只经过集合S中的顶点而到达顶点x的路径。因为假若此路径上除x之外有一个或一个以上的顶点不在集合S中，那么必然存在另外的终点不在S中而路径长度比此路径还短的路径，这与我们按路径长度递增的顺序产生最短路径的前提相矛盾，所以此假设不成立。,3 迪杰斯特
34、拉算法的实现,Dijkstra算法的实现:首先，引进一个辅助向量Dist，它的每个分量Di 表示当前所找到的从始点v 到每个终点vi 的最短路径的长度。它的初态为：若从v 到vi有弧，则Disti为弧上的权值；否则置 Disti为。显然，长度为：Distj=MinDi|viV 的路径就是从v出发的长度最短的一条最短路径。此路径为（v,vj）。,那么，下一条长度次短的最短是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是（v,vk），或者是（v,vj,vk）。它的长度或者是从v 到vk 的弧上的权值，或者是Distj和从vj到vk的弧上的权值之和。依据前面介绍的算法思想，在一般情
35、况下，下一条长度次短的最短路径的长度必是：Distj=MinDisti|viV-S 其中，Di 或者弧（v,vi）上的权值，或者是Dk(vkS和弧（vk,vi）上的权值之和。,4 迪杰斯特拉算法描述,根据以上分析，可以得到如下描述的算法：（1）假设用带权的邻接矩阵edges 来表示带权有向图，edgesij 表示弧vi,vj上的权值。若vi,vj不存在，则置edgesij为（在计算机上可用允许的最大值代替）。S为已找到从v出发的最短路径的终点的集合，它的初始状态为空集。那么，从v出发到图上其余各顶点（终点）vi可能达到最短路径长度的初值为：Di=edgesLocate Vex(G,v)i vi
36、V,（2）选择vj，使得 Dj=MinDi|viV-S vj就是当前求得的一条从v出发的最短路径的终点。令 SSj（3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。如果 Dj+edgesjkDk 则修改Dk为Dk=Dj+edgesjk 重复操作（2）、（3）共n-1次。由此求得从v 到图上其余各顶点的最短路径是依路径长度递增的序列。,求下面带权有向图中V0到其它结点之间的最短路径,7.6 AOV网和拓扑排序,7.6.1 实现规则1 基本概念,AOV网(Activity on vertex network):所有的工程或者某种流程可以分为若干个小的工程或阶段，这些小的工程或阶段就称
37、为活动。若以图中的顶点来表示活动，有向边表示活动之间的优先关系，则这样活动在顶点上的有向图称为AOV网。,在AOV网中，若从顶点i到顶点j之间存在一条有向路径，称顶点i是顶点j的前驱，或者称顶点j是顶点i 的后继。若是图中的弧，则称顶点i是顶点j的直接前驱，顶点j 是顶点i的直接后驱。例如，我们把计算机专业的学生必须完成的课程看作活动，学习一门课程表示进行一项活动，有些基础课程，没有先修课程，而有些专业课程需要需要学完他的先修课程才能开始。我们可以把这些课程之间先修和后续的关系表示为一个AOV网,(a)计算机专业课程及其AOV网实例,类似的AOV网的例子还有很多，比如大家熟悉的计算机程序，任何
38、一个可执行程序也可以划分为若干个程序段（或若干语句），由这些程序段组成的流程图也是一个AOV网。,在AOV网中，有向边表示i活动应先于j活动开始，即i活动必须完成后，j活动才可以开始，并称i为j的直接前驱，j为i的直接后继。这种前驱与后继的关系有传递性，此外，任何活动i不能以它自己作为自己的前驱或后继，这叫做反自反性。从前驱和后继的传递性和反自反性来看，AOV网中不能出现有向回路(或称有向环)。在AOV网中如果出现了有向环，则意味着某项活动应以自己作为先决条件，这是不对的，工程将无法进行。对程序流程而言，将出现死循环。,因此，对给定的AOV网，应先判断它是否存在有向环。判断AOV网是否有有向环
39、的方法是对该AOV网进行拓扑排序，将AOV网中顶点排列成一个线性有序序列，若该线性序列中包含AOV网全部顶点，则AOV网无环，否则，AOV网中存在有向环，该AOV网所代表的工程是不可行的。,2 拓扑排序,下面将介绍怎样实现拓扑排序,实现步骤如下：（1）在AOV网中选一个入度为0的顶点且输出之；（2）从AOV网中删除此顶点及该顶点发出来的所有有向边；（3）重复（1）、（2）两步，直到AOV网中所有顶点都被输出或网中不存在入度为0的顶点。,从拓扑排序步骤可知，若在第3步中，网中所有顶点都被输出，则表明网中无有向环，拓扑排序成功。若仅输出部分顶点，网中已不存在入度为0的顶点，则表明网中有有向环，拓扑排序不成功。一个AOV网的拓扑序列是不唯一的。,7.7 AOE网和关键路径,
