本章主要介绍图的基本概念、图的存储结构和有关图的一些常课件.ppt

1、本章主要介绍图的基本概念、图的存储结构和有关图本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习：的一些常用算法。通过本章学习：1)了解图的定义和术语了解图的定义和术语 2)掌握图的各种存储结构掌握图的各种存储结构 3)掌握图的深度优先搜索和广度优先搜索遍历算法掌握图的深度优先搜索和广度优先搜索遍历算法 4)理解最小生成树、最短路径、拓扑排序、关键路径理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法等图的常用算法 图图(Graph)是一种较线性表和树更为复杂的非线性结构：对结点的前趋和是一种较线性表和树更为复杂的非线性结构：对结点的前趋和后继个数不加限制的数据

2、结构，描述元素之间后继个数不加限制的数据结构，描述元素之间”多对多多对多”关系。图的应用极广，关系。图的应用极广，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。的其它分支中。在线性结构中，结点之间是在线性结构中，结点之间是线性关系线性关系，除开始结点和终端结点外，每个结，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。点只有一个直接前趋和直接后继。在树形结构中，结点之间实质上是在树形结构中，结点之间实质上是层次关系层次关系，同层上的每个结点可以和下，同层上的每个结点可以和下一层的

3、零个或多个结点（即孩子）相关，但只和上一层的一个结点（即双亲）一层的零个或多个结点（即孩子）相关，但只和上一层的一个结点（即双亲）相关（根结点除外），树是图的特例！相关（根结点除外），树是图的特例！图的引入：哥尼斯堡桥问题图的引入：哥尼斯堡桥问题 6.1.2 图的基本术语图的基本术语R RZ ZY YX XX XS SR RZ ZY Y（a)G1（b)G2（c)G3（d)G452341123467522223645211.无向图无向图G1中顶点中顶点3的度为的度为 4，顶点，顶点5的度为的度为3。2.有向图有向图G3中顶点中顶点1的出度的出度OD(1)=3，入度入度ID(1)=1，其其度度TD

4、(1)=4。在图在图6-16-1中，图中，图(a)a)为无向图，其中为无向图，其中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)=，在无向图在无向图G中，若存在一个顶点序

5、列中，若存在一个顶点序列Vp,Vi1，Vi2，Vin，Vq,使得（使得（Vp,Vi1）,(Vi1,Vi2),.，(Vin,Vq)均属于均属于E（G），），则称顶则称顶点点Vp到到Vq存在一条路径。存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为则称此路径为简单路径简单路径。起点和终点相同的路径称为起点和终点相同的路径称为回路回路；简单路径组成的回路称为简单回路。简单路径组成的回路称为简单回路。路径上经过的路径上经过的边的数目边的数目称为该路径的称为该路径的路径长度路径长度。边边:无向图中无向图中顶点的偶对，写

6、成（顶点的偶对，写成（VxVx，VyVy）或（或（VyVy，VxVx）。）。弧弧:有向图中顶点的偶对有向图中顶点的偶对,Vx,VyVx,Vy表示从表示从VxVx到到VyVy。弧头弧头:弧的终点弧的终点弧尾弧尾:弧的起点弧的起点弧弧 VxVx，VyVy 弧尾弧尾Vx 弧头弧头Vy 设有两个图设有两个图 G(V,E)和和 G(V,E)。若若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。（a)（b)52341364521图图6-3 6-3 连通分量和强连通分量连通分量和强连通分量 v vi i和和v vj j（v vi i，v vj jVV）图图6-16-1中中G1G1是连

7、通图，是连通图，G2G2是非连通图。是非连通图。G2 G2中有中有3 3个连通分量，如图个连通分量，如图6-36-3（a a）所示。所示。邻接点邻接点顶点顶点:图中的结点图中的结点 邻接点邻接点:无向图中，若边无向图中，若边(x,x,y)y)E E，有向图中，若弧有向图中，若弧(x,x,y)y)E E，VxVyx、y互为邻接点互为邻接点VxVyy是是x的邻接点的邻接点2022-12-2811 邻接矩阵邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设是表示顶点之间相邻关系的矩阵。设G(V，E)是具有是具有n个顶点的图，则个顶点的图，则G的邻接矩阵是具有如下性质的的邻接

