图-数据结构课件.pptx

1、“图图”专题专题2012年11级新队员暑假ACM培训主讲：廖枝平2022-12-91 1)1)了解图的定义和术语；了解图的定义和术语；2)2)掌握图的各种存储结构；掌握图的各种存储结构；3)3)掌握图的深度优先搜索和广度优先搜索遍历算掌握图的深度优先搜索和广度优先搜索遍历算法；法；4)4)理解最小生成树、最短路径、拓扑排序等图的理解最小生成树、最短路径、拓扑排序等图的常用算法。常用算法。主要介绍图的基本概念、图的存储结构和有关主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。学习目的：图的一些常用算法。学习目的：2022-12-92 集合集合:数据元素间的关系是同属一个集合。数据元素间

2、的关系是同属一个集合。线性结构：线性结构：结点间的关系是线性关系，除开始结点和结点间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。终端结点外，每个结点只有一个直接前趋和直接后继。树形结构：树形结构：结点间的关系实质上是层次关系，同层上结点间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。结点除外）。图（图（GraphGraph）结构：结构：对结点（图中常称为顶点）的前趋对结点（图

3、中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。和后继个数不加限制的，即结点之间的关系是任意的。图图是一种较线性表和树更为复杂的是一种较线性表和树更为复杂的非线性结构非线性结构。是对。是对结点的前趋和后继个数不加限制的数据结构，用来描述结点的前趋和后继个数不加限制的数据结构，用来描述元素之间元素之间“多对多多对多”的关系。的关系。2022-12-932022-12-94 2022-12-952022-12-96（a)G1（b)G2（c)G3（d)G452341123467522223645212022-12-97 在图在图7-17-1中，图中，图(a)a)为无向图，其中为无

4、向图，其中G1G1的顶点集的顶点集合和边集合分别为：合和边集合分别为：V(G1)=1V(G1)=1，2 2，3 3，4 4，5 5，6 6，77，E(G1)=(1E(G1)=(1，2)2)，(l(l，3)3)，(2(2，3)3)，(3(3，4)4)，(3(3，5)5)，(5(5，6)6)，(5(5，7)7)。图图(c)c)为有向图，其中为有向图，其中G3G3的顶点集合和弧集合的顶点集合和弧集合分别为分别为V(G3)=1V(G3)=1，2 2，3 3，4 4，5 5，66，E(G3)=，2022-12-987.1.2 图的基本术语图的基本术语1 1 顶点的度顶点的度 与顶点与顶点v v相关的相关

5、的边边或弧的数目或弧的数目称作顶点称作顶点v v的度。的度。在有向图在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。度和出度之和称为该顶点的度。例如图例如图7-17-1中，无向图中，无向图G1G1中顶点中顶点3 3的度为的度为4 4，顶点，顶点5 5的度为的度为3 3。例如在图例如在图7-17-1中，有向图中，有向图G3G3中顶点中顶点1 1的出度的出度OD(1)=3OD(1)=3，入入度度ID(1)=1ID

6、(1)=1，其度其度TD(1)=4TD(1)=4。2022-12-99 在无向图在无向图G中，若存在一个顶点序列中，若存在一个顶点序列Vp,Vi1，Vi2，Vin，Vq,使得（使得（Vp,Vi1）,(Vi1,Vi2),.，(Vin,Vq)均属于均属于E（G），），则称则称顶点顶点Vp到到Vq存在一条路径。存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为同，则称此路径为简单路径简单路径。起点和终点相同的路径称为起点和终点相同的路径称为回路回路；简单路径组成的回路称为简单回路。简单路径组成的回路称为简单回路。路径上经

7、过的路径上经过的边的数目边的数目称为该路径的称为该路径的路径长度路径长度。2022-12-9102022-12-911 边边:无向图中无向图中顶点的偶对，写成（顶点的偶对，写成（VxVx，VyVy）或（或（VyVy，VxVx）。）。弧弧:有向图中顶点的偶对有向图中顶点的偶对,Vx,VyVx,Vy表示从表示从VxVx到到VyVy。弧头弧头:弧的终点弧的终点 弧尾弧尾:弧的起点弧的起点弧弧 VxVx，VyVy 弧尾弧尾Vx 弧头弧头Vy2022-12-912 设有两个图设有两个图 G(V,E)和和 G(V,E)。若若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。2022-

