数据结构课件图

1、第六章第六章 图图 基本术语基本术语 图的存储结构图的存储结构 图的遍历图的遍历north china electric power university 最小生成树和最短路径问题最小生成树和最短路径问题 aov aov网与拓扑排序网与拓扑排序 aoe aoe网与关键路径网与关键路径基本术语基本术语north china electric power university 图是由图是由顶点的非空有穷集合顶点的非空有穷集合与与顶点之间关系顶点之间关系( (边或弧边或弧) )的集合的集合构成的结构构成的结构, , 通常表示为通常表示为 g = ( v, e)其中其中, , v 为顶点集合为顶点集合

2、, , e 为关系为关系( (边或弧边或弧) )的集合的集合. .一一. .图的定义图的定义华电华电计算机系计算机系north china electric power university( (b) ). 这条边依附于顶点这条边依附于顶点vi 和和vj。 (vi, vj)vjvivjvivjvivjvi 关于一条边或弧的表示方法关于一条边或弧的表示方法:( (a) ). 顶点顶点vi 与与vj 是这条边的两个邻接点。是这条边的两个邻接点。( (1) ). 用图形用图形: :(2). 用符号用符号:( (3) ). 用语言用语言: :华电计算机系华电计算机系north china electr

3、ic power university华电华电计算机系计算机系v1v2v3v4 其中其中 v1 = v1, v2, 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) north china electric power university 无向图：无向图： 有向图：有向图：与边有关的数据称为与边有关的数据称为权权, ,边上带权的图称为边上带权的图称为网络网络。二二. .图的分类图

4、的分类对于对于（vi,vj) e, ,必有必有（vj,vi) e，并且偶对中顶，并且偶对中顶点的前后顺序无关。点的前后顺序无关。若 e是顶点的有序偶对。是顶点的有序偶对。华电华电计算机系计算机系 网网( (络络) )：v1v2v3v4v1v2v3v4v1v2v3v4104178north china electric power university 1. .顶点的度顶点的度对于有向图而言对于有向图而言, 有有: 顶点的顶点的出度出度: 以顶点以顶点vi 为出发点的边的数目为出发点的边的数目,记为记为od(vi). 顶点的顶点的入度入度: 以顶点以顶点vi 为终止点的边的数目为终止点的边的数目

5、,记为记为id(vi). td(vi) = od(vi) + id(vi)三三. .名词术语名词术语依附于顶点依附于顶点vi的边的数目的边的数目, ,记为记为td(vi).华电华电计算机系计算机系v1v3v4v1v2v3v4v2north china electric power university 边的数目达到最大的图称为完全图边的数目达到最大的图称为完全图. . 边的数目达边的数目达到或接近最大的图称为稠密图到或接近最大的图称为稠密图, ,否则否则, ,称为稀疏图称为稀疏图. . 具有具有n个顶点的有向图最多有个顶点的有向图最多有n(n-1) 条边条边. . 具有具有n个顶点的无向图最多

6、有个顶点的无向图最多有n(n-1)/2 条边条边. . 对于具有对于具有n个顶点个顶点, ,e条边的图条边的图, ,有有 2e = td(vi)ni=1结论结论1结论结论2结论结论3华电华电计算机系计算机系north china electric power university 2. . 路径路径dcebap(a, e): a, b, e a, c, d, e 出发点与终止点相同的路径称为回路或环；顶点序列中出发点与终止点相同的路径称为回路或环；顶点序列中顶点不重复出现的路径称为简单路径。不带权的图的路径长顶点不重复出现的路径称为简单路径。不带权的图的路径长度是指路径上所经过的边的数目，带权