8、矩阵是具有如下性质的n阶方阶方阵。阵。Aij=1 对无向图若存在边(vi,vj),对有向图若存在弧0 反之无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。对称的。在有向图中：在有向图中：第第 i 行行 1 的个数就是顶点的个数就是顶点 i 的出度，的出度，第第 j 列列 1 的个数就是顶点的个数就是顶点 j 的入度。的入度。在无向图中在无向图中,第第 i 行行(列列)1 的个数就是顶点的个数就是顶点i 的度。的度。2022-12-281214320011000010100101(a)(b)图图6-6 有向图及其邻接

9、矩阵有向图及其邻接矩阵 154320010101011001001110010011(a)(b)图图6-5 无向图及其邻接矩阵无向图及其邻接矩阵2022-12-2813 无向图，（无向图，（vi，vj）和（和（vj，vi）表示同一条边，因此，在邻接矩阵中表示同一条边，因此，在邻接矩阵中Aij=Aji。无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。下）的部分表示。对有向图，弧对有向图，弧和和表示方向不同的两条弧，表示方向不同的两条弧，Aij和和Aji表示不同表示不同的弧，所以有向图的邻接矩阵一般

10、不具有对称性。的弧，所以有向图的邻接矩阵一般不具有对称性。邻接矩阵表示法适合于以顶点为主的运算。邻接矩阵表示法适合于以顶点为主的运算。对于有向图，顶点对于有向图，顶点vi的出度的出度OD(vi)等于邻接矩阵第等于邻接矩阵第i行元素之和；顶点行元素之和；顶点vi的入度的入度ID(vi)等于邻接矩阵第等于邻接矩阵第i列元素之和，即列元素之和，即：对于无向图，顶点对于无向图，顶点v vi i的度等于邻接矩阵第的度等于邻接矩阵第i i行的元素之和，即：行的元素之和，即：njjiA1,njijA1,njjiA1,TDTD（v vi i）=2022-12-2814 使用邻接矩阵存储结构，可用一维数组表示图

11、的顶点集合，使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型定义如下：定义如下：#define MAX_VERTICES 50 /最大顶点数最大顶点数typedef int AdjMatrixMAX_VERTICESMAX_VERTICES;/邻接矩阵类型邻接矩阵类型typedef struct VertexType vexsMAX_VERTICES;/顶点表顶点表AdjMatrix arcs;/邻接矩阵邻接矩阵int vexnum,arcnum;/图的顶点数和弧数图的顶点数和弧

12、数 MGraph;由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。疏矩阵，因此会造成一定存储空间的浪费。2022-12-2815建立邻接矩阵算法建立邻接矩阵算法:void CreateMGraph(MGraph&G)int i,j,k,w;char v1,v2;printf(Input vexnum&arcnum:);scanf(%d,%d,&G.vexnum,&G.arcnum);printf(Input Vertices:);scanf(%s,G.vexs);for(i=0;iG.vexnum

13、;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,v2);j=LocateVex(G,v2);void PrintMGraph(MGraph G)/输出输出 int i,j;printf(Output Vertices:);printf(%s,G.vexs);printf(n);

14、printf(Output AdjMatrix:n);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)printf(%4d,G.arcsij);printf(n);return;G.arcsij=w;G.arcsji=w;return;2022-12-2816 图的链式存储结构图的链式存储结构 1)1)为每个顶点建立一个单链表，为每个顶点建立一个单链表，2)2)第第i i个单链表中包含顶点个单链表中包含顶点ViVi的所有邻接顶点。的所有邻接顶点。邻接表是图的一种链式存储结构。在邻接表中为图中每个顶点建立邻接表是图的一种链式存储结构。在邻接表中为图中每个顶点建