8、12-913（a)（b)52341364521图图7-3 7-3 连通分量和强连通分量连通分量和强连通分量 v vi i和和v vj j（v vi i，v vj jVV）图图7-17-1中中G1G1是连通图，是连通图，G2G2是非连通图。是非连通图。G2 G2中有中有3 3个连通分量，如图个连通分量，如图7-37-3（a a）所示。所示。2022-12-914(a)无向网 (b)有向网 图 7-4 无向带权图和有向带权图 5 3 1 2 4 4 1 6 7 2 3 5 8 A B C 2 1 5 3 4 或弧或弧权可以代权可以代表一个顶点到另一个顶点的距离，耗费等。表一个顶点到另一个顶点的距离

9、，耗费等。一般称为一般称为如图如图7-47-4所示所示 2022-12-915 非连通图非连通图的生成树则组成一个的生成树则组成一个生成森林生成森林。若图中有。若图中有n n个顶点个顶点，m m个连通分量，则生成森林中有个连通分量，则生成森林中有n-mn-m条边。条边。2022-12-916 图的基本运算也包括查找、插入和删除。图的基本运算也包括查找、插入和删除。（1 1）顶点定位运算）顶点定位运算 确定顶点确定顶点v v在图中的位置；在图中的位置；（2 2）取顶点运算）取顶点运算 求取图中第求取图中第i i个顶点；个顶点；（3 3）求第一个邻接点运算）求第一个邻接点运算 求图中顶点求图中顶点

10、v v的第一个邻接点；的第一个邻接点；（4 4）求下一个邻接点运算）求下一个邻接点运算 已知已知w w为图中顶点为图中顶点v v的某个邻接点，的某个邻接点，求顶点求顶点w w的下一个邻接点；的下一个邻接点；（5 5）插入顶点运算）插入顶点运算 在图中增添一个顶点在图中增添一个顶点v v作为图的第作为图的第n+1n+1个顶个顶点，其中点，其中n n为插入该顶点前图的顶点个数；为插入该顶点前图的顶点个数；（6 6）插入弧运算）插入弧运算 在图中增添一条从顶点在图中增添一条从顶点v v到顶点到顶点w w的弧。的弧。（7 7）删除顶点运算）删除顶点运算 从图中删除顶点从图中删除顶点v v以及所有与顶点

11、以及所有与顶点v v相关联相关联的弧。的弧。（8 8）删除弧运算）删除弧运算 从图中删除一条从顶点从图中删除一条从顶点v v到顶点到顶点w w的弧。的弧。2022-12-917 邻接矩阵邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的是表示顶点之间相邻关系的矩阵。设矩阵。设G(V，E)是具有是具有n个顶点的图，则个顶点的图，则G的邻接矩阵的邻接矩阵是具有如下性质的是具有如下性质的n阶方阵。阶方阵。无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。阵可能是不对称的。在有向图中：在有向图中：第第 i 行行 1

12、的个数就是顶点的个数就是顶点 i 的出度，的出度，第第 j 列列 1 的个数就是顶点的个数就是顶点 j 的入度。的入度。在无向图中在无向图中,第第 i 行行(列列)1 的个数就是顶点的个数就是顶点i 的度。的度。A Aijij=1 1 对无向图若存在边对无向图若存在边(v(vi i,v,vj j),),对有向图若存在弧对有向图若存在弧v 0 0 反之反之2022-12-91814320011000010100101(a)(b)图图7-6 有向图及其邻接矩阵有向图及其邻接矩阵 154320010101011001001110010011(a)(b)图图7-5 无向图及其邻接矩阵无向图及其邻接矩阵

13、2022-12-919 对于无向图，（对于无向图，（vi，vj）和（和（vj，vi）表示同一条边，因表示同一条边，因此，在邻接矩阵中此，在邻接矩阵中Aij=Aji。无向图的邻接矩阵是（关于主对角线）对称矩阵，可用无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。主对角线以上（或以下）的部分表示。对有向图，弧对有向图，弧和和表示方向不同的两条弧，表示方向不同的两条弧，Aij和和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。称性。邻接矩阵表示法适合于以顶点为主的运算。邻接矩阵表示法适合于以顶点为主的运算。20