7、的图的路径长度是指度是指路径上所经过的边的数目，带权的图的路径长度是指路径上经过的边上的权值之和。路径上经过的边上的权值之和。 顶点顶点vx到到vy之间有路径之间有路径p(vx, vy)的充分必要条件为的充分必要条件为: : 存存在顶点序列在顶点序列 vx, vi1, vi2, , vim, vy, , 并且序列中相邻两个顶并且序列中相邻两个顶点构造的顶点偶对分别为图中的一条边。点构造的顶点偶对分别为图中的一条边。华电华电计算机系计算机系north china electric power university 3. .子图子图 v1v2v3v4 对于图对于图g=(v,e) 与与 g =(v

8、,e ), , 若有若有v v, e e, ,则称则称g 为为g的一个子图的一个子图. .华电华电计算机系计算机系v1v2v3v4v1v2north china electric power university 4. .图的连通图的连通 无向图中顶点无向图中顶点vi 到到vj 有路径有路径, ,则称顶点则称顶点vi 与与vj 是连通的。是连通的。 若无向图中任意两个顶点都连通若无向图中任意两个顶点都连通, , 则称该无向图是连则称该无向图是连通的。通的。 若有向图中顶点若有向图中顶点vi 到到vj 有路径有路径, ,并且顶点并且顶点vj 到到vi 也有路也有路径径, ,则称顶点则称顶点vi

9、与与vj 是连通的。是连通的。 若有向图中任意两个顶点都连通若有向图中任意两个顶点都连通, ,则称该有向图是强则称该有向图是强连通的。连通的。(1). .无向图的连通无向图的连通(2). .有向图的连通有向图的连通华电华电计算机系计算机系north china electric power university 5. .生成树生成树华电华电计算机系计算机系 包含具有包含具有n 个顶点的连通图个顶点的连通图g 的全部的全部n 个顶点个顶点, ,仅包仅包含其含其n-1条边的连通子图称为条边的连通子图称为g 的一个生成树。的一个生成树。v1v3v4v2v1v3v4v2v1v3v4v2v1v3v4v2

10、v1v3v4v2north china electric power university华电华电计算机系计算机系对于一个图对于一个图, ,需要存储的信息应该包括需要存储的信息应该包括: :( (1).).所有顶点的数据信息；所有顶点的数据信息；( (2).).顶点之间关系顶点之间关系( (边或弧边或弧) )的信息的信息; ;( (3).).权的信息。权的信息。图的存储结构图的存储结构north china electric power university一一. .邻接矩阵存储方法邻接矩阵存储方法 核心思想核心思想: : 采用两个数组存储一个图采用两个数组存储一个图. .1. . 定义一个一

11、维数组定义一个一维数组vertex1:n存放图中所有顶点存放图中所有顶点 的数据信息的数据信息. .2. . 定义一个二维数组定义一个二维数组a1:n,1:n存放图中所有顶点之存放图中所有顶点之 间关系的信息间关系的信息( (该数组被称为邻接矩阵该数组被称为邻接矩阵),),有有 1 当顶点当顶点vi到顶点到顶点vj有边时有边时ai, j= 0 当顶点当顶点vi到顶点到顶点vj无边时无边时对于带权的图对于带权的图, , 有有 wij 当顶点当顶点vi到顶点到顶点vj有边有边, ,且边的权为且边的权为wij ai, j= = 当顶点当顶点vi到顶点到顶点vj无边时无边时oo数组存储方法数组存储方法

12、华电华电计算机系计算机系north china electric power university0 1 1 11 0 1 11 1 0 11 1 1 0a1 =v1v2v3v4vertex11:4v1v2v3v4vertex21:4 4 6 7 8 a2 =华电华电计算机系计算机系v1v2v3v4v1v2v3v4104178north china electric power university( (1).).无向图的邻接矩阵一定是一个对称矩阵无向图的邻接矩阵一定是一个对称矩阵.( (2).).不带权的有向图的邻接矩阵一般是一个稀疏矩阵。不带权的有向图的邻接矩阵一般是一个稀疏矩阵。( (3

13、).).无向图的邻接矩阵的第无向图的邻接矩阵的第i 行行( (或第或第i 列列) )非非0 或非或非 元素的个数为第元素的个数为第i 个顶点的度数个顶点的度数. .( (4).).有向图的邻接矩阵的第有向图的邻接矩阵的第i 行非行非0或非或非 元素的个数为元素的个数为 第第i 个顶点的出度个顶点的出度; ;第第i 列非列非0或非或非 元素的个数为第元素的个数为第 i 个顶点的入度。个顶点的入度。特点特点: :华电华电计算机系计算机系north china electric power university二二. .邻接表存储方法邻接表存储方法核心思想核心思想: :对具有对具有n个顶点的图建立个