15、立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。表示以该顶点为弧尾的一条弧），称为边（或弧）结点。表结点表结点头结点头结点vertexlinkinfodatafirstarc2022-12-28172022-12-28182022-12-2819(a)1304421302143231501234(b)41320212310123(c)143213003201232022-12-28202022-12-2821hlinkhlink指向弧头相同的下一条弧，指向弧头相同的下一条

16、弧，tlinktlink指向弧尾相同的指向弧尾相同的下一条弧；下一条弧；datadata顶点信息，顶点信息，firstinfirstin以该顶点为头的第一个弧结点，以该顶点为头的第一个弧结点，firstoutfirstout以该结点为尾的第一个弧结点以该结点为尾的第一个弧结点headvextailvexhlinktlinkinfofirstindatafirstout顶点结点顶点结点弧结点弧结点2022-12-28224 43 32 21 132312012030103212022-12-28232022-12-2824(a)无向网 (b)有向网 图 6-4 无向带权图和有向带权图 5 3 1

17、 2 4 4 1 6 7 2 3 5 8 A B C 2 1 5 3 4 或弧或弧权权可以代表一个顶点到另一个顶点的距离，耗费等。可以代表一个顶点到另一个顶点的距离，耗费等。一般称为一般称为如图如图6-46-4所示所示 图的基本运算也包括查找、插入和删除。图的基本运算也包括查找、插入和删除。（1 1）顶点定位运算）顶点定位运算 确定顶点确定顶点v v在图中的位置；在图中的位置；（2 2）取顶点运算）取顶点运算 求取图中第求取图中第i i个顶点；个顶点；（3 3）求第一个邻接点运算）求第一个邻接点运算 求图中顶点求图中顶点v v的第一个邻接点；的第一个邻接点；（4 4）求下一个邻接点运算）求下一

18、个邻接点运算 已知已知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以及所有与顶点以及所有与顶点v v相关联的弧。相关联的弧。（8 8）删除弧运算）删除弧运

19、算 从图中删除一条从顶点从图中删除一条从顶点v v到顶点到顶点w w的弧。的弧。2022-12-28262022-12-2827int LocateVex(ALGraph G,char u)int i;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:)

20、;scanf(%d,%d,&G.vexnum,&G.arcnum);printf(Input Vertices:);for(i=0;iG.vexnum;i+)scanf(%c,&G.verticesi.data);G.verticesi.firstarc=NULL;2022-12-2828 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;图的遍历顺序有两种：图的遍历顺序有两种：但是，在图中有回路，从图中某一顶

21、点出发访问图中其它但是，在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中或许还有顶点没有访问顶点时，可能又会回到出发点，而图中或许还有顶点没有访问到，因此，图的遍历较树的遍历更复杂。到，因此，图的遍历较树的遍历更复杂。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。径等算法的基础。1 深度优先搜索思想深度优先搜索思想 深度优先搜索遍历类似于树的先序遍历。假定给定图深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是的初态是所有顶点均未被访问过，在所有顶点均未被访问过，在G中任选一个顶点中任

22、选一个顶点i作为遍历的初始点，作为遍历的初始点，则深度优先搜索则深度优先搜索递归调用包含以下操作：递归调用包含以下操作：（1 1）访问搜索到的未被访问的邻接点；）访问搜索到的未被访问的邻接点；（2 2）将此顶点的）将此顶点的visitedvisited数组元素值置数组元素值置1 1；（3 3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。此邻接点开始进行同样的访问和搜索。深度优先搜索深度优先搜索DFSDFS可描述为：可描述为：（1 1）访问）访问v v0 0顶点；顶点；（2 2）置）置 visitedvv

23、isitedv0 0=1=1；（3）搜索搜索v0未被访问的邻接点未被访问的邻接点w，若存在邻接点若存在邻接点w，则则DFS(w)。17823456(a)int visitedMAX_VERTEX_NUM;void DFS(ALGraph G,int v)ArcNode*p;printf(%c,G.verticesv.data);visitedv=1;p=G.verticesv.firstarc;while(p)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-nextarc;/从第从第v个顶点出发个顶点出发DFS整个图的整个图的DFS遍历遍历void DFSTra

