数据结构-07图

1、数据结构数据结构 第七章 图图 第七章 图主要内容主要内容图的基本概念图的基本概念1图的存储结构图的存储结构2图的遍历图的遍历3图的常见应用图的常见应用4教学要求教学要求教学重点教学难点目标要求1理解图的基本概念及其术语；2.掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法3.熟练掌握图的两种遍历算法、思想，步骤，能列出遍历序列4.理解最小生成树的概念，能按 Prim 算法构造最小生成树；5.领会并掌握最短路径、拓扑排序的算法思想1理解图的定义、术语及其含义；2.掌握各种图的邻接矩阵表示法及其类型说明3.理解并掌握图遍历方法4.领会生成树和最小生成树的概念，掌握 Prim 算法思想；5.理解

2、并掌握最短路径和Dijkstra方法算法思想1.正确理解与区别图的常用术语2.区别图的两种存储结构的不同点及其应用场合3. Prim 算法思想4. Dijkstra算法思想7.1图的基本概念图的基本概念图图是一种数据元素间可具有任意关系的一种数据结构是一种数据元素间可具有任意关系的一种数据结构 图的特点图的特点 顶点的前驱和后继个数无限制顶点的前驱和后继个数无限制 顶点之间的关系是任意的顶点之间的关系是任意的 图中任意两个顶点之间可能有关系图中任意两个顶点之间可能有关系 例例 .集成电路的布线集成电路的布线 城市之间的交通图城市之间的交通图 电路网络的铺设电路网络的铺设 图的应用图的应用 工程

3、进度的安排工程进度的安排数据库系统的设计数据库系统的设计 课程表的制定课程表的制定 西安西安北京北京南京南京杭州杭州上海上海 南京南京 西安西安 北京北京 上海上海杭州杭州7.1图的基本概念图的基本概念7.1.1 图的定义图的定义图是由顶点集合图是由顶点集合V V以及相关的边集合以及相关的边集合E E构成的一种非构成的一种非线性数据结构，记为：线性数据结构，记为：G =(V，E) V4 V1 V2 V5V3无向图无向图G1 V4 V1 V2 V3有向图有向图G2G1（V1，E1）,其中其中V1 = V（G1）= v1，v2，v3，v4，v5 E1 = E（G1) = (v1，v2),(v1，v

4、4),(v2，v3),(v3，v4）,(v3，v5), (v4，v5) G2（V2，E2），其中），其中 V2 = V（G2）=v1，v2，v3，v4 E2 = E（G2) =, , 顶点对代表边，（）顶点对代表弧，有向图有向图G2 V4 V1 V2 V37.1.2关于图的若干术语关于图的若干术语顶点vi，vj之间有边(vi,vj)或弧，则vi，vj互称为邻接顶点弧头：弧尾：相关联：对于有向图，顶点v的入度是指以顶点v为弧头的弧的数目称为顶点的入度；记为ID(v)以顶点v为弧尾的弧的数目称为顶点的出度，记为OD(v)。与顶点v相关联的边的数目称为顶点的度；记为TD(v)对有向图，是顶点的入度和

5、出度之和从顶点v出发，如果能顺沿边（对有向图为弧）到达顶点u；则称v到u之间有一条路径.表示为一个顶点的序列.路径长度：除路径的第一个顶点和最后一个顶点外，在路径顶点序列中同一顶点不重复出现的路径称为简单路径图图的若干的若干术语术语入度和出度顶顶点的度路路径径简单简单路径径邻邻接顶顶点 V4 V1 V2 V5V3无向图无向图G1ID(V1)=1ID(V1)=1ID(V3)=2ID(V3)=1TD(V3)=3TD(V1)=2(vi, vj)=(vj,vi)?=(v1 ， v2 ， v3 ， v5 ， v4 ， v3 )，路径长度，路径长度=5(v4 ， v3 ， v1 ， v2)，路径长度，路径