14、顶点的图建立n个线性链表存储该图个线性链表存储该图. .1. 1. 每一个链表前面设置一个头结点每一个链表前面设置一个头结点, ,用来存放一个顶点的用来存放一个顶点的 数据信息数据信息, ,称之为顶点结点称之为顶点结点. .其结构为其结构为: :vertexlink其中其中, ,vertex 域存放某个顶点的数据信息域存放某个顶点的数据信息; ; link 域存放某个链表中第一个结点的地址域存放某个链表中第一个结点的地址. .2. 2. 第第i 个链表中的每一个链结点个链表中的每一个链结点( (称之为边结点称之为边结点) )表示以第表示以第i 个顶点为出发点的一条边个顶点为出发点的一条边; ;

15、边结点的构造为边结点的构造为nextweightadjvex其中其中, ,next 域为指针域域为指针域; ; weight 域为权值域域为权值域( (若图不带权若图不带权, ,则无此域则无此域);); adjvex 域存放以第域存放以第i 个顶点为出发点的一条边个顶点为出发点的一条边 的另一端点在头结点数组中的位置的另一端点在头结点数组中的位置. .n个头结点之间为一数组结构个头结点之间为一数组结构. .华电华电计算机系计算机系north china electric power university1234v1v2v3v447861233 ( (1).).无向图的第无向图的第i 个链表中边

16、结点个链表中边结点 的个数是第的个数是第i 个顶点度数个顶点度数. .( (2).).有向图的第有向图的第i 个链表中边结点个链表中边结点 的个数是第的个数是第i 个顶点的出度。个顶点的出度。特特点点1234v1 v3v2v4234332411421华电计算机系华电计算机系v1v2v3v4v1v2v3v46478type edgeptrtype edgeptr= = edgenode; edgenode=record adjvex:1.n; weight:real; next:edgeptr; end; vexnode=record vertex:vertype; link:edgeptr;

17、end; adj_list=array1.n of vexnode; 邻接表的类型定义邻接表的类型定义north china electric power universitynorth china electric power university1234v1v2v3v464127284 三三. .有向图的十字链表存储方法有向图的十字链表存储方法 ( (略略) ) 四四. .无向图的多重邻接表存储方法无向图的多重邻接表存储方法 ( (略略) )关于逆邻接表关于逆邻接表华电华电计算机系计算机系v1v2v3v46478north china electric power universitya

18、defcbabcdef12345623461341245123534615例例 已知一具有已知一具有n个顶点的无向图个顶点的无向图g采用邻接表存储方法采用邻接表存储方法, 写一算法写一算法, 删除图中数据信息为删除图中数据信息为item 的那个顶点的那个顶点.需要做的工作需要做的工作: : ( (1). ). 寻找满足条件的那个顶点寻找满足条件的那个顶点; ;( (2). ). 从头结点数组中删除该顶点从头结点数组中删除该顶点; ;( (3). ). 删除与该顶点相关的边删除与该顶点相关的边; ;( (4). ). 修改有关的边结点的修改有关的边结点的adjvex 域的内容。域的内容。华电计算

19、机系华电计算机系north china electric power university华电华电计算机系计算机系a defcbabcdef12345623461341245123534615a defcbabdeff123456235131243514north china electric power universityprocedure del( g, n, item );begin k:=0; for i:=1 to n do if(gi.vertex=item)then k:=i; exit; if (k=0) then return; p:=gk.link; for i:=k+1