24、verse(ALGraph G)for(int v=0;vG.vexnum;+v)visitedv=0;for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);对于连通图，从一个顶点出发，调用对于连通图，从一个顶点出发，调用DFS函数即可将所有顶点函数即可将所有顶点都遍历到。都遍历到。1 广度优先搜索思想广度优先搜索思想 广度优先搜索遍历类似于树的按层次遍历。广度优先搜索遍历类似于树的按层次遍历。对于无向连通图，广度优先搜索是从图的某个顶点对于无向连通图，广度优先搜索是从图的某个顶点v0出发，在出发，在访问访问v0之后，依次搜索访问之后，依次搜索访问v0的各个未被

25、访问过的邻接点的各个未被访问过的邻接点w1，w2，。然后顺序搜索访问然后顺序搜索访问w1的各未被访问过的邻接点，的各未被访问过的邻接点，w2的各未的各未被访问过的邻接点，被访问过的邻接点，。即从。即从v0开始，由近至远，按层次依次访问开始，由近至远，按层次依次访问与与v0有路径相通且路径长度分别为有路径相通且路径长度分别为1，2，的顶点，直至连通图中的顶点，直至连通图中所有顶点都被访问一次。所有顶点都被访问一次。广度优先搜索的顺序不是唯一的，例如图广度优先搜索的顺序不是唯一的，例如图6-10(a)连通图的广度连通图的广度优先搜索遍历顺序可为优先搜索遍历顺序可为v1，v2，v3，v4，v5，v6

26、，v7，v8 也可为也可为v1，v3，v2，v7，v6，v5，v4，v8。1 广度优先搜索思想广度优先搜索思想 设图设图G的初态是所有顶点均未访问，在的初态是所有顶点均未访问，在G 中任选一顶点中任选一顶点i作为初作为初始点，则广度优先搜索的基本思想是：始点，则广度优先搜索的基本思想是：并将其访问标志置为已并将其访问标志置为已被访问，即被访问，即visitedi=1；依此类推，直到图中所有顶点都被访问完为止依此类推，直到图中所有顶点都被访问完为止。广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出

27、发搜索访问其邻接以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索中需要设置一个队列点。所以在广度优先搜索中需要设置一个队列Queue，使已被访使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点各个邻接点 队列初始化，空队列；队列初始化，空队列；f-队首指针，队首指针，r-队尾指针队尾指针#define MAXV void bfs(ALGraph*g,int v)ArcNode

28、*p;int queueMAXV;/定义存放队列的数组定义存放队列的数组 int visitedMAXV；/定义存放结点的访问标志的数组定义存放结点的访问标志的数组 int f=0,r=0,x,i;/队列头尾指针初始化，把队列置空队列头尾指针初始化，把队列置空 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

29、=queuetf;/出队并赋给出队并赋给x p=g-adjlistx.firstarc;/找与顶点找与顶点x邻接的第一个顶点邻接的第一个顶点 p=g-adjlistx.firstarc;/找与顶点找与顶点x邻接的第一个顶点邻接的第一个顶点 while(p!=NULL)if(visitedp-adjvex=0)/若当前邻接点未被访问若当前邻接点未被访问 visitedp-adjvex=l;/置该顶点已被访问的标志置该顶点已被访问的标志 printf(“d”，p-adjvex);/访问该顶点访问该顶点 r=(r+1)MAXV;queuer=p-adjvex;/该顶点进队该顶点进队 p=p-next

30、arc;/找下一个邻接点找下一个邻接点 /w进队列进队列 2022-12-28436.2.3 连通分支/*程序6-3 求连通分支的算法*/void connected(void)int i;for(i=0;in;i+)if(!visitedi)dfs(i);printf(“n”);17823456(a)17823456(b)17823456(c)在图论中，常常将树定义为一个无回路连通图。一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题。最小生成树的的约束条件：最小生