6、长度=3不是简单路径不是简单路径是简单路径是简单路径7.1.2关于图的若干术语关于图的若干术语子图图设G =(V,E)和G=(V,E)是两个图，若V是V的子集 ，且E是E的子集 ， 则图G称为图G的子图 V4 V1 V2 V5 V4 V1 V2 V5V3V1 V2 V5V3V1 V4 V1 V2 V5V3无向图无向图G1V1 V2V3 V4 V5V3V1 V2V3 V4 V1 V2 V5 V4 V2 V5V3哪些是G1的子图？7.1.2关于图的若干术语关于图的若干术语有向图有向图G2 V4 V1 V2 V3 V4 V2 V3V1 V2 V3V1 V2 V3 V4 V1 V2 V3V1 V3 V

7、2 V3子图图设G =(V,E)和G=(V,E)是两个图，若V是V的子集 ，且E是E的子集 ， 则图G称为图G的子图如果一条路径的第一个顶点和最后一个顶点为同一个顶点，则称该路径为回路，或称环第一个顶点和最后一个顶点为同一个顶点的简单路径；或称简单环从顶点 vi到顶点vj有路径，则说 vi和vj是连通的若图中任意两顶点之间都是连通（对于无向图）对有向图，如果任意一对顶点v ,u之间均有从v到u和从u到v的路径存在图图的若干的若干术语术语入简单简单回路连连通连连通通图图强连连通图图回路 V4 V1 V2 V5V3无向图无向图G1有向图有向图G2 V4 V1 V2 V3回路回路(v1 ， v2 ，

8、 v3 ， v5 ， v4 ， v1 )回路回路:(v2 ， v3 ， v1 ， v2)回路回路(v1 ， v2 ， v3 ， v5 ， v4 ， v3 ， v2 ， v1 )7.1.2关于图的若干术语关于图的若干术语连通连通图图非强连通图非强连通图7.1.2关于图的若干术语关于图的若干术语无向图的极大连通子图无向图的极大连通子图（不存在包含它更大的连通子图）（不存在包含它更大的连通子图）连通分量连通分量任何连通图的连通分量只有一个，即是其自身。非连通图有多个连通分量（非连通图的每一个连通部分）。无向图无向图( (非连通非连通) V2 V1 V3 V5 V9 V6 V8V7 V4 V2 V1

9、V3 V5 V4 V9 V6 V8V7无向图无向图3 3个连通分量个连通分量7.1.2关于图的若干术语关于图的若干术语有向图中的极大强连通子图有向图中的极大强连通子图。强连通分量强连通分量强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连通分量）。有向图有向图( (非强连通非强连通) ) V4 V1 V2 V3有向图的有向图的2 2个强连通分量个强连通分量 V4 V1 V2 V37.1.2关于图的若干术语关于图的若干术语与边或弧相关联的数称为与边或弧相关联的数称为“权权”带有权的图称为带权图带有权的图称为带权图，又称为网，又称为网权权带权图带权图权反应相关边或弧的某种数量特征。

10、如表示从一个顶点到另一个顶点的距离、时间、电流、电压、耗费、代价等 又分为无向网和有向网 V5 V1 V2V4 V6 V3 V5 V1 V2V4 V6 V315251930402515501525193040251550无向图无向图有向图有向图无向网无向网有向网有向网7.1.3 图的基本性质图的基本性质性质性质1.1. n n 个顶点的无向图最多有个顶点的无向图最多有 n(n-1)/2 n(n-1)/2 条边，条边，n n 个顶点的有向图最多有个顶点的有向图最多有n(n-1) n(n-1) 条弧条弧 。如果如果n n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 n(n-1)/2 条边，

11、则称之为条边，则称之为无向完全图无向完全图如果如果n n 个顶点的有向图有个顶点的有向图有 n(n-1)n(n-1)条边，则称之为条边，则称之为有向完全图有向完全图 V2 V1V3V4 V5 有向图中弧的取值范围：0en(n-1)。（即：每两个顶点之间都存在着一条边) V2 V1 V3 V4 若图中边或弧的数目很少，则称为稀疏图。反之，若边或弧的数目接近完全图，则称为稠密图 无向完全图无向完全图有向完全图有向完全图7.1.3 图的基本性质图的基本性质性质性质2. 2. n n 个顶点的无向连通图最少有个顶点的无向连通图最少有(n-1)(n-1)条边条边。如果如果n n 个顶点的无向连通图只有个