20、 to n do gi-1.vertex:=gi.vertex; gi-1.link:=gi.link; n:=n1; / 顶点的个数减顶点的个数减1 1 / while(pnil) do q:=p; p:=p .next; dispose(q); 华电计算机系华电计算机系 for i:=1 to n do p:=gi.link; while (pnil）do if(p .adjvex=k) then if(gi.link=p) then gi.link:=p .next else q .next:=p .next; r:=p;p:=p .next; dispose(r); else if (

21、p .adjvexk) then p .adjvex:= p .adjvex1; q:=p; p:=p .next; end; 北航北航计算机系计算机系north china electric power university 从图中某个指定的顶点出发从图中某个指定的顶点出发, , 按照某一原则对图中按照某一原则对图中 所有顶点都访问一次所有顶点都访问一次, , 得到一个由图中所有顶点组成的得到一个由图中所有顶点组成的 序列序列, , 这一过程称为图的遍历这一过程称为图的遍历. .原则原则: : 从图中某个指定的顶点从图中某个指定的顶点v出发出发, ,先访问顶点先访问顶点v, ,然后从顶然后从

22、顶点点v 未被访问过的一个邻接点出发未被访问过的一个邻接点出发, , 继续进行深度优先遍继续进行深度优先遍历历, ,直到图中与直到图中与v 相通的所有顶点都被访问相通的所有顶点都被访问; ;若此时图中还若此时图中还有未被访问过的顶点有未被访问过的顶点, , 则从另一个未被访问过的顶点出发则从另一个未被访问过的顶点出发重复上述过程重复上述过程, ,直到遍历全图直到遍历全图. .一一. . 深度优先搜索深度优先搜索华电华电计算机系计算机系图的遍历图的遍历 为了标记某一时刻图中哪些顶点是否被访问为了标记某一时刻图中哪些顶点是否被访问, ,定定义一维数组义一维数组visited1:n, , 有有 1

23、表示表示第第i个顶点已经被访问个顶点已经被访问 visitedi = = 0 表示表示第第i个顶点还未被访问个顶点还未被访问 north china electric power universitynorth china electric power university二二. . 广度优先搜索广度优先搜索华电华电计算机系计算机系原则原则: : 从图中某个指定的顶点从图中某个指定的顶点v出发出发, ,先访问顶点先访问顶点v, ,然后依次然后依次访问顶点访问顶点v的各个未被访问过的邻接点的各个未被访问过的邻接点, ,然后又从这些邻接然后又从这些邻接点出发点出发, , 按照同样的规则访问它们的那

24、些未被访问过的邻按照同样的规则访问它们的那些未被访问过的邻接点，如此下去，直到图中与接点，如此下去，直到图中与v 相通的所有顶点都被访问相通的所有顶点都被访问; ; 若此时图中还有未被访问过的顶点若此时图中还有未被访问过的顶点, , 则从另一个未被访问则从另一个未被访问过的顶点出发重复上述过程过的顶点出发重复上述过程, , 直到遍历全图直到遍历全图. .north china electric power university 可以用深度优先搜索或广度优先搜索算法来判断图可以用深度优先搜索或广度优先搜索算法来判断图是否连通。在对无向图进行遍历时，对于连通图，仅需是否连通。在对无向图进行遍历时，

25、对于连通图，仅需要一次搜索过程，图中的顶点就全部被访问。对于非连要一次搜索过程，图中的顶点就全部被访问。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰好为其各个连通分量中的顶点集。点访问序列恰好为其各个连通分量中的顶点集。三三. . 求图的连通分量求图的连通分量算法算法: : procedure component(var g); begin for i:=1 to vnum do visitedi:=0;count:=0; for i:=1 to vnum do if visitedi=0 then count:=coun

26、t+1;dfs(g,i); end;north china electric power university最小生成树和最短路径问题最小生成树和最短路径问题 带权连通图中带权连通图中, ,总的权值之和最小的带权生成树总的权值之和最小的带权生成树 为最小生成树为最小生成树. . 最小生成树也称最小代价生成树最小生成树也称最小代价生成树, ,或或 最小花费生成树最小花费生成树. .构造网的最小生成树的依据：构造网的最小生成树的依据：1.1. 在网中选择在网中选择n-1n-1条边，连接网条边，连接网 的的n n个顶点；个顶点；2. 2. 尽可能选取权值为最小的边。尽可能选取权值为最小的边。最小生成

27、树的概念：最小生成树的概念：最小生成树问题最小生成树问题v4v2v6v5v3v116115691814192220最小生成树的权值最小生成树的权值 = 56kruskal算法：算法： 1.1.设设t t的初态为空集；的初态为空集； 2.2.当当t t中边数小于中边数小于n-1n-1时做下列工作时做下列工作 从从e e中选取权值为最小的边中选取权值为最小的边(v,w)(v,w)，并删除之；，并删除之； 若若(v,w)(v,w)不和不和 t t 中的边一起构成回路，则将边中的边一起构成回路，则将边(v,w)(v,w)加入到加入到t t中去。中去。1246536536215465124653 t t

28、为空为空north china electric power university124653选权值最小的边选权值最小的边(1,3)(1,3) 从从e e中将其删去中将其删去11246531选选e e中最小的边中最小的边(4,6)(4,6)从从e e中将其删去中将其删去212465312从从e e中选最小的边中选最小的边(2,5)(2,5)从从e e中将其删去中将其删去3124653123从从e e中选最小的边中选最小的边(3,6)(3,6)从从e e中将其删去中将其删去4north china electric power university从从e e中选最小的边中选最小的边(3,4)(3

29、,4)，但加入，但加入t t后会使后会使t t中出现回路，所以边中出现回路，所以边(3,4)(3,4)不可取，把边不可取，把边(3,4)(3,4)从从e e中删除。再中删除。再看看(1,4)(1,4)同样会使同样会使t t构成回路，仍不构成回路，仍不可取，从可取，从e e中删去中删去(1,4)(1,4)，选，选(2,3)(2,3)，从从e e中删去中删去(2,3),(2,3),最后已够最后已够5 5条边了，条边了，这样生成树就是最小生成树。最小这样生成树就是最小生成树。最小生成树可能不唯一，但权的总数相生成树可能不唯一，但权的总数相同。同。24653123415 算法的思想明确、也很简单，但具

30、体实现时比较困难，需算法的思想明确、也很简单，但具体实现时比较困难，需要解决一些具体的问题，譬如如何使所选的新边没有和已选的边要解决一些具体的问题，譬如如何使所选的新边没有和已选的边构成回路。构成回路。算法讨论：算法讨论：north china electric power universityprimprim算法：算法： 1.1.设设v(t)v(t)的初态为空集的初态为空集(v(t)(v(t)为落在生成树上的顶点集合为落在生成树上的顶点集合);); 2. 2.在连通图上任选一顶点加入到在连通图上任选一顶点加入到v(t)v(t)集合中去；集合中去； 3.3.将下列步骤重复将下列步骤重复n-1n

31、-1次：次： 在在i i属于属于v(t)v(t)，j j不属于不属于v(t)v(t)的边中，选权值最小的边的边中，选权值最小的边 ( (i,j)i,j)； 将顶点将顶点j j加入到加入到v(t)v(t)中去；中去； 输出输出i,ji,j及及w wijij。north china electric power university例：例：初态初态v(t)=v(t)= 选选顶点顶点=v(t)=v(t)=1 1 做做n-1n-1次次1)1)边边(1,2)(1,2)的权值最小，的权值最小，将将=v(t)=v(t)=1,21,2; ; write(1,2) write(1,2) weight 16 we