14、22-12-920对于对于有向图有向图，顶点，顶点vi的的出度出度OD(vi)等于邻接矩阵等于邻接矩阵第第i行行元素元素之和；顶点之和；顶点vi的的入度入度ID(vi)等于邻接矩阵等于邻接矩阵第第i列列元素之和，即元素之和，即：对于对于无向图无向图，顶点顶点v vi i的度等于邻接矩阵第的度等于邻接矩阵第i i行的元素之和行的元素之和，即：，即：njjiA1,njjiA1,njijA1,TDTD（v vi i）=对于对于带权图的邻接矩阵带权图的邻接矩阵，定义为：，定义为：Aij=Wij 若(vi,vj)或E，Wij 为该边或弧的权 反之2022-12-921 无向图的邻接矩阵 A B C D

15、DCBAA0111101111011110A B C D 2022-12-922 有向图的邻接矩阵 A B C A B C CBAB0101001102022-12-923 使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型定义如下：定义如下：#define MAX_VERTEX_NUM 20 /最大顶点数最大顶点数typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵类型邻

16、接矩阵类型typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点表顶点表AdjMatrix arcs;/邻接矩阵邻接矩阵int vexnum,arcnum;/图的顶点数和弧数图的顶点数和弧数 MGraph;由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。疏矩阵，因此会造成一定存储空间的浪费。2022-12-924建立邻接矩阵算法建立邻接矩阵算法:void CreateMGraph(MGraph&G)int i,j,k,w;char v1,v2;printf

17、(Input vexnum&arcnum:);scanf(%d,%d,&G.vexnum,&G.arcnum);printf(Input Vertices:);scanf(%s,G.vexs);for(i=0;iG.vexnum;i+)scanf(%c,&G.vexsi);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)G.arcsij=0;for(k=0;kG.arcnum;k+)printf(Input Arcs(v1,v2&w):n);scanf(%c%c,%d,&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v

18、2);j=LocateVex(G,v2);G.arcsij=w;G.arcsji=w;return;2022-12-925void PrintMGraph(MGraph G)/输出输出 int i,j;printf(Output Vertices:);printf(%s,G.vexs);printf(n);printf(Output AdjMatrix:n);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)printf(%4d,G.arcsij);printf(n);return;2022-12-926 图的链式存储结构图的链式存储结构 1)1)为每个顶点建

19、立一个单链表，为每个顶点建立一个单链表，2)2)第第i i个单链表中包含顶点个单链表中包含顶点ViVi的所有邻接顶点。的所有邻接顶点。邻接表是图的一种链式存储结构。邻接表是图的一种链式存储结构。类似于树的孩子链表类似于树的孩子链表表示法。表示法。在邻接表中为图中每个顶点建立一个单链表，用在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。以该顶点为弧尾的一条弧），称为边（或弧）结点。2022-12-927 表结点表结点头结点头结点adjvexnextarcin

20、fodatafirstarc2022-12-9282022-12-9292022-12-930(a)1304421302143231501234(b)41320212310123(c)143213003201232022-12-9312022-12-932无向图、有向图 A B C D A B C 2022-12-933无向图的邻接表 AV BV DV CV B C D A B D A C D A B C 2022-12-934 AV BV CV C B C B 有向图的邻接表2022-12-9352022-12-936int LocateVex(ALGraph G,char u)int i;

