1、基本术语基本术语 图是由图是由顶点的非空有穷集合顶点的非空有穷集合与与顶点之间关系顶点之间关系(边或弧边或弧)的集合的集合构成的结构构成的结构,通常表示为通常表示为 G=(V,E)其中其中,V 为顶点集合为顶点集合,E 为关系为关系(边或弧边或弧)的集合的集合.一一.图的定义图的定义(b)这条边依附于顶点这条边依附于顶点vi 和和vj。(vi,vj)vjvivjvi 关于一条边或弧的表示方法关于一条边或弧的表示方法:(1)用图形用图形:(2)用符号用符号:(3)用语言用语言:(a)顶点顶点vi 与与vj 是这条边的两个邻接点。是这条边的两个邻接点。v1v2v3v4 其中其中 V1=v1,v2,
2、v3,v4 E1=(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)G1=(V1,E1)v1v2v3v4其中其中 V2=v1,v2,v3,v4 E2=,G2=(V2,E2)无向图：无向图：有向图：有向图：与边有关的数据称为与边有关的数据称为权权,边上带权的图称为边上带权的图称为网络网络。二二.图的分类图的分类对于对于（vi,vj)E,必有必有（vj,vi)E，并且偶对中顶，并且偶对中顶点的前后顺序无关。点的前后顺序无关。若 E是顶点的有序偶对。是顶点的有序偶对。网网(络络)：v1v2v3v4v1v2v3v4v1v2v3v4104178 1.顶点的度顶
3、点的度对于有向图而言对于有向图而言,有有:顶点的顶点的出度出度:以顶点以顶点vi 为出发点的边的数目为出发点的边的数目,记为记为OD(vi).顶点的顶点的入度入度:以顶点以顶点vi 为终止点的边的数目为终止点的边的数目,记为记为ID(vi).TD(vi)=OD(vi)+ID(vi)三三.名词术语名词术语依附于顶点依附于顶点vi的边的数目的边的数目,记为记为TD(vi).v1v3v4v1v2v3v4v2 边的数目达到最大的图称为完全图边的数目达到最大的图称为完全图.边的数目达边的数目达到或接近最大的图称为稠密图到或接近最大的图称为稠密图,否则否则,称为稀疏图称为稀疏图.具有具有n个顶点的有向图最
4、多有个顶点的有向图最多有n(n-1)条边条边.具有具有n个顶点的无向图最多有个顶点的无向图最多有n(n-1)/2 条边条边.对于具有对于具有n个顶点个顶点,e条边的图条边的图,有有 2e=TD(vi)ni=1结论结论1结论结论2结论结论3 2.路径路径DCEBAP(A,E):A,B,E A,C,D,E 出发点与终止点相同的路径称为回路或环；顶点序列中出发点与终止点相同的路径称为回路或环；顶点序列中顶点不重复出现的路径称为简单路径。不带权的图的路径长顶点不重复出现的路径称为简单路径。不带权的图的路径长度是指路径上所经过的边的数目，带权的图的路径长度是指度是指路径上所经过的边的数目，带权的图的路径
5、长度是指路径上经过的边上的权值之和。路径上经过的边上的权值之和。顶点顶点vx到到vy之间有路径之间有路径P(vx,vy)的充分必要条件为的充分必要条件为:存存在顶点序列在顶点序列 vx,vi1,vi2,vim,vy,并且序列中相邻两个顶并且序列中相邻两个顶点构造的顶点偶对分别为图中的一条边。点构造的顶点偶对分别为图中的一条边。3.子图子图 v1v2v3v4 对于图对于图G=(V,E)与与 G=(V,E),若有若有V V,E E,则称则称G 为为G的一个子图的一个子图.v1v2v3v4v1v2 4.图的连通图的连通 无向图中顶点无向图中顶点vi 到到vj 有路径有路径,则称顶点则称顶点vi 与与
6、vj 是连通的。是连通的。若无向图中任意两个顶点都连通若无向图中任意两个顶点都连通,则称该无向图是连则称该无向图是连通的。通的。若有向图中顶点若有向图中顶点vi 到到vj 有路径有路径,并且顶点并且顶点vj 到到vi 也有路也有路径径,则称顶点则称顶点vi 与与vj 是连通的。是连通的。若有向图中任意两个顶点都连通若有向图中任意两个顶点都连通,则称该有向图是强则称该有向图是强连通的。连通的。(1)无向图的连通无向图的连通(2)有向图的连通有向图的连通 5.生成树生成树 包含具有包含具有n 个顶点的连通图个顶点的连通图G 的全部的全部n 个顶点个顶点,仅包仅包含其含其n-1条边的连通子图称为条边
7、的连通子图称为G 的一个生成树。的一个生成树。v1v3v4v2v1v3v4v2v1v3v4v2v1v3v4v2v1v3v4v2对于一个图对于一个图,需要存储的信息应该包括需要存储的信息应该包括:(1)所有顶点的数据信息；所有顶点的数据信息；(2)顶点之间关系顶点之间关系(边或弧边或弧)的信息的信息;(3)权的信息。权的信息。图的存储结构图的存储结构一一.邻接矩阵存储方法邻接矩阵存储方法1.定义一个一维数组定义一个一维数组VERTEX1:n存放图中所有顶点存放图中所有顶点 的数据信息的数据信息.2.定义一个二维数组定义一个二维数组A1:n,1:n存放图中所有顶点之存放图中所有顶点之 间关系的信息
8、间关系的信息(该数组被称为邻接矩阵该数组被称为邻接矩阵),),有有 1 当顶点当顶点vi到顶点到顶点vj有边时有边时Ai j=0 当顶点当顶点vi到顶点到顶点vj无边时无边时对于带权的图对于带权的图,有有 wij 当顶点当顶点vi到顶点到顶点vj有边有边,且边的权为且边的权为wij Ai j=当顶点当顶点vi到顶点到顶点vj无边时无边时oo0 1 1 11 0 1 11 1 0 11 1 1 0A1=v1v2v3v4Vertex11:4v1v2v3v4Vertex21:4 4 6 7 8 A2=v1v2v3v4v1v2v3104178邻接矩阵的类型定义如下邻接矩阵的类型定义如下:#define
9、 Vnum 图的顶点数图的顶点数enum adj0,1;typedef adj_adjmatrixvnumvnum adjmatrix;typedef struct VexType VexsVnum;/顶点的信息顶点的信息 adjmatrix arcs;/邻接矩阵邻接矩阵 graph;建立无向网邻接矩阵的算法如下建立无向网邻接矩阵的算法如下:void build-graph(graph&ga)for(i=0;in;i+)scanf(“%d”,ga.Vexsi);for(i=0;i+;in)for(j=0;j+;jn)ga.arcsij=maxint;for(k=0;k+;ke)/读入边读入边(
10、i,j)和权和权 scanf(“%d,%d,%d”,i,j,w);ga.arcsij=w;ga.arcsji=w;(1)无向图的邻接矩阵一定是一个对称矩阵无向图的邻接矩阵一定是一个对称矩阵;(2)不带权的有向图的邻接矩阵一般是一个稀疏矩阵不带权的有向图的邻接矩阵一般是一个稀疏矩阵;(3)无向图的邻接矩阵的第无向图的邻接矩阵的第i 行行(或第或第i 列列)非非0 或非或非 元素的个数为第元素的个数为第i 个顶点的度数个顶点的度数;(4)有向图的邻接矩阵的第有向图的邻接矩阵的第i 行非行非0或非或非 元素的个数为元素的个数为 第第i 个顶点的出度个顶点的出度;第第i 列非列非0或非或非 元素的个数
11、为第元素的个数为第 i 个顶点的入度。个顶点的入度。特点特点:二二.邻接表存储方法邻接表存储方法核心思想核心思想:对具有对具有n个顶点的图建立个顶点的图建立n个线性链表存储该图个线性链表存储该图.1.1.每一个链表前面设置一个头结点每一个链表前面设置一个头结点,用来存放一个顶点的用来存放一个顶点的 数据信息数据信息,称之为顶点结点称之为顶点结点.其结构为其结构为:vertexlink其中其中,vertex 域存放某个顶点的数据信息域存放某个顶点的数据信息;link 域存放某个链表中第一个结点的地址域存放某个链表中第一个结点的地址.2.2.第第i 个链表中的每一个链结点个链表中的每一个链结点(称
12、之为边结点称之为边结点)表示以第表示以第i 个顶点为出发点的一条边个顶点为出发点的一条边;边结点的构造为边结点的构造为nextweightadjvex其中其中,next 域为指针域域为指针域;weight 域为权值域域为权值域(若图不带权若图不带权,则无此域则无此域););adjvex 域存放以第域存放以第i 个顶点为出发点的一条边个顶点为出发点的一条边 的另一端点在头结点数组中的位置的另一端点在头结点数组中的位置.n个头结点之间为一数组结构个头结点之间为一数组结构.1234v1v2v3v447861233 (1)无向图的第无向图的第i 个链表中边结点的个数是第个链表中边结点的个数是第i 个顶
13、点度数个顶点度数.(2)有向图的第有向图的第i 个链表中边结点的个数是第个链表中边结点的个数是第i 个顶点的出度。个顶点的出度。特点特点:1234v1 v3v2v4234332411421v1v2v3v4v1v2v3v46478typedef struct edgenode int adjvex;/该边所指向的顶点的序号该边所指向的顶点的序号 float weight;/边上的权值边上的权值 struct edgenode*next;/指向下一条弧的指针指向下一条弧的指针*edgeptr;typedef struct VerType vertex;edgeptr link;vexnode;ty
14、pedef vexnode Adj_ListMAX_VERTEX_NUM;邻接表的类型定义邻接表的类型定义void build_adjlist(Adj_List ga)scanf(“%d,%d”,&n,&e);/读入顶点数，边数读入顶点数，边数e for(i=0;in;i+)/初始化邻接表初始化邻接表 gai.vertex=i;gai.link=NULL;for(k=0;ke;k+)scanf(“%d,%d”,&i,&j);/读入顶点对读入顶点对 p=new struct edgenode;p-adjvex=j;p-next=gai.link;gai.link=p;建立图的邻接表的算法：建立图
15、的邻接表的算法：1234v1v2v3v464127284关于逆邻接表关于逆邻接表v1v2v3v46478三三.十字链表存储方法十字链表存储方法 在用邻接表表示有向图时，有时需要同时使用邻接表和在用邻接表表示有向图时，有时需要同时使用邻接表和逆邻接表。用有向图的十字链表可把这两个结合起来表示。逆邻接表。用有向图的十字链表可把这两个结合起来表示。其中，其中，tail和和head 分别表示弧的尾顶点和头顶点；分别表示弧的尾顶点和头顶点；dut是弧的权值；是弧的权值；hlink 链接以链接以head为头的另一条弧；为头的另一条弧；tlink链接以链接以tail为尾的另一条弧。为尾的另一条弧。另外，设立
16、一个由另外，设立一个由n个表头结点构成的向量，每个表头结点存放一个顶个表头结点构成的向量，每个表头结点存放一个顶点，其结构也由上述五个域组成，点，其结构也由上述五个域组成，head域存放该顶域存放该顶点的入度；点的入度；tail域存放出度域存放出度;hlink链接以该顶点为头链接以该顶点为头的弧；的弧；tlink链接以该顶点为尾的弧。链接以该顶点为尾的弧。tailheadduttlinkhlink0 03 03 00 00 01 2 63 4 70 02 3 22 4 50 00 03 4 800121436781234123452 在邻接多重表中在邻接多重表中,每一条边只有一个边结点。边结点
17、的结每一条边只有一个边结点。边结点的结构如下：构如下：mark vertex1 vertex2 path1 path2 其中其中,mark 是记录是否处理过的标记是记录是否处理过的标记;vertex1和和vertex2是该边两顶点位置。是该边两顶点位置。path1域指向下一条依附于顶点域指向下一条依附于顶点vertex1的边；的边；path2 是指向下一条依附于顶点是指向下一条依附于顶点vertex2的边。的边。四四.邻接多重表存储方法邻接多重表存储方法 顶点结点的结构顶点结点的结构 存储顶点信息的结点表以顺序表方式组织存储顶点信息的结点表以顺序表方式组织,每一个顶每一个顶点结点有两个数据域：
18、其中，点结点有两个数据域：其中，data 存放与该顶点相关的信存放与该顶点相关的信息，息，Firstout 是指示第一条依附该顶点的边的指针。在邻是指示第一条依附该顶点的边的指针。在邻接多重表中接多重表中,所有依附于同一个顶点的边都链接在同一个所有依附于同一个顶点的边都链接在同一个单链表中。单链表中。data FirstoutA DEFCBABCDEF12345623461341245123534615例：例：已知一具有已知一具有n个顶点的无向图个顶点的无向图G采用邻接表存储方法采用邻接表存储方法,写一算法写一算法,删除图中数据信息为删除图中数据信息为item 的那个顶点的那个顶点.需要做的工
19、作需要做的工作:(1)寻找满足条件的那个顶点寻找满足条件的那个顶点;(2)从头结点数组中删除该顶点从头结点数组中删除该顶点;(3)删除与该顶点相关的边删除与该顶点相关的边;(4)修改有关的边结点的修改有关的边结点的adjvex 域的内容。域的内容。A DEFCBABCDEF12345623461341245123534615A DEFCBABDEFF123456235131243514void Del(g,n,item)k=0;for(i=1;i=n;i+)if(gi.vertex=item)k=i;break;if(k=0)return;p=gk.link;for(i=k+1;inext;d
20、elete q;for(i=1;iadjvex=k)if(gi.link=p)gi.linki=p-next;else q-next:=p-next;r=p;p=p-next;delete r;else if(p-adjvex k)p-adjvex=p-adjvex1;q=p;p=p-next;从图中某个指定的顶点出发从图中某个指定的顶点出发,按照某一原则对图中按照某一原则对图中 所有顶点都访问一次所有顶点都访问一次,得到一个由图中所有顶点组成的得到一个由图中所有顶点组成的 序列序列,这一过程称为图的遍历这一过程称为图的遍历.原则原则:从图中某个指定的顶点从图中某个指定的顶点v v出发出发,先
21、访问顶点先访问顶点v,v,然后从顶然后从顶点点v v未被访问过的一个邻接点未被访问过的一个邻接点W1W1出发出发,访问了顶点访问了顶点W1W1后，再从后，再从W1W1出发，访问和出发，访问和W1W1邻接且未被访问过的任意顶点邻接且未被访问过的任意顶点W2W2，然后从，然后从W2W2出发进行如上访问，重复，直到某一顶点所有邻接点都被出发进行如上访问，重复，直到某一顶点所有邻接点都被访问过时，接着退回到尚有邻接点未被访问过的顶点，再从访问过时，接着退回到尚有邻接点未被访问过的顶点，再从该顶点出发，重复上述过程，直到所有的被访问过的顶点的该顶点出发，重复上述过程，直到所有的被访问过的顶点的邻接点都已
22、被访问为止。邻接点都已被访问为止。一一.深度优先搜索深度优先搜索图的遍历图的遍历 为了标记某一时刻图中哪些顶点是否被访问为了标记某一时刻图中哪些顶点是否被访问,定定义一维数组义一维数组visited1:n,有有 1 表示表示第第i个顶点已经被访问个顶点已经被访问 visitedi=0 表示表示第第i个顶点还未被访问个顶点还未被访问 例如：用深度优先搜索法遍历下图例如：用深度优先搜索法遍历下图。12345678 2 3 1 4 5 1 6 7 2 8 2 8 3 8 3 8 4 5 6 7 V1V2V3V4V5V6V7V812345678void dfs(Adj_List g,int v0)/从
23、从v0出发，深度优先遍历图出发，深度优先遍历图g，g以邻接表为存储结构以邻接表为存储结构 printf(“%d”,v0);visitedv0=1;/标志标志v0已访问已访问 p=gv0.link;/找找v0的第一个邻接点的第一个邻接点 while(p!=NULL)if(visitedp-adjvex=0)dfs(g,p-adjvex);p=p-next;/回溯回溯找找v0的下一个邻接点的下一个邻接点 深度优先搜索的递归算法：深度优先搜索的递归算法：void dfs(Adj_List g,int v0)top=0;printf(“%d”,v0);visitedv0=1;/标志标志v0已访问已访问
24、 p=gv0.link;/找找v0的第一个邻接点的第一个邻接点 while(p!=NULL|top0)while(p!=NULL)if(visitedp-adjvex=1)p=p-next;/找找v0的下一个邻接点的下一个邻接点 else w=p-adjvex;printf(“%d”,w);visitedw=1;top+;Stop=p;p=gw.link;if(top 0)p=Stop;top-;p=p-next;深度优先搜索的非递归算法：深度优先搜索的非递归算法：分析上述过程分析上述过程,在遍历图时在遍历图时,对图中每个顶点至多调用对图中每个顶点至多调用一次一次dfsdfs过程，因为一旦某个
25、顶点被标志成已被访问，就过程，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构，当用二维数组表示邻接矩阵作图的存储采用的存储结构，当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为结构时，查找每个顶点的邻接点所需时间为O(nO(n2 2),),其中其中n n为为图中顶点数图中顶点数;而当以邻接表作图的存储结构时，查找邻接而当以邻接表作图的存储结构时，查找邻接点所需时间为点所
26、需时间为O(e)O(e)，其中，其中e e为无向图中的边数或有向图中为无向图中的边数或有向图中弧的个数。因此，当以邻接表作存储结构时，深度优先搜弧的个数。因此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为索遍历图的时间复杂度为O(n+e)O(n+e)。深度优先搜索遍历算法的复杂性分析：深度优先搜索遍历算法的复杂性分析：二二.广度优先搜索广度优先搜索原则原则:从图中某个指定的顶点从图中某个指定的顶点v v出发出发,先访问顶点先访问顶点v,v,然后依次然后依次访问顶点访问顶点v v的各个未被访问过的邻接点的各个未被访问过的邻接点W1,W2,W1,W2,Wt,Wt，然后，然后再依次访问再
27、依次访问W1,W2,W1,W2,Wt,Wt的所有的未被访问过的邻接点，的所有的未被访问过的邻接点，再从这些被访问的顶点出发，逐次进行访问，直到所有顶再从这些被访问的顶点出发，逐次进行访问，直到所有顶点都被访问到为止。点都被访问到为止。12345678例如右图：例如右图：从从V1V1出发，出发，V1V1访问了访问了;再访问与再访问与V1V1邻接的邻接的V2V2，V3;V3;然后再访问与然后再访问与V2V2邻接的邻接的V4V4、V5V5，与，与V3V3邻接的邻接的V6V6、V7;V7;再访问与再访问与V4V4邻接的邻接的V8V8则所有的顶点都则所有的顶点都被访问到了因此遍历结束。遍历的顺序被访问到
28、了因此遍历结束。遍历的顺序是：是：V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8 对于广度优先搜索的方法，我们用不着去记录所走过的对于广度优先搜索的方法，我们用不着去记录所走过的路径。我们只需记录与每一个顶点相邻接的所有顶点，而且当路径。我们只需记录与每一个顶点相邻接的所有顶点，而且当访问完这些顶点时，按照先记录先搜索的方式，对被记录的顶访问完这些顶点时，按照先记录先搜索的方式，对被记录的顶点进行广度优先搜索。（即若点进行广度优先搜索。（即若W1W1在在W2W2之前被访问，则之前被访问，则W1W1的邻接的邻接点也在点也在W2W2的邻接点之前被访问。）所以我们用一个队列的邻接点
29、之前被访问。）所以我们用一个队列Q Q来记录来记录这些顶点是比较方便的（依次存放被访问的结点）。这些顶点是比较方便的（依次存放被访问的结点）。和和dfsdfs算法一样，在这里也需要一个辅助函数算法一样，在这里也需要一个辅助函数VisitedWVisitedW来标志顶点是否被访问过。来标志顶点是否被访问过。我们仍假设图用邻接表来表示。我们仍假设图用邻接表来表示。算法算法：void bfs(Adj_List g,int v0)/g为图的邻接矩阵或邻接表，从为图的邻接矩阵或邻接表，从V0出发，用广度优先搜索法出发，用广度优先搜索法/遍历图，遍历图，visitedw为标志向量，其初值为为标志向量，其初
30、值为0 visitedv0=1;printf(“%d”,v0);f=0;r=0;p=gv0.link;do while(p!=NULL)v=p-adjvex;if(visitedv=0)qr=v;r+;printf(“%d”,v);visitedv=1;p=p-next;/找某一顶点的所有邻接点并进找某一顶点的所有邻接点并进队队 if(f!=r)/v出队出队 v=qf;f+;p=gv.link;while(p!=NULL)|(f!=r)可以用深度优先搜索或广度优先搜索算法来判断图是否连通。在对可以用深度优先搜索或广度优先搜索算法来判断图是否连通。在对无向图进行遍历时，对于连通图，仅需要一次搜索
31、过程，图中的顶点就无向图进行遍历时，对于连通图，仅需要一次搜索过程，图中的顶点就全部被访问。对于非连通图，则需要多次调用搜索过程，而每次调用得全部被访问。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰好为其各个连通分量中的顶点集。到的顶点访问序列恰好为其各个连通分量中的顶点集。三三.求图的连通分量求图的连通分量 int Count_Component(adj_list g,int n)int count;for(v=0;vn;v+)/*初始化初始化visited数组数组 visitedv=0;count=0;for(v=0;v V(T)=V(T)=1 1 做做n-1n-1
32、次次1)1)边边(1,2)(1,2)的权值最小，的权值最小，将将=V(T)=V(T)=1,21,2;weight(1,2)=16 weight(1,2)=161246532)2)边边(2,3)(2,3)的权值最小，的权值最小，将将=V(T)=V(T)=1,2,31,2,3;weight(2,3)=5(2,3)=53)3)边边(3,4)(3,4)的权值最小，的权值最小，将将=V(T)=V(T)=1,2,3,41,2,3,4;weight(3,4)=6(3,4)=6 165618192111143364)4)边边(2,6)(2,6)的权值最小，的权值最小，将将=V(T)=V(T)=1,2,3,4,
33、61,2,3,4,6;weight(2,6)=11(2,6)=115)5)边边(4,5)(4,5)的权值最小，的权值最小，将将=V(T)=V(T)=1,2,3,4,5,61,2,3,4,5,6;weight(4,5)=18(4,5)=18i=16Weight =561246531656181921111433612465316561811最短路径问题最短路径问题:一一.路径长度的定义路径长度的定义1.不带权的图不带权的图:路径上所经过的边的数目路径上所经过的边的数目。2.带权的图带权的图:路径上所经过的边上的权值之和路径上所经过的边上的权值之和.二二.问题的提出问题的提出三三.解决问题所需要确
34、定的数据结构解决问题所需要确定的数据结构1.1.图的存储图的存储:以以1n 分别代表分别代表n个顶点个顶点,采用邻接矩阵存采用邻接矩阵存 储该图储该图,有有 Wij 当顶点当顶点vi 到顶点到顶点vj 有边有边,且权为且权为Wij Ai,j=当顶点当顶点vi 到顶点到顶点vj j无边时无边时 0 当当vi=vj 时时 设出发顶点为设出发顶点为v(通常称为源点通常称为源点)。确定源点到其他各顶点的。确定源点到其他各顶点的最短路径，常应用于选择路线，架设电线等最短路径，常应用于选择路线，架设电线等.2.设置一个标志数组设置一个标志数组S1:n记录源点记录源点v 到图中哪些顶点的最短到图中哪些顶点的
35、最短 路径已经找到，有：路径已经找到，有：1 1 表示源点到顶点表示源点到顶点i 的最短路径已经找到的最短路径已经找到 Si=0 表示源点到顶点表示源点到顶点i 的最短路径尚未找到的最短路径尚未找到 初始时，初始时，Sv=1,Si=0 i=1,2,n i v3.设置数组设置数组dist1:n 分别记录源点分别记录源点v 到图中各顶点的最短路径到图中各顶点的最短路径的路径长度，的路径长度，其中，其中，disti记录源点到顶点记录源点到顶点i 的最短路径的的最短路径的长度；初始时，长度；初始时，dist数组的值为邻接矩阵第数组的值为邻接矩阵第v 行的行的n个元素值。个元素值。4.设置数组设置数组p
36、ath1:n 分别记录源点分别记录源点v 到图中各顶点的最短路到图中各顶点的最短路 径所经过的顶点序列，其中，径所经过的顶点序列，其中，pathi记录源点到顶点记录源点到顶点i 的的 路径，初始时，路径，初始时，pathi=v,i=1,2,3,n 013524455010201015152033530v0v0是源点是源点 最短路径最短路径v0v2 10v0v2 10v0v2v3 10+15=25v0v2v3 10+15=25v0v2v3v1 10+15+20v0v2v3v1 10+15+20v0v4 45v0v4 45v0v5 v0v5 无路可走无路可走 从以上可以发现每一条最短路径中间所经过
37、的顶点具有如从以上可以发现每一条最短路径中间所经过的顶点具有如下特点：下一条最短路径下特点：下一条最短路径(设其终点为设其终点为x)x)可能是可能是,或者或者v0,u,v,x，而，而u,u,v,v都是已求得的最短路径终点。都是已求得的最短路径终点。例例 假设假设S S为已求得的最短路径的终点的集合为已求得的最短路径的终点的集合(S(S初态为空集初态为空集)，则，则下一条长度次短的最短路径（设终点为下一条长度次短的最短路径（设终点为x x）：）：或者是弧或者是弧；或者是中间经过或者是中间经过S S集合中顶点，最后到达顶点集合中顶点，最后到达顶点x x的路径。的路径。Dijkstra算法思想：算法
38、思想：四四.算法算法(用自然语言表达用自然语言表达)b)b)设设S S为已找到从为已找到从v v0 0出发的最短路径的终点的集合出发的最短路径的终点的集合,它的初它的初态为源点（态为源点（v v0 0)。c)c)设从设从v0v0出发到出发到G G中其余各顶点中其余各顶点(终点终点)v)vi i的最短路径长度为：的最短路径长度为：初态初态disti=costvdisti=costv0 0,v,vi i V Vi iV(G)V(G)选择选择u u，使，使distu=Mindistu=Mindisti|vdisti|vi i不属于不属于S,vS,vi iV(G)V(G)（则（则u u为目前求得的一条
39、从为目前求得的一条从v v0 0出发的最短路径的终点）出发的最短路径的终点）令令S=S S=S u u（u u进入进入s s）设设costcost为带权的邻接矩阵为带权的邻接矩阵 a)cost=a)cost=上的权值上的权值 (i,j(i,j之间有弧之间有弧)(i,j (i,j之间无弧之间无弧)修改所有不在修改所有不在S S的终点的最短路径的长度，若的终点的最短路径的长度，若 distu+costu,idistidistu+costu,idisti，则修改则修改distidisti为为disti=distu+costu,idisti=distu+costu,i同时修改相应同时修改相应的路径的路
40、径.重复操作共重复操作共n-1n-1次，由此求得从次，由此求得从v v0 0到到G G中其余各顶中其余各顶点的最短路径是依路径长度递增的序列。点的最短路径是依路径长度递增的序列。void shortpath(cost,v0)/*求从源点求从源点v0到其它各顶点的最短路径到其它各顶点的最短路径,cost为有向图的带权为有向图的带权邻接矩阵，邻接矩阵，v0为其中某个顶点的编号；为其中某个顶点的编号；disti为当前找到的从为当前找到的从v0到到i的最短路径长度；的最短路径长度；pathi为相应的路径；为相应的路径；max为计算机内允许的最为计算机内允许的最大值大值*/for(i=0;in;i+)d
41、isti=costv0i;if(distimax)pathi=v0+i;/表示集合，表示集合，+表示两个集合相并表示两个集合相并 else pathi=;/表示为空集表示为空集 /建立建立dist及及path的初态的初态 s=char(v0);num=0;/s为已找到最短路径的终点的集合为已找到最短路径的终点的集合 while(numn-1)wm=max;u=v0;for(i=0;in;i+)/选选disti的最小值的最小值 if(!(i in s)&distiwm)/若若i不属于不属于s且且distiwm u=i;wm=disti;/按按disti的最小值选取了的最小值选取了u s=s+u;
42、/将将u加入最短路径的终点集合加入最短路径的终点集合s for(i=0;in;i+)/修改修改dist和和past的值的值 if(!(i in s)&distu+costuidisti)/若若i不属于不属于s disti=distu+costui;pathi=pathu+i;num+;算法执行时间：第一个算法执行时间：第一个FOR循环是循环是O(n)，接下来循环共进，接下来循环共进行行n-1次，每一次执行时间是次，每一次执行时间是O(n)，所以总的时间为，所以总的时间为O(n2)。Floyed算法思想：算法思想：从从i i 到到j j的路径上每次增加一个结点的路径上每次增加一个结点k k，看这
43、个增加了一，看这个增加了一个结点个结点k k的新路径的长度是否比原来的路径长度小，若小的新路径的长度是否比原来的路径长度小，若小,则则以新路径代之以新路径代之,否则保持原路径。否则保持原路径。A(k)ij=minA(k-1)ij,A(k-1)ik+A(k-1)kj(1kn)算法计算公式：算法计算公式：其中其中:A(k)ij表示顶点表示顶点i,j之间的中间点的序号不大于之间的中间点的序号不大于k的最短距离的最短距离;由于由于G中顶点编号不大于中顶点编号不大于n，所以最后到了，所以最后到了Anij就代表就代表i到到j的最短路径之长。的最短路径之长。算法描述：算法描述：void all_path(c
44、ost)for(i=1;i=n;i+)for(j=1;j=n;j+)aij=costij;if(i!=j)&(aijmax)pathij=i+j;for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(ai,k+ak,jai,j)aij=aik+akj;pathij=pathik+pathkj;cost=cost=0 4 110 4 116 0 26 0 23 03 0cost:cost:带权邻接矩阵带权邻接矩阵A A：最短路径长度：最短路径长度P P：相应的路径：相应的路径 例：例：641132ABC321初态初态K=0K=0时，时，A A(0)(0)
45、1 2 31 2 3 1 1 2 2 3 30 4 110 4 116 0 26 0 23 03 0 AB AC AB AC PathPath(0)(0)1 2 31 2 3 1 1 2 2 3 3BA BCBA BCCA CA K=1K=1时，时，A A(1)(1)1 2 3 Path 1 2 3 Path(1)(1)1 2 3 1 2 3 1 0 4 11 1 AB AC 1 0 4 11 1 AB AC 2 6 0 2 2 BA BC 2 6 0 2 2 BA BC 3 3 3 3 7 7 0 3 CA 0 3 CA CABCABK=2K=2时，时，A A(2)(2)1 2 3 Path
46、 1 2 3 Path(2)(2)1 2 3 1 2 3 1 0 4 1 0 4 6 6 1 AB 1 AB ABCABC 2 6 0 2 2 BA BC 2 6 0 2 2 BA BC 3 3 3 3 7 7 0 3 CA 0 3 CA CABCABK=3K=3时，时，A A(3)(3)1 2 3 Path 1 2 3 Path(3)(3)1 2 3 1 2 3 1 0 4 1 0 4 6 6 1 AB 1 AB ABCABC 2 2 5 5 0 2 2 0 2 2 BCABCA BC BC 3 3 3 3 7 7 0 3 CA 0 3 CA CABCABAOV网与拓扑排序网与拓扑排序一一.
47、AOV网举例：网举例：验收验收筹备筹备招标招标备料备料进驻进驻工地工地测量测量挖地基挖地基浇注浇注水泥水泥搭架搭架 子子例例1程序程序语言语言数据数据结构结构离散离散数学数学软件软件工程工程操作操作系统系统编译编译原理原理数据库数据库计算机计算机组成组成汇编汇编网络网络数字数字逻辑逻辑计算机计算机导论导论例例2二二.AOV网的定义网的定义 以顶点表示活动，以有向边表示活动之间的优先以顶点表示活动，以有向边表示活动之间的优先关系的有向图称为关系的有向图称为AOV网。网。在在AOV网中，若顶点网中，若顶点i 到顶点到顶点j 之间有有向路径，则称之间有有向路径，则称顶点顶点i 为顶点为顶点j 的前驱
48、，顶点的前驱，顶点j 为顶点为顶点i的后继；若顶点的后继；若顶点i 到顶到顶点点j 之间为一条有向边，则称顶点之间为一条有向边，则称顶点i 为顶点为顶点j的直接前驱，顶的直接前驱，顶点点j 为顶点为顶点i 的直接后继。的直接后继。三三.拓扑排序拓扑排序 检查检查AOV网是否存在回路的方法是对网是否存在回路的方法是对AOV网进行拓扑排网进行拓扑排序，构造一个序列，使得该序列满足条件：序，构造一个序列，使得该序列满足条件：1.若在若在AOV网中，顶点网中，顶点i 优先于顶点优先于顶点j,则在该序列中也则在该序列中也是顶点是顶点i 优先于顶点优先于顶点j。2.若在若在AOV网中，顶点网中，顶点i 与
49、顶点与顶点j之间不存在优先关系之间不存在优先关系,则在该序列中建立它们的优先关系，即顶点则在该序列中建立它们的优先关系，即顶点i优先于顶点优先于顶点j，或，或顶点顶点j 优先于顶点优先于顶点i。3.若能够构造出拓扑序列，则拓扑序列包含若能够构造出拓扑序列，则拓扑序列包含AOV网的网的全部顶点。全部顶点。四四.拓扑排序方法拓扑排序方法 1.从从AOV网中任选择一个没有前驱网中任选择一个没有前驱(入度为入度为0)的顶点的顶点；2.从从AOV网中去掉该顶点以及以该顶点为出发点的所有边；网中去掉该顶点以及以该顶点为出发点的所有边；3.重复上述过程，直到网中的所有顶点都被去掉重复上述过程，直到网中的所有
50、顶点都被去掉,或者网中或者网中 还有顶点，但不存在入度为还有顶点，但不存在入度为0 的顶点。的顶点。五五.算法思想算法思想 建立一个栈（这个栈存放入度为建立一个栈（这个栈存放入度为0 0的结点）检查邻接表，将的结点）检查邻接表，将所有入度为零的顶点送栈，随后输出入度为所有入度为零的顶点送栈，随后输出入度为0 0的顶点。的顶点。VjVj输出时，输出时，将将VjVj的直接后继的直接后继Vk(k=1,2,Vk(k=1,2,)的入度减的入度减1 1，并将入度减到零的，并将入度减到零的顶点进栈。当栈为空时，则检查一下是否输出了有向图的全部顶点进栈。当栈为空时，则检查一下是否输出了有向图的全部顶点（顶点（