32、ight 161246532)2)边边(2,3)(2,3)的权值最小，的权值最小， 将将=v(t)=v(t)=1,2,31,2,3; ; write(2,3) write(2,3) weight 5weight 53)3)边边(3,4)(3,4)的权值最小，的权值最小， 将将=v(t)=v(t)=1,2,3,41,2,3,4; ; write(3,4) write(3,4) weight 6weight 616561819211114336north china electric power university4)4)边边(2,6)(2,6)的权值最小，的权值最小， 将将=v(t)=v(t)

33、=1,2,3,4,61,2,3,4,6; ; write(2,6) weight 11 write(2,6) weight 115)5)边边(4,5)(4,5)的权值最小，的权值最小， 将将=v(t)= v(t)= 1,2,3,4,5,61,2,3,4,5,6; ; write(4,5) weight 18 write(4,5) weight 18i=16weight = 561246531656181921111433612465316561811north china electric power university最短路径问题最短路径问题一一. .路径长度的定义路径长度的定义1. .

34、不带权的图不带权的图: : 路径上所经过的边的数目路径上所经过的边的数目。2. . 带权的图带权的图: : 路径上所经过的边上的权值之和路径上所经过的边上的权值之和. .二二. .问题的提出问题的提出三三. .解决问题所需要确定的数据结构解决问题所需要确定的数据结构1. 1. 图的存储图的存储: :以以1n 分别代表分别代表n个顶点个顶点, ,采用邻接矩阵存采用邻接矩阵存 储该图储该图, ,有有 wij 当顶点当顶点vi 到顶点到顶点vj 有边有边, ,且权为且权为wij ai, j= = 当顶点当顶点vi 到顶点到顶点vj j无边时无边时 0 当当vi=vj 时时设出发顶点为设出发顶点为v(

35、 (通常称为源点通常称为源点) )。north china electric power university2. . 设置一个标志数组设置一个标志数组s1:n记录源点记录源点v 到图中哪些顶点的最短到图中哪些顶点的最短 路径已经找到，有：路径已经找到，有： 1 1 表示源点到顶点表示源点到顶点i 的最短路径已经找到的最短路径已经找到 si = 0 表示源点到顶点表示源点到顶点i 的最短路径尚未找到的最短路径尚未找到 初始时，初始时， sv=1, si=0 i =1, 2, , n i v3. . 设置数组设置数组dist1:n 分别记录源点分别记录源点v 到图中各顶点的最短路径到图中各顶点的