21、for(i=0;iG.vexnum;i+)if(u=G.verticesi.data)return i;if(i=G.vexnum)printf(Error u!n);exit(1);return 0;void CreateALGraph_adjlist(ALGraph&G)int i,j,k,w;char v1,v2;ArcNode*p;printf(Input vexnum&arcnum:);scanf(%d,%d,&G.vexnum,&G.arcnum);printf(Input Vertices:);for(i=0;iG.vexnum;i+)scanf(%c,&G.verticesi.

22、data);G.verticesi.firstarc=NULL;2022-12-937 printf(Input Arcs(v1,v2&w):n);for(k=0;kadjvex=j;p-info=w;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;return;2022-12-938hlinkhlink指向弧头相同的下一条弧，指向弧头相同的下一条弧，tlinktlink指向弧尾相同的指向弧尾相同的下一条弧；下一条弧；datadata顶点信息，顶点信息，firstinfirstin以该顶点为头的第一个弧结点，以该顶点为头的第一个弧结点

23、，firstoutfirstout以该结点为尾的第一个弧结点以该结点为尾的第一个弧结点headvextailvexhlinktlinkinfofirstindatafirstout顶点结点顶点结点弧结点弧结点2022-12-939432132312012030103212022-12-9402022-12-941markivex ilinkjvexjlinkdatafirstedge2022-12-9422301154323441201304321图图7-9为图为图7-5(a)无向图的邻接多重表。无向图的邻接多重表。2022-12-9432022-12-944 但是，在图中有回路，从图中某一顶

24、点出发访问图中其它顶但是，在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中或许还有顶点没有访问到，点时，可能又会回到出发点，而图中或许还有顶点没有访问到，因此，图的遍历较树的遍历更复杂。因此，图的遍历较树的遍历更复杂。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。径等算法的基础。图的遍历顺序有两种：图的遍历顺序有两种：对每种搜索顺序，访问各顶点的顺序也不是唯一的。对每种搜索顺序，访问各顶点的顺序也不是唯一的。2022-12-9451 深度优先搜索思想深度优先搜索思想 深度优先搜索遍历类似于树

25、的先序遍历。假定给定图深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是的初态是所有顶点均未被访问过，在所有顶点均未被访问过，在G中任选一个顶点中任选一个顶点i作为遍历的初始点，作为遍历的初始点，则深度优先搜索则深度优先搜索递归调用包含以下操作：递归调用包含以下操作：（1 1）访问搜索到的未被访问的邻接点；）访问搜索到的未被访问的邻接点；（2 2）将此顶点的）将此顶点的visitedvisited数组元素值置数组元素值置1 1；（3 3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。邻接点开始进行

26、同样的访问和搜索。深度优先搜索深度优先搜索DFSDFS可描述为：可描述为：（1 1）访问）访问v v0 0顶点；顶点；（2 2）置）置 visitedvvisitedv0 0=1=1；（3）搜索搜索v0未被访问的邻接点未被访问的邻接点w，若存在邻接点若存在邻接点w，则则DFS(w)。2022-12-9462022-12-9472022-12-94817823456(a)2022-12-949int visitedMAX_VERTEX_NUM;void DFS(ALGraph G,int v)ArcNode*p;printf(%c,G.verticesv.data);visitedv=1;p=G

27、.verticesv.firstarc;while(p)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-nextarc;/从第从第v个顶点出发个顶点出发DFS2022-12-950整个图的整个图的DFS遍历遍历void DFSTraverse(ALGraph G)for(int v=0;vG.vexnum;+v)visitedv=0;for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);对于连通图，从一个顶点出发，调用对于连通图，从一个顶点出发，调用DFS函数即可将所有顶点函数即可将所有顶点都遍历到。都遍历到。2022-12-95

28、11 广度优先搜索思想广度优先搜索思想 广度优先搜索遍历类似于树的按层次遍历。广度优先搜索遍历类似于树的按层次遍历。对于无向连通图，广度优先搜索是从图的某个顶点对于无向连通图，广度优先搜索是从图的某个顶点v0出发，在出发，在访问访问v0之后，依次搜索访问之后，依次搜索访问v0的各个未被访问过的邻接点的各个未被访问过的邻接点w1，w2，。然后顺序搜索访问然后顺序搜索访问w1的各未被访问过的邻接点，的各未被访问过的邻接点，w2的各未的各未被访问过的邻接点，被访问过的邻接点，。即从。即从v0开始，由近至远，按层次依次访问开始，由近至远，按层次依次访问与与v0有路径相通且路径长度分别为有路径相通且路径

29、长度分别为1，2，的顶点，直至连通图中的顶点，直至连通图中所有顶点都被访问一次。所有顶点都被访问一次。广度优先搜索的顺序不是唯一的，例如图广度优先搜索的顺序不是唯一的，例如图7-10(a)连通图的广度连通图的广度优先搜索遍历顺序可为优先搜索遍历顺序可为v1，v2，v3，v4，v5，v6，v7，v8 也可为也可为v1，v3，v2，v7，v6，v5，v4，v8。17823456(a)2022-12-9521 广度优先搜索思想广度优先搜索思想 设图设图G的初态是所有顶点均未访问，在的初态是所有顶点均未访问，在G 中任选一顶点中任选一顶点i作为初作为初始点，则广度优先搜索的基本思想是：始点，则广度优先