31、成树的的约束条件：1.只能使用图中的边只能使用图中的边2.只能使用恰好只能使用恰好n-1 条边条边3.只能使用无回路的边只能使用无回路的边所以生成树是连通图中的极小连通子图.不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树 构造最小生成树的算法有很多，下面主要介绍克鲁斯卡尔构造最小生成树的算法有很多，下面主要介绍克鲁斯卡尔(KruskalKruskal)算法和普里姆算法和普里姆(Prim)Prim)算法。算法。克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的

32、方法。造最小生成树的方法。在图中任取一个顶点在图中任取一个顶点K作为开始点，令作为开始点，令U=k，W=V-U，其中其中V为图中所有顶点集，然后找一个顶点在为图中所有顶点集，然后找一个顶点在U中，另一个顶中，另一个顶点在点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入保存起来，并将该边顶点全部加入U集合中，并从集合中，并从W中删去这些顶点，中删去这些顶点，然后重新调整然后重新调整U中顶点到中顶点到W中顶点的距离中顶点的距离,使之保持最小，再重复此过使之保持最小，再重复此过程，直到程，直到W为空集止。

33、为空集止。T=While(T contains less than n-1 edges&E is not empty)choose a least cost edge(v,w)from E;delete(v,w)from E;if(v,w)does not create a cycle in T)add(v,w)to T;else discard(v,w);If(T contains fewer than n-1 edges)printf(“No spanning treen”);如果给定带权无向连通图如果给定带权无向连通图G G有有e e条边，且边已经按权值递增的次序存条边，且边已经按权值递

34、增的次序存放在数组放在数组E E中，则用克鲁斯卡尔算法构造最小生成树的时间复杂度为中，则用克鲁斯卡尔算法构造最小生成树的时间复杂度为O O(e)(e)。克鲁斯卡尔算法的时间复杂度与边数克鲁斯卡尔算法的时间复杂度与边数e e有关，该算法适合于求边数有关，该算法适合于求边数较少的带权无向连通图的最小生成树。较少的带权无向连通图的最小生成树。为实现克鲁斯卡尔算法需设置一维辅助数组为实现克鲁斯卡尔算法需设置一维辅助数组E E，按权值从小到大的顺序存按权值从小到大的顺序存放图的边，数组的下标取值从放图的边，数组的下标取值从0 0到到e-1e-1（e e为图为图G G边的数目）。假设数组边的数目）。假设数

35、组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;Void kruskal(Edge E,int n,int e)int i,j,m1,m2,sn1,sn2,k;int vsetMAXV;for(i

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

37、printf(“(m1，m2)：dn”,Ej.weight);k+;/生成边数增生成边数增l for(i=0;in;i+)/两个集合统一编号两个集合统一编号 if(vseti=/集合编号为集合编号为sn2的改为的改为sn1 vseti=sn1;j+;/扫描下一条边扫描下一条边 2022-12-2852Sollin 算法：教材算法：教材P183 初始状态同前图，此时森林中每个棵树是单独一个顶点。下一步为每初始状态同前图，此时森林中每个棵树是单独一个顶点。下一步为每个顶点选边，分别是：个顶点选边，分别是：(0,5),(1,6),(2,3),(3,2),(4,3),(5,0),(6,1)去掉重复的去

38、掉重复的边后：边后：(0,5),(1,6),(2,3),(4,3)得到得到a)森林，再加上森林，再加上(5,4),(1,2)得到得到b)图图:交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通连通?在有多条通路的情况下，哪一条路最短在有多条通路的情况下，哪一条路最短?若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路接通路(从其它顶点达到从其它顶点达到)。路径上的开始顶点。路径上的开始顶点(出发点出发点)称为源点，路称为源点，路径上的最后一个顶点称为终点，并假定

39、讨论的权值不能为负数。径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。迪杰斯特拉迪杰斯特拉 单源点最短路径是指：给定一个出发点单源点最短路径是指：给定一个出发点(单源点单源点)和一个有向网和一个有向网G=(VG=(V，E),E),求出源点到其它各顶点之间的最短路径。求出源点到其它各顶点之间的最短路径。迪杰斯特拉迪杰斯特拉(DijkstraDijkstra)在做了大量观察后在做了大量观察后,首先提出了按路径长首先提出了按路径长度递增产生各顶点的最短路径算法度递增产生各顶点的最短路径算法,我们称之为我们称之为迪杰斯特拉算法迪杰斯特拉算法。算法的基本思想是算法的基本思想是:设置并逐步扩充一个