36、最短路径的路径长度，的路径长度， 其中，其中，disti记录源点到顶点记录源点到顶点i 的最短路径的的最短路径的长度；初始时，长度；初始时，dist数组的值为邻接矩阵第数组的值为邻接矩阵第v 行的行的n个元素值。个元素值。 4. . 设置数组设置数组path1:n 分别记录源点分别记录源点v 到图中各顶点的最短路到图中各顶点的最短路 径所经过的顶点序列，其中，径所经过的顶点序列，其中，pathi记录源点到顶点记录源点到顶点i 的的 路径，初始时，路径，初始时，pathi= v , i =1, 2, 3, , n 华电计算机系华电计算机系013524455010201015152033530v0

37、v0是源点是源点 最短路径最短路径v0v2 10v0v2 10v0v2v3 10+15=25v0v2v3 10+15=25v0v2v3v1 10+15+20v0v2v3v1 10+15+20v0v4 45v0v4 45v0v5 v0v5 无路可走无路可走 从以上可以发现每一条最短路径中间所经过的顶点具有如从以上可以发现每一条最短路径中间所经过的顶点具有如下特点：下一条最短路径下特点：下一条最短路径( (设其终点为设其终点为x)x)可能是可能是,或者或者 ,v,x，而，而u,u,v,v都是已求得的最短路径终点。都是已求得的最短路径终点。例例 假设假设s s为已求得的最短路径的终点的集合为已求得的

38、最短路径的终点的集合(s(s初态为空集初态为空集) )，则，则下一条长度次短的最短路径（设终点为下一条长度次短的最短路径（设终点为x x）：）： 或者是弧或者是弧 v0,x； 或者是中间经过或者是中间经过s s集合中顶点，最后到达顶点集合中顶点，最后到达顶点x x的路径。的路径。 dijkstra算法思想：算法思想：north china electric power university4.4.算法算法( (用自然语言表达用自然语言表达) )1. 确定确定dist、s、path 三个数组的初值。三个数组的初值。2. 利用利用s数组与数组与dist 数组在那些尚未找到最短路径的顶点中数组在那些