12、顶点的无向连通图只有(n-1)(n-1)条边，则该图条边，则该图不存在回路不存在回路 如果如果n n个顶点而变数少于个顶点而变数少于n-1n-1，则一定是，则一定是非连通的非连通的如果如果n n 个顶点的无向连通图的边数大于个顶点的无向连通图的边数大于(n-1)(n-1)，则，则必存在回路必存在回路 树树生成树：所有顶点均由边连接在一起但不存在回路生成树：所有顶点均由边连接在一起但不存在回路的图。的图。 V4 V1 V2 V5V3无向图无向图 V4 V1 V2 V5V3 V4 V1 V2 V5V3无向图的生成树无向图的生成树一个图可以有许多棵不同的生成树7.1.4 图的基本操作图的基本操作每种

13、操作会因为图的存储结构不同而有所区别每种操作会因为图的存储结构不同而有所区别图的基本操作深度优先遍历深度优先遍历删除边或弧删除边或弧插入顶点插入顶点顶点赋值顶点赋值创建图创建图读取顶点读取顶点查图的顶点查图的顶点读取邻接顶点读取邻接顶点删除顶点删除顶点插入边或弧插入边或弧广度优先遍历广度优先遍历7.2 图的存储结构图的存储结构7.2.1 邻接矩阵表示法邻接矩阵表示法邻接矩阵表示法也称数组表示法，采用两个数组表示图邻接矩阵表示法也称数组表示法，采用两个数组表示图 用一个一维数存储顶点用一个一维数存储顶点 用一个二维数组存储顶点对之间的边用一个二维数组存储顶点对之间的边 邻接矩阵邻接矩阵 V4 V

14、1 V2 V5V3无向图无向图矩阵矩阵元素元素定义：定义：Ai,jAi,j=1 1 对无向图存在对无向图存在( (vi,vjvi,vj) )边边, ,对有向图存在对有向图存在 边边 0 0 其他情况其他情况0110010101110100010101010V V1 1 V V2 2 V V3 3 V V4 4 V V5 5V V1 1 V V2 2 V V3 3 V V4 4 V V5 5邻接矩阵邻接矩阵7.2 图的存储结构图的存储结构7.2.1 邻接矩阵表示法邻接矩阵表示法 V4 V1 V2 V3有向图有向图0100000101000010V V1 1 V V2 2 V V3 3 V V4

15、4V V1 1 V V2 2 V V3 3 V V4 4 邻接矩阵邻接矩阵我们来观察下图的邻接矩阵具有哪些特点？（1 1）无向图或带权无向图的邻接矩阵是一个对称矩阵。可以采用下三角矩阵压缩存储）无向图或带权无向图的邻接矩阵是一个对称矩阵。可以采用下三角矩阵压缩存储 （2 2）对无向图，顶点）对无向图，顶点vivi的度的度TD(viTD(vi) )是其邻接矩阵中第是其邻接矩阵中第i i行（或第行（或第i i列）中列）中“1”1”的个数的个数 （3 3）对有向图，其邻接矩阵中第）对有向图，其邻接矩阵中第i i行中行中“1”1”的个数是第的个数是第i i个顶点的出度个顶点的出度OD(viOD(vi)

16、 )。而第。而第i i列中列中“1”1”的个数的个数是第是第i i个顶点的入度个顶点的入度ID(viID(vi) ) （4 4）很容易确定图或网中任意两个顶点之间是否有边或弧相连。对计算顶点的度比较方便有多少条边或）很容易确定图或网中任意两个顶点之间是否有边或弧相连。对计算顶点的度比较方便有多少条边或弧则需要逐行逐列扫描矩阵弧则需要逐行逐列扫描矩阵 （5 5）所占存储空间只与顶点个数有关，与边数无关，在边数较少时，空间浪费较大。因此，对稀疏图而）所占存储空间只与顶点个数有关，与边数无关，在边数较少时，空间浪费较大。因此，对稀疏图而言，不适于用邻接矩阵存储。言，不适于用邻接矩阵存储。 7.2.1