30、搜索的基本思想是：并将其访问标志置为已并将其访问标志置为已被访问，即被访问，即visitedi=1；依此类推，直到图中所有顶点都被访问完为止依此类推，直到图中所有顶点都被访问完为止。2022-12-953广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索中需要设置一个队列点。所以在广度优先搜索中需要设置一个队列Queue，使已被访使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队问的顶点顺序

31、由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点各个邻接点 2022-12-954队列初始化，空队列；队列初始化，空队列；f-队首指针，队首指针，r-队尾指针队尾指针2022-12-955#define MAXV void bfs(ALGraph*g,int v)ArcNode*p;int queueMAXV;/定义存放队列的数组定义存放队列的数组 int visitedMAXV；/定义存放结点的访问标志的数组定义存放结点的访问标志的数组 int f=0,r=0,x,i;/队列

32、头尾指针初始化，把队列置空队列头尾指针初始化，把队列置空 for(i=0,in;i+)/访问标志数组初始化访问标志数组初始化 visitedi=0;printf(“d”,v);/访问初始顶点访问初始顶点v visitedv=1;/置已访问标记置已访问标记 r=(r+1)MAXV;queuer=v;/v进队进队 while(f!=r)/若队列不空时循环若队列不空时循环 f=(f+1)MAXV;x=queuetf;/出队并赋给出队并赋给x p=g-adjlistx.firstarc;/找与顶点找与顶点x邻接的第一个顶点邻接的第一个顶点 2022-12-956p=g-adjlistx.firstar

33、c;/找与顶点找与顶点x邻接的第一个顶点邻接的第一个顶点 while(p!=NULL)if(visitedp-adjvex=0)/若当前邻接点未被访问若当前邻接点未被访问 visitedp-adjvex=l;/置该顶点已被访问的标志置该顶点已被访问的标志 printf(“d”，p-adjvex);/访问该顶点访问该顶点 r=(r+1)MAXV;queuer=p-adjvex;/该顶点进队该顶点进队 p=p-nextarc;/找下一个邻接点找下一个邻接点 /w进队列进队列 2022-12-9572022-12-95817823456(a)17823456(b)17823456(c)2022-12

34、-959按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的生成树有个顶点的连通网络的生成树有 n 个顶个顶点、点、n-1 条边。条边。而所有包含而所有包含n-1 n-1 条边及条边及n n个顶点的连通图都个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图是无回路的树，所以生成树是连通图中的极小连通子图.由于使用不同的遍历图的方法，可以得到不同的生成树；从由于使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如深度优先生成不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树树、广度优先生成树 在图论中，常常将树定义为

35、一个无回路连通图。在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。通讯线路铺设造价最优问题就是一个最小生成树问题。2022-12-960 假设把假设把n n个城市看作图的个城市看作图的n n个顶点，边表示两个个顶点，边表示两个城市之间的线路，

36、每条边上的权值表示铺设该线城市之间的线路，每条边上的权值表示铺设该线路所需造价。铺设线路连接路所需造价。铺设线路连接n n个城市，但不形成回个城市，但不形成回路，这实际上就是图的生成树，而以最少的线路路，这实际上就是图的生成树，而以最少的线路铺设造价连接各个城市，即求线路铺设造价最优铺设造价连接各个城市，即求线路铺设造价最优问题，实际上就是在图的生成树中选择权值之和问题，实际上就是在图的生成树中选择权值之和最小的生成树。最小的生成树。构造最小生成树的算法有很多，下面分别介绍构造最小生成树的算法有很多，下面分别介绍克鲁斯卡尔克鲁斯卡尔(Kruskal)Kruskal)算法算法和和普里姆普里姆(P

37、rim)Prim)算法算法。2022-12-961 假设假设G=G=（V V，E E）是一个具有是一个具有n n个顶点的带权无向连通图，个顶点的带权无向连通图，T=(UT=(U，TE)TE)是是G G的最小生成树，其中的最小生成树，其中U U是是T T的顶点集，的顶点集，TETE是是T T的的边集，则构造最小生成树的过程如下：边集，则构造最小生成树的过程如下：(1)(1)置置U U的初值等于的初值等于V V，TETE的初值为空集；的初值为空集；(2)(2)按权值从小到大的顺序依次选取图按权值从小到大的顺序依次选取图G G中的边，若选取的中的边，若选取的边未使生成树边未使生成树T T形成回路，则