39、尚未找到最短路径的顶点中 确定一个与源点最近的顶点确定一个与源点最近的顶点u, ,并置并置su为为1，同时将顶点，同时将顶点 u加入加入pathu. .3. . 根据顶点根据顶点u修改源点到所有尚未找到最短路径的顶点的路修改源点到所有尚未找到最短路径的顶点的路 径长度。径长度。 即即 1）将源点将源点v到顶点到顶点u的的( (最短最短) )路径长度分别加到源点路径长度分别加到源点v 通过顶点通过顶点u可以直接到达、且尚未找到最短路径的那些顶可以直接到达、且尚未找到最短路径的那些顶 点的路径长度上点的路径长度上; ;若加后的长度小于原来若加后的长度小于原来v 到某顶点到某顶点r的路的路 径长度，

40、则用加后的长度替代原来的长度，否则不替代。径长度，则用加后的长度替代原来的长度，否则不替代。 2）若替代，将源点）若替代，将源点v 到顶点到顶点u 的路径的路径( (最短路径最短路径) )上经上经 过的所有顶点替换过的所有顶点替换pathr. .4. . 重复第重复第2 至第至第3 步步n-1 次。次。for i1 to n do disticostv, iend si0sv1 pathi v 北航计算机系北航计算机系north china electric power university floyed算法思想：算法思想： 从从i i 到到j j的路径上每次增加一个结点的路径上每次增加一个结

41、点k k，看这个增加了一，看这个增加了一个结点个结点k k的新路径的长度是否比原来的路径长度小，若小的新路径的长度是否比原来的路径长度小，若小, ,则则以新路径代之以新路径代之, ,否则保持原路径。否则保持原路径。a(k)i,j=mina(k-1)i,j,a(k-1)i,k+a(k-1)k,j (1kn) 算法计算公式：算法计算公式：其中其中: :a(k)i,j表示顶点表示顶点i,j之间的中间点的序号不大于之间的中间点的序号不大于k的最短距离的最短距离; 由于由于g g中顶点编号不大于中顶点编号不大于n n，所以最后到了，所以最后到了a an ni,ji,j就代表就代表i i到到j j的最短路

42、径之长。的最短路径之长。north china electric power university算法描述：算法描述：procedure all_path(cost);begin for i:=1 to n do for j:=1 to n do ai,j:=costi,j; if(ij)and(ai,jmax) then pathi,j=i+j for k:=1 to n do for i:=1 to n do for j:=1 to n do if ai,k+ak,jai,j then ai,j:=ai,k+ak,j; pathi,j:=pathi,k+pathk,j; end;north

43、 china electric power universitycost=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)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 north china electric

44、power universityk=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 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

45、 3 3 3 7 7 0 3 ca 0 3 ca cabcabnorth china electric power universityk=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 cabcabnorth china electric power universityaov网与拓扑排序网与拓扑排序一一. .什么是什么是aov网网验收验收筹备

46、筹备招标招标备料备料进驻进驻工地工地测量测量挖地基挖地基浇注浇注水泥水泥搭架搭架 子子例例1north china electric power university华电华电计算机系计算机系程序程序语言语言数据数据结构结构离散离散数学数学软件软件工程工程操作操作系统系统编译编译原理原理数据库数据库计算机计算机组成组成汇编汇编网络网络数字数字逻辑逻辑计算机计算机导论导论例例2north china electric power university华电计算机系华电计算机系二二. .aov网的定义网的定义 在在aov网中，若顶点网中，若顶点i 到顶点到顶点j 之间有有向路径，之间有有向路径， 则称