17、 邻接矩阵表示法邻接矩阵表示法带权图的邻接矩阵带权图的邻接矩阵矩阵矩阵元素元素定义：定义：Ai,j=w wijij 对无向图存在对无向图存在( (vi,vjvi,vj) )边边, ,对有向图存在对有向图存在 边边 其他情况其他情况邻接矩阵邻接矩阵8471245398V V1 1 V V2 2 V V3 3 V V4 4 V V5 5V V1 1 V V2 2 V V3 3 V V4 4 V V5 5 V3 V1 V5V4 V2有向带权图有向带权图83478412957.2.1 邻接矩阵表示法邻接矩阵表示法3.3.邻接矩阵的类型描述邻接矩阵的类型描述#define Vmax 20 #define

18、 INFINITY 32768typedef char VType; typedef int EType; typedef struct VType vexsVmax; EType edgesVmaxVmax; int Vnum,Enum; MGRAGH; 最大顶点数设为20表示一个最大值 用于存储顶点的数组，顶点表 用于存储边信息的矩阵，边表 MGRAPH CREATMG(MGRAPH G) int i,j; char vi,vj; printf(please input the elemnts of vexs:n); for(i=0;(G.vexsi=getchar()!=#&iVmax;

19、i+); G.Vnum=i; for(i=0;iG.Vnum;i+) for(j=0;jG.Vnum;j+) G.edgesij=0; G.Enum=0; printf(please input the %d arc such as ab :,G.Enum+1); scanf(%c%c,&vi,&vj); while(vi!=#&vj!=#&G.EnumG.Vnum*(G.Vnum)-1) if(vi=vj) printf(input errorn); else i=LOC(G.vexs,vi); j=LOC(G.vexs,vj); if(i=-1|j=-1) printf(no vexsn)

20、; else if(G.edgesij=1) printf(input repetitiousn); else G.edgesij = 1; G.edgesji = 1; G.Enum+; printf(please input the %d arc :,G.Enum+1); scanf(%c%c,&vi,&vj); return（G）; 7.2.2 有关邻接矩阵的算法有关邻接矩阵的算法1.1.建立无向图建立无向图定义定义2 2个数组；个数组；初始化顶点数组初始化顶点数组vexsvexs。将矩阵的每个元素都初始化成将矩阵的每个元素都初始化成0 0。再读入顶点对再读入顶点对 ( (vi,vjvi

21、,vj),),将边将边 ( (vi,vjvi,vj) )置置1 1对等边对等边( (vj,vivj,vi) )也置成也置成1 17.2.3 邻接表表示法邻接表表示法基本思想：基本思想：再把所有单链表邻接成一个表再把所有单链表邻接成一个表 V4 V1 V2 V5V3无向图无向图对每个顶点建立一条单链表，每一条链存储顶点数据及其与相关联顶点的边或弧对每个顶点建立一条单链表，每一条链存储顶点数据及其与相关联顶点的边或弧邻接点的位置号用一维数组存储链头结点，即顶点本身信息邻接表：由若干个单链表构成n个顶点就建n个单链表一种顺序分配与链一种顺序分配与链式分配相结合的存式分配相结合的存储方法储方法7.2.

22、3 邻接表表示法邻接表表示法链头结点结构：链头结点结构：指针指针其他其他数据数据顶点位置号顶点位置号adjvex weight next比如权值比如权值链结点结构：链结点结构：指针指针顶点数据顶点数据vertex link指针指针顶点位置号顶点位置号adjvex next带其他信息的链结点结构带其他信息的链结点结构#define Vmax 20#define INFINITY 32768typedef char VertexType; typedef int EdgeType;typedef struct EnodeVertexType adjvex; EdgeType weight; str

23、uct arcnode *next;EDGENODE;typedef struct Vnode VertexType vertex; EDGENODE *link; HNODE;typedef struct HNODE hlistVmax;int vexnum,arcnum; LGRAPH;每个单链表由链头结点和链结点构成每个单链表由链头结点和链结点构成 定义链结点定义链结点定义链头结点定义链头结点定义图定义图指示第一条边或弧指示第一条边或弧存放与存放与 vi vi 邻接的顶点在表邻接的顶点在表头数组中的位置头数组中的位置指示下一条边或弧指示下一条边或弧邻接表的类型描述：邻接表的类型描述：7.

24、2.3 邻接表表示法邻接表表示法有向图邻接表的特点：有向图邻接表的特点：（1 1）第）第i i 个链表中结点数目为顶点个链表中结点数目为顶点i i的出度的出度；（2 2）所有链表中结点数目为图中弧数；）所有链表中结点数目为图中弧数；（3 3）占用的存储单元数目为）占用的存储单元数目为n+en+e 。不能直接求出顶点的入度不能直接求出顶点的入度无向图邻接表的特点：无向图邻接表的特点：（1 1）第）第i i 个链表中结点数目为顶点个链表中结点数目为顶点i i的度；的度；（2 2）所有链表中结点数目的一半为图中边数；）所有链表中结点数目的一半为图中边数；（3 3）占用的存储单元数目为）占用的存储单元

25、数目为n+2e n+2e 。有向图的邻接表：有向图的邻接表：1. 1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。行中非零元素的个数。2. 2. 区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。致），但邻接表不唯一（链接次序与顶点编号无关）。3. 3. 用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-1)/2)n(n-

26、1)/2)；而邻接表多用于稀而邻接表多用于稀疏图的存储（疏图的存储（enen2 2) )讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？7.3 图的遍历图的遍历常见的图遍历方式有两种：深度优先遍历和广度优先遍历常见的图遍历方式有两种：深度优先遍历和广度优先遍历 从图的某个顶点出发，访问图中每个顶点且每个顶点只访问一次，称为从图的某个顶点出发，访问图中每个顶点且每个顶点只访问一次，称为图的遍历。图的遍历。 7.3.1 深度优先遍历深度优先遍历1首先访问顶点首先访问顶点i i2若当前访问的顶点的若当前访问的顶点的邻接顶点有未被访问邻接顶点有未被访问的，则任选一个访问的，