38、加入形成回路，则加入TETE；若选取的边使生成树若选取的边使生成树T T形成回路，则将其舍弃。循环执行形成回路，则将其舍弃。循环执行(2)(2)，直到，直到TETE中包含中包含(n-1)n-1)条边为止。条边为止。克鲁斯卡尔算法是一种按权值递增的次序选择合适的边克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法。来构造最小生成树的方法。2022-12-9622022-12-963 为实现克鲁斯卡尔算法需要设置一维辅助数组为实现克鲁斯卡尔算法需要设置一维辅助数组E E，按按权值从小到大的顺序存放图的边，数组的下标取值从权值从小到大的顺序存放图的边，数组的下标取值从0 0到到e

39、-1e-1（e e为图为图G G边的数目）。边的数目）。假设数组假设数组E E存放图存放图G G中的所有边，中的所有边，且边已按权值从小到大的顺序排列。且边已按权值从小到大的顺序排列。n n为图为图G G的顶点个数，的顶点个数，e e为图为图G G的边数。克鲁斯卡尔算法如下：的边数。克鲁斯卡尔算法如下：#define MAXE#define MAXV typedef struct int vex1;/边的起始顶点边的起始顶点 int vex2;/边的终止顶点边的终止顶点 int weight;/边的权值边的权值 Edge;2022-12-964Void kruskal(Edge E,int n

40、,int e)int i,j,m1,m2,sn1,sn2,k;int vsetMAXV;for(i=0;in;i+)/初始化辅助数组初始化辅助数组 vseti=i;k=1;/表示当前构造最小生成树的第表示当前构造最小生成树的第k条边，初值为条边，初值为1 j=0;/E中边的下标，初值为中边的下标，初值为0 while(je)/生成的边数小于生成的边数小于e时继续循环时继续循环 ml=Ej.vex1;m2=Ej.vex2;/取一条边的两个邻接点取一条边的两个邻接点 sn1=vsetm1;sn2=vsetm2;/分别得到两个顶点所属的集合编号分别得到两个顶点所属的集合编号 if(sn1!=sn2)

41、/两顶点分属于不同的集合，该边是最小生成树的一条边两顶点分属于不同的集合，该边是最小生成树的一条边2022-12-965 printf(“(m1，m2)：dn”,Ej.weight);k+;/生成边数增生成边数增l for(i=0;in;i+)/两个集合统一编号两个集合统一编号 if(vseti=sn2)/集合编号为集合编号为sn2的改为的改为sn1 vseti=sn1;j+;/扫描下一条边扫描下一条边 如果给定带权无向连通图如果给定带权无向连通图G G有有e e条边，且边已经按权值递增的条边，且边已经按权值递增的次序存放在数组次序存放在数组E E中，则用克鲁斯卡尔算法构造最小生成树的时中，则

42、用克鲁斯卡尔算法构造最小生成树的时间复杂度为间复杂度为O(e)O(e)。克鲁斯卡尔算法的时间复杂度与边数克鲁斯卡尔算法的时间复杂度与边数e e有关，有关，该算法适合于求边数较少的带权无向连通图的最小生成树。该算法适合于求边数较少的带权无向连通图的最小生成树。2022-12-9662022-12-9672022-12-968假设假设G=(VG=(V，E)E)是一个具有是一个具有n n个顶点的带权无向连通图，个顶点的带权无向连通图，T(UT(U，TE)TE)是是G G的最小生成树，其中的最小生成树，其中U U是是T T的顶点集，的顶点集，TETE是是T T的边集，则的边集，则构造构造G G的最小生

43、成树的最小生成树T T的步骤如下：的步骤如下：（1 1）初始状态，）初始状态，TETE为空，为空，U=vU=v0 0，v v0 0VV；（2 2）在所有在所有uUuU，vV-UvV-U的边的边(u u，v)Ev)E中找一条代价最中找一条代价最小的边小的边(uu，v)v)并入并入TETE，同时将同时将vv并入并入U U；重复执行步骤（重复执行步骤（2 2）n-1n-1次，直到次，直到U=VU=V为止。为止。在普里姆算法中，为了便于在集合在普里姆算法中，为了便于在集合U U和和(V-U)V-U)之间选取权值之间选取权值最小的边，需要设置两个辅助数组最小的边，需要设置两个辅助数组closestclo