47、顶点则称顶点i 为顶点为顶点j 的前驱，顶点的前驱，顶点j 为顶点为顶点i的后继；若的后继；若 顶点顶点i 到顶点到顶点j 之间为一条有向边，则称顶点之间为一条有向边，则称顶点i 为顶点为顶点j 的直接前驱，顶点的直接前驱，顶点j 为顶点为顶点i 的直接后继。的直接后继。 以顶点表示活动，以有向边表示活动之间的优先以顶点表示活动，以有向边表示活动之间的优先关系的有向图称为关系的有向图称为aov网。网。north china electric power university 三三. .拓扑排序拓扑排序 检查检查aov网是否存在回路的方法是对网是否存在回路的方法是对aov网进行网进行拓扑排序，构

48、造一个序列，使得该序列满足条件：拓扑排序，构造一个序列，使得该序列满足条件： 1. . 若在若在aov网中，顶点网中，顶点i 优先于顶点优先于顶点j , ,则在该序则在该序列中也是顶点列中也是顶点i 优先于顶点优先于顶点j 。 2. . 若在若在aov网中，网中， 顶点顶点i 与顶点与顶点j之间不存在优之间不存在优先关系先关系, ,则在该序列中建立它们的优先关系，即顶点则在该序列中建立它们的优先关系，即顶点i优先于顶点优先于顶点j，或顶点，或顶点j 优先于顶点优先于顶点i 。 3. . 若能够构造出拓扑序列，则拓扑序列包含若能够构造出拓扑序列，则拓扑序列包含aov网的全部顶点。网的全部顶点。n

49、orth china electric power university 四四. .拓扑排序方法拓扑排序方法 1. . 从从aov网中任选择一个没有前驱网中任选择一个没有前驱( (入度为入度为0) )的顶点的顶点； 2. . 从从aov网中去掉该顶点以及以该顶点为出发点的所网中去掉该顶点以及以该顶点为出发点的所 有边；有边； 3. . 重复上述过程，直到网中的所有顶点都被去掉重复上述过程，直到网中的所有顶点都被去掉, ,或或 者网中还有顶点，但不存在入度为者网中还有顶点，但不存在入度为0 的顶点；的顶点； 前者说明前者说明aovaov网中无回路，网中无回路，后者说明后者说明aovaov网中存在

50、回路。网中存在回路。north china electric power universityv1v4v3v2v6v5v7v1v5v7v3v6v2v4例例华电计算机系华电计算机系v4v3v2v6v7v4v3v2v6v5v7v4v3v2v7v4v3v7v4v7v7north china electric power universityaoe网与关键路径网与关键路径筹备筹备付款付款签合同签合同做预做预置件置件验收验收施工施工招标招标7 7天天联系材料联系材料8 8天天图纸设计图纸设计1515天天进驻工地进驻工地4 4天天运材料运材料6 6天天搬搬运运3 3天天例例north china elec

51、tric power university一一. .aoe网的定义网的定义 aoe网为一个带权的有向无环图，其中，顶点表示事网为一个带权的有向无环图，其中，顶点表示事件，有向边表示活动，边上的权值表示活动持续的时间。件，有向边表示活动，边上的权值表示活动持续的时间。v1v4v2v3v5v7v9v8v6a1a2a3a4a5a6a7a8a9a10a1164511297244 正常情况下，正常情况下，aoe网中只有一个入度为网中只有一个入度为0 的顶点，称的顶点，称 之为之为源点源点；有一个出度为；有一个出度为0 的顶点，称之为的顶点，称之为终点终点。north china electric power university1. .只有在某个顶点所代表的事件发生以后只有在某个顶点所代表的事件发生以后, ,该顶点引发的该顶点引发的 活动才能开始。活动才能开始。2. .进入某事件的所有边所代表的活动都已完成进入某事件的所有边所代表的活动都已完成, ,该顶点所该顶点所 代表的事件才能发生。代表的事件才能发生。aoe网的特点网的特点：1. . 关键路径的定义关键路径的定义 从源点到终点的路径中具有最大路径长度的路径为从源点到终点的路径中具有最大路径长度的路径为关键路径关键路径;