27、则任选一个访问之；之；反之，退回到最近访反之，退回到最近访问过的顶点；直到与问过的顶点；直到与起始顶点相通的全部起始顶点相通的全部顶点都访问完毕；顶点都访问完毕；3若此时图中尚有顶点若此时图中尚有顶点未被访问，则再选其未被访问，则再选其中一个顶点作为起始中一个顶点作为起始顶点并访问之，重复顶点并访问之，重复上述过程；上述过程； 反之，反之，遍历结束遍历结束为了避免重复访为了避免重复访问而造成死循环，问而造成死循环，我们要设定一个我们要设定一个访问标识访问标识出现这种情况的出现这种情况的是非连通图我们是非连通图我们这里不讨论这里不讨论访问该结点后，访问该结点后，将其访问标记置将其访问标记置为访问

28、过，即为访问过，即visitedivisitedi=1=1；7.3.1 深度优先遍历深度优先遍历 D A B E CGHF深度优先遍历过程：深度优先遍历过程： EB C FDAGHADGEBCFH起始访问点起始访问点深度优先遍历序列：深度优先遍历序列：这个序列并不是这个序列并不是唯一的唯一的7.3.1 深度优先遍历深度优先遍历深度优先遍历算法：深度优先遍历算法：void DFSTMG(MGRAPH G) int visitedM=0; int i,j; SEQSTACK S; S = INISTACK(); Visited0=1; printf(%c ,G.vexs0); S = PUSSTA