40、集合设置并逐步扩充一个集合S S，存放已求出其存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是最短路径的顶点，则尚未确定最短路径的顶点集合是V-SV-S，其中其中V V为网中所有顶点集合。按最短路径长度递增的顺序逐个以为网中所有顶点集合。按最短路径长度递增的顺序逐个以V-SV-S中的中的顶点加到顶点加到S S中，直到中，直到S S中包含全部顶点，而中包含全部顶点，而V-SV-S为空。为空。具体做法是具体做法是:设源点为设源点为V0,V0,则则S S中只包含顶点中只包含顶点V0V0，令令W=V-SW=V-S，则则W W中包含除中包含除V0V0外图中所有顶点，外图中所有顶点，V0V0对应

41、的距离值为对应的距离值为0 0，W W中顶点对中顶点对应的距离值是这样规定的：若图中有弧应的距离值是这样规定的：若图中有弧 V0,Vj则则VjVj顶点的距离顶点的距离为此弧权值，否则为为此弧权值，否则为(一个很大的数一个很大的数)，然后每次从，然后每次从W W中的顶点中的顶点中选一个其距离值为最小的顶点中选一个其距离值为最小的顶点VmVm加入到加入到S S中，每往中，每往S S中加入一个中加入一个顶点顶点VmVm，就要对就要对W W中的各个顶点的距离值进行一次修改。若加进中的各个顶点的距离值进行一次修改。若加进VmVm做中间顶点，使做中间顶点，使+的值小于的值小于 V0,Vj值，则用值，则用+

42、代替原来代替原来VjVj的距离，修改后再在的距离，修改后再在W W中选距离值最中选距离值最小的顶点加入到小的顶点加入到S S中，如此进行下去，直到中，如此进行下去，直到S S中包含了图中所有顶中包含了图中所有顶点为止。点为止。实现的算法：实现的算法：P185 P185 程序程序6-9,6-10,6-116-9,6-10,6-112022-12-2858图图6-16 带权有向图带权有向图 5320411001020505103060从以上图从以上图6-166-16的最短路径可以看出：的最短路径可以看出：1)1)最短路径并不一定是经过边或弧数最少的路径。最短路径并不一定是经过边或弧数最少的路径。如

43、从顶点如从顶点0 0到顶点到顶点5 5的路径（的路径（0 0，5 5）长度为）长度为100100，路径（路径（0 0，4 4，5 5）长度为）长度为9090，路径（，路径（0 0，2 2，3 3，5 5）长度为）长度为7070，路径（，路径（0 0，4 4 ，3 3，5 5）长度为）长度为6060，其中最短路径为（，其中最短路径为（0 0，4 4，3 3，5 5），最短路径长度为），最短路径长度为6060。2)2)这些最短路径中，长度最短的路径上只有一条弧，且它的权值在从源点这些最短路径中，长度最短的路径上只有一条弧，且它的权值在从源点出发的所有弧的权值中最小。如从源点出发的所有弧的权值中最小

44、。如从源点0 0出发有出发有3 3条弧，其中以弧条弧，其中以弧02的权值为最小。此时（的权值为最小。此时（0 0，2 2）不仅是顶点）不仅是顶点 0 0到顶点到顶点2 2 的一条最短路的一条最短路径，而且它在从源点径，而且它在从源点0 0到其它各顶点的最短路径中长度最短。到其它各顶点的最短路径中长度最短。3)3)按照路径长度递增的次序产生最短路径。求得第二条最短路径（按照路径长度递增的次序产生最短路径。求得第二条最短路径（0 0，4 4）；）；之后求得第三条最短路径（之后求得第三条最短路径（0 0，4 4，3 3），它经过已求出的第二条最短路），它经过已求出的第二条最短路径（径（0 0，4 4