44、sest和和lowcostlowcost，分别用分别用于存放顶点的序号和边的权值。于存放顶点的序号和边的权值。对于每一个顶点对于每一个顶点vV-UvV-U，closestvclosestv为为U U中距离中距离v v最近的一最近的一个邻接点，即边个邻接点，即边(v v，closestv)closestv)是在所有与顶点是在所有与顶点v v相邻、且相邻、且其另一顶点其另一顶点jUjU的边中具有最小权值的边，其最小权值为的边中具有最小权值的边，其最小权值为lowcostvlowcostv，即即lowcostv=costvclosestvlowcostv=costvclosestv，2022-12-

45、9692022-12-9702022-12-9712022-12-972typedef int VRType;structVertexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;void MiniSpanTree_PRIM(MGraph G,VertexType u)int k,j,i,minCost;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)if(j!=k)closedgej.adjvex=u;closedgej.lowcost=G.arcskj;2022-12-973closedgek.lowcost

46、=0;for(i=1;iG.vexnum;+i)k=minimum(closedge);minCost=INFINITY;for(j=0;jG.vexnum;+j)if(closedgej.lowcost minCost&closedgej.lowcost!=0)minCost=closedgej.lowcost;k=j;printf(%c,%c)n,closedgek.adjvex,G.vexsk);closedgek.lowcost=0;for(j=0;jG.vexnum;+j)if(G.arcskjclosedgej.lowcost)closedgej.adjvex=G.vexsk;cl

47、osedgej.lowcost=G.arcskj;2022-12-974普里姆算法中的第二个普里姆算法中的第二个forfor循环语句频度为循环语句频度为n-1n-1，其中包其中包含的两个内循环频度也都为含的两个内循环频度也都为n-1n-1，因此普里姆算法的时间复因此普里姆算法的时间复杂度为杂度为O(nO(n2 2)。普里姆算法的时间复杂度与边数普里姆算法的时间复杂度与边数e e无关，该算无关，该算法更适合于求边数较多的带权无向连通图的最小生成树。法更适合于求边数较多的带权无向连通图的最小生成树。2022-12-975 交通网络中常常提出这样的问题：从甲地到乙地之间是否交通网络中常常提出这样的问

48、题：从甲地到乙地之间是否有公路连通有公路连通?在有多条通路的情况下，哪一条路最短在有多条通路的情况下，哪一条路最短?交通网络可用带权图来表示。顶点表示城市名称，边表示交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上两个城市有路连通，边上权权值可表示两城市之间的距离、交通值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。指路径上边数之和最少，而是指路径上各边的权值之和最小。另外，若两个顶点之间没有边，则认为两个顶点无通路，另外，若两

49、个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路但有可能有间接通路(从其它顶点达到从其它顶点达到)。路径上的开始顶点路径上的开始顶点(出发点出发点)称为源点，路径上的最后一个称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。顶点称为终点，并假定讨论的权值不能为负数。2022-12-9762022-12-9772022-12-978 单源点最短路径是指：给定一个出发点单源点最短路径是指：给定一个出发点(单源点单源点)和一和一个有向网个有向网G=(VG=(V，E),E),求出源点到其它各顶点之间的最短路径。求出源点到其它各顶点之间的最短路径。迪杰斯特拉迪杰斯特拉(Dij

50、kstra)Dijkstra)在做了大量观察后在做了大量观察后,首先提出了首先提出了按路径长度递增产生各顶点的最短路径算法按路径长度递增产生各顶点的最短路径算法,我们称之为我们称之为迪迪杰斯特拉算法杰斯特拉算法。算法的基本思想算法的基本思想:设置并逐步扩充一个集合设置并逐步扩充一个集合S S，存放已存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合求出其最短路径的顶点，则尚未确定最短路径的顶点集合是是V-SV-S，其中其中V V为网中所有顶点集合。按最短路径长度递增为网中所有顶点集合。按最短路径长度递增的顺序逐个以的顺序逐个以V-SV-S中的顶点加到中的顶点加到S S中，直到中，直到S