29、CK(S,0); S = PUSSTACK(S,0); while(!EMPSTACK(S) i = GETSTACK(S); for(j=0;j= G.Vnum) S = POPSTACK(S);7.3.2 广度优先遍历广度优先遍历广度优先遍历方法：广度优先遍历方法：1首先访问顶点首先访问顶点i i，并，并将其访问标志置为已将其访问标志置为已被访问，即被访问，即visitedivisitedi=1=1；2接着依次访问与顶点接着依次访问与顶点i i有边相连的所有顶有边相连的所有顶点点W1W1，W2W2，WtWt3然后再按顺序访问与然后再按顺序访问与W1W1，W2W2，WtWt有边有边相连又未曾

30、访问过的相连又未曾访问过的顶点；顶点；依此类推，直到图中依此类推，直到图中所有顶点都被访问完所有顶点都被访问完为止为止 7.3.2 广度优先遍历广度优先遍历 D A B E CGHF广度优先遍历过程：广度优先遍历过程： EB C FDAGHADEBGCHF起始访问点起始访问点广度优先遍历序列：广度优先遍历序列：这个序列也不是这个序列也不是唯一的唯一的7.3.2 广度优先遍历广度优先遍历广度优先遍历算法：广度优先遍历算法：void BFSTMG(MGRAPH G) int visitedM; int i=0,j; SEQUEUE Q; Q=INIQUEUE(Q); visited0=1; pri

31、ntf(%c ,G.vexs0); Q=INCQUEUE(Q,0); doi = GETQUEUE(Q); Q = OUTCQUEUE(Q); for(j=0;jG.Vnum;j+) if(G.edgesij=1 & visitedj!=1) visitj=1; printf(%c ,G.vexsj); Q=INCQUEUE(Q,j); while(!EMQUEUE（Q)）;7.4 图的常见应用图的常见应用图的常见图的常见应用应用关键路径关键路径，外排序，外排序等等拓扑排序拓扑排序问题问题最短路径最短路径问题问题最小生成最小生成树问题树问题是是图图的比的比较较典型的典型的应应用用7.4.1 最

32、短路径问题最短路径问题1.单源点最短路径问题：单源点最短路径问题：从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径所谓最短路径问题是指，如果从图中某一顶点（源点）到达另一顶点（终点）所谓最短路径问题是指，如果从图中某一顶点（源点）到达另一顶点（终点）的路径的路径 ，沿此路径上各边的权值总和（称为路径长度）达到最小，沿此路径上各边的权值总和（称为路径长度）达到最小 在有多条通路的情况下，哪一条路最短在有多条通路的情况下，哪一条路最短 2个顶点之间没个顶点之间没有边，但有可有边，但有可能有间接通路能有间接通路2 2、迪杰斯特拉（、迪杰斯特拉（DijkstraDijkstra）算法：

33、）算法：按按路径长度递增路径长度递增次序产生各顶点的最短路径。次序产生各顶点的最短路径。 1、将源点到终点的所有路径都列出来，然后在其中选最短的一条。、将源点到终点的所有路径都列出来，然后在其中选最短的一条。 缺点：缺点：当路径特别多时，特别麻烦；没有规律可循。当路径特别多时，特别麻烦；没有规律可循。 V4 V1 V2 V5V3202510812183157.4.1 最短路径问题最短路径问题理解路径长度递增：理解路径长度递增： V4 V1 V2 V5V320251081218315选定源点：选定源点：v v1 1到其他各点的路径中，必定只含一条弧到其他各点的路径中，必定只含一条弧 v ，且其权

34、值最小。，且其权值最小。 由此，只要在所有从源点出发的弧中查找权值最小者。由此，只要在所有从源点出发的弧中查找权值最小者。 (18) (18)它只可能有两种情况：它只可能有两种情况： 1)1)、直接从源点到、直接从源点到 v vi i （只含一条弧只含一条弧）；）； 下一条下一条路径长度次短路径长度次短的最短路径的最短路径： (20) (20)2)2)、从源点经过顶点、从源点经过顶点 v v4 4，再到达，再到达 v vi i , , （由两条弧组成由两条弧组成）。）。v v4 4 必为已求得必为已求得的最短路径上的最短路径上的顶点的顶点V4V27.4.1 最短路径问题最短路径问题 可能有四种