45、）到达顶点）到达顶点3 3；求得的第四条最短路径（；求得的第四条最短路径（0 0，4 4，3 3，5 5），经过），经过已求出的第三条最短路径（已求出的第三条最短路径（0 0，4 4，3 3）到达顶点）到达顶点5 5。5320411001020505103060迪杰斯特拉迪杰斯特拉算法的求解过程：算法的求解过程：10 3 5 20 8 25 4 30 3 30 1 2 3 5 4 (a)一个有向网点 (b)源点 1 到其它顶点的初始距离 1 2 3 5 4 12 3 8 25 30 1 2 3 5 4(c)第一次求得的结果 (d)第二次求得的结果 3 8 12 4 1 2 3 5 4 3 8

46、12 4 3 8 12 4(e)第三次求得的结果 (f)第四次求得的结果 1 2 3 5 4 1 2 3 5 4 图图6-17 迪杰斯特拉算法求最短路径过程及结果迪杰斯特拉算法求最短路径过程及结果 在狄克斯特拉算法中，求一条最短路径所花费的时间：从在狄克斯特拉算法中，求一条最短路径所花费的时间：从V-S中选取具有最小距离的顶点中选取具有最小距离的顶点v k花费时间花费时间O(n)；修改修改V-S中顶点的距中顶点的距离花费时间离花费时间O(n)；输出最短路径花费时间输出最短路径花费时间O(n)。因此求出因此求出n-1条最条最短路径的时间复杂度为短路径的时间复杂度为O(n2)。顶点对之间的最短路径

47、是指：对于给定的有向网顶点对之间的最短路径是指：对于给定的有向网G=(V,E),G=(V,E),对对G G中任意一对顶点有序对中任意一对顶点有序对V V、W(VW),W(VW),找出找出V V到到W W和和W W到到V V的最短距离。的最短距离。解决此问题的一个有效方法是解决此问题的一个有效方法是:轮流以每一个顶点为源点轮流以每一个顶点为源点,重复执重复执行迪杰斯特拉算法行迪杰斯特拉算法n n次次,即可求得每一对顶点之间的最短路径即可求得每一对顶点之间的最短路径,总的总的时间复杂度为时间复杂度为O(nO(n3 3)带权的邻接矩阵来存储表示图带权的邻接矩阵来存储表示图G G，若，若i=i=j,c

48、ostijj,costij=0,=0,右右 ijij不在不在G G中则设置中则设置costijcostij 为一个充分大的数。为一个充分大的数。令令A A(k)(k)ijij 表示从顶点表示从顶点i i出发，只经过序号小于等于出发，只经过序号小于等于k k的中间的中间顶点顶点,到达顶点到达顶点j j的最距离。的最距离。A(k)ij=minA(k-1)ij,A(k-1)ik+A(k-1)kj 其中其中 k=1,2,n例例6-5 下图给出了一个有向图及其代价邻接矩阵下图给出了一个有向图及其代价邻接矩阵A-1，对于这个图：对于这个图：A(1)02 不等于不等于 minA(1)02,A(0)01+A(

49、0)12，实际上，实际上A(1)02=-程序程序6-12 所有顶点对之间的最短路径算法所有顶点对之间的最短路径算法 void allcosts(int cost max_vertices,int distancemax_verticers,int n)int i,j,k;for(i=0;in;i+)for(j=0;jn;j+)distanceij=costij;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jn;j+)if(distanceik+distancekjdistanceij)distanceij)=distanceik+distancekj;通常我们把计划

50、、施工过程、生产流程、程序流程等都当成通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这一个工程，一个大的工程常常被划分成许多较小的子工程，这些些子工程称为活动子工程称为活动。这些活动完成时，整个工程也就完成了。这些活动完成时，整个工程也就完成了。例如，计算机专业学生的课程开设可看成是一个工程，每一例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图门课程就是工程中的活动，图7-217-21给出了若干门所开设的课程，给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先其中有些课程的开设