35、情况：可能有四种情况： 1)1)、直接从源点到、直接从源点到 v vi i （由一条弧组成由一条弧组成）；）； 2)2)、从源点经过顶点、从源点经过顶点 v v4 4，再到达，再到达 v vi i , , （由两条弧组成由两条弧组成）；）； 3)3)、从源点经过顶点、从源点经过顶点 v v2 2，再到达，再到达 v vi i , , （由两条弧组成由两条弧组成）；）； 4)4)、从源点经过顶点、从源点经过顶点 v v4 4, , v v2 2，再到达，再到达 v vi i , , , , （由三条弧组成由三条弧组成）；）； 再下一条再下一条路径长度次短路径长度次短的最短路径的特点：的最短路径的

36、特点： , , (30) (30) V4 V1 V2 V5V320251081218315v v4 4 v v2 2必为已求必为已求得的最短路径得的最短路径上的顶点上的顶点其余最短路径：其余最短路径： 2)2)、从源点、从源点，再到达再到达（含有多条弧含有多条弧） V4V1 V2 V5V3202510812183151)1)、直接从源点到、直接从源点到 v vi i （只含一条弧只含一条弧）；）；V3V5 , , (33) (33)7.4.1 最短路径问题最短路径问题2.迪杰斯特拉算法思路：迪杰斯特拉算法思路： V4 V1 V2 V5V320251081218315步骤：步骤：（1）初始时，）

37、初始时，S只包含源点，只包含源点，S=v，v的距离为的距离为0。T包含除包含除v外的其他顶点，外的其他顶点，T中顶点的距离为顶点的权或中顶点的距离为顶点的权或 。（2）从）从T中选取一个距离最小的顶点中选取一个距离最小的顶点vi，把，把vi加入到加入到S中中（3）以）以k 作为新考虑的中间点，修改作为新考虑的中间点，修改T中各顶点的距离。中各顶点的距离。（4）重复步骤（）重复步骤（2）、（）、（3）直到所有顶点都包含在）直到所有顶点都包含在S中。中。终点终点从从 v v1 1 到各终点的最短路径及长度到各终点的最短路径及长度i i =1 =1i i =2 =2i i =3 =3i i =4 =

38、4v v1 1v v2 2v v3 3v v4 4v v5 5v vj j S S02018V1v418V40201833V2v220020301833V3v320+10020301833V5v518+157.4.2 最小代价生成树问题最小代价生成树问题1.最小代价生成树的概念最小代价生成树的概念生成树：是一个极小连通子图，它含有图中全部顶点，但只有生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。条边。所有顶点均由边连接在一起，但不存在回路的图所有顶点均由边连接在一起，但不存在回路的图最小生代价成树：给定一个无向网，在该网的所有生成树中，使得各边权数之和最小最小生代价成树：给

39、定一个无向网，在该网的所有生成树中，使得各边权数之和最小的那棵生成树称为该网的最小代价生成树，也叫最小生成树。的那棵生成树称为该网的最小代价生成树，也叫最小生成树。 普里姆算法普里姆算法MST（Minimum cost Spanning Tree）性质）性质如何获得图的生成树如何获得图的生成树 如何获得图的最小代价生成树如何获得图的最小代价生成树 由深度优先遍历得到的生成树，获得由深度优先遍历得到的生成树，获得深度优先生成树深度优先生成树由广度优先遍历得到的生成树，获得广度度优先生成树由广度优先遍历得到的生成树，获得广度度优先生成树 7.4.2 最小代价生成树问题最小代价生成树问题2.普里姆算法：普里姆算法：E A FDG C B171912AEG14168D21615BC5F13Prim算法是从连通网中的某一个顶点开始，以此作为生成树的初始状态，然后不断地将算法是从连通网中的某一个顶点开始，以此作为生成树的初始状态，然后不断地将网中的网中的其它顶点其它顶点添加到生成树上，直到最后一个顶点添加到生成树上时得到最小生成树添加到生成树上，直到最后一个顶点添加到生成树上时得到最小生成树一端在生成树中另一端在生成树外的所以一端在生