数据结构07图

1、2022-3-261本章主要介绍本章主要介绍图图的基本概念、图的存储结构和有关的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该：图的一些常用算法。通过本章学习，读者应该： 1) 了解图的定义和术语了解图的定义和术语 2) 掌握图的各种存储结构掌握图的各种存储结构 3) 掌握图的掌握图的深度优先搜索深度优先搜索和和广度优先搜索广度优先搜索遍历算法遍历算法 4) 理解理解最小生成树、最短路径、拓扑排序、关键路最小生成树、最短路径、拓扑排序、关键路径径等图的常用算法等图的常用算法 2022-3-262 图图（GraphGraph）是一种较线性表和树更为复杂的是一种较线性表和树更

2、为复杂的非线性结构非线性结构。是是对结点的前趋和后继对结点的前趋和后继个数不加限制个数不加限制的数据结构，用来的数据结构，用来描述元素之描述元素之间间“多对多多对多”的关系。的关系。 在在线性结构线性结构中，结点之间的关系是中，结点之间的关系是线性关系线性关系，除开始结点和，除开始结点和 终端结点外，每个结点只有一个直接前趋和直接后继。终端结点外，每个结点只有一个直接前趋和直接后继。 在在树形结构树形结构中，结点之间的关系实质上是中，结点之间的关系实质上是层次关系层次关系，同层上，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但的每个结点可以和下一层的零个或多个结点（即孩子）相关

3、，但只能和上一层的一个结点（即双亲）相关（根结点除外）。只能和上一层的一个结点（即双亲）相关（根结点除外）。 在在图结构图结构中，对结点（图中常称为顶点）的前趋和后继个数中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是不加限制的，即结点之间的关系是任意的任意的。 由此，图的应用极为广泛，特别是近年来的迅速发展，已渗由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。以及数学的其它分支中。2022-3-263 第七章第七章 图图2022-

4、3-264v 图图定义定义 图图G由两个集合由两个集合V和和E组成，记为组成，记为 G = ( V , E ) 其中，其中， V是顶点的有穷非空集合，是顶点的有穷非空集合， E是是V中顶点偶对的有穷集，中顶点偶对的有穷集，这些顶点偶对称为边。通常这些顶点偶对称为边。通常V(G)和和E(G)分别称分别称为图的为图的顶点集合顶点集合和和边集合边集合。注注： E(G)可以为空集。可以为空集。2022-3-265v 图的数据结构的图的数据结构的形式化定义形式化定义 （p156） G = ( V , E ) 其中其中 V = x | x dataobject E =VR VR=| p(x,y) ( x

5、, y V ) VR是两顶点间的关系的集合，即边的是两顶点间的关系的集合，即边的集合。集合。2022-3-266G1G1=（V，E） V=v1, v2, v3, v4E=, , , 其中其中表示从表示从x到到y的一条弧（的一条弧（arc），），A为为弧集合，弧集合，x为弧尾（为弧尾（tail），），y为弧头（为弧头（head)x弧尾y弧头2022-3-267G2 G2=（V，E） V=v1, v2, v3, v4, v5E=(v1, v2), (v1, v3), (v2, v3), (v3, v4), (v2,v5), (v3,v5)其中，其中，(x, y)表示表示x与与y之间的一条连线，称为

6、边之间的一条连线，称为边（edge）2022-3-268图的图的术语术语设设n为顶点数，为顶点数，e为边或弧的条数为边或弧的条数 对对无向图无向图有：有：0 e n(n-1)/2 有向图有向图有：有：0 e n(n-1)证明证明：对有向图，每个：对有向图，每个顶点至多有顶点至多有n-1条边与其它的条边与其它的n-1个个顶点相连顶点相连，则，则n个顶点至多有个顶点至多有n(n-1)条边条边。但对无向图，但对无向图，每每条条边连接边连接2个顶点，故最多为个顶点，故最多为n(n-1)/22022-3-269在一个无向图中，若存在一条边在一个无向图中，若存在一条边v, , 则称则称v vi i，v v

7、j j为该边的两个为该边的两个端点端点，并称它们，并称它们互为互为邻结点邻结点。21453G22022-3-2610在一个有向图中，若存在一条边在一个有向图中，若存在一条边 , , 则称该边则称该边是顶点是顶点v vi i的一条出边，是的一条出边，是v vj j的一条入边，称的一条入边，称v vi i是起是起始端点（或起点），称始端点（或起点），称v vj j是终止端点（或终点）是终止端点（或终点）, ,并称它们并称它们互为邻结点互为邻结点. .2134G12022-3-2611图中每个顶点的图中每个顶点的度是以度是以该顶点为一端点的边的数目。该顶点为一端点的边的数目。记为记为 D(V) 。对

8、于有向图，入度为以该顶点为终点的对于有向图，入度为以该顶点为终点的边的数目，出度为以该顶点为起点的边的边的数目，出度为以该顶点为起点的边的数目。数目。例例 D(v1)=3 无向图的度数为依附于顶点无向图的度数为依附于顶点v的边数；有向图的度数等于以的边数；有向图的度数等于以顶点顶点v 为弧头的弧数与以顶点为弧头的弧数与以顶点v为弧尾的弧数之和为弧尾的弧数之和21453G22134G1例例 D(v1)=2 2022-3-2612设有两个图设有两个图G=（V，E） G=（V，E）中，若中，若V是是V的子集，的子集， E是是E的子集，则称的子集，则称G是是G子图。子图。 G2 2022-3-2613

9、对不含多重边和自环的图。对不含多重边和自环的图。21453214532022-3-2614图的图的术语术语 边达到最大的图边达到最大的图 无向完全图：无向完全图：具有具有条边的简单图条边的简单图称为无向完全图称为无向完全图 有向完全图：有向完全图：具有具有条边的有向图。条边的有向图。 稀疏图：稀疏图： 边或弧很少的图。边或弧很少的图。 稠密图：稠密图： 边或弧很多的图。边或弧很多的图。 权：权：与图的边或弧相关的数。与图的边或弧相关的数。 网：网：边或弧上带有权值的图。边或弧上带有权值的图。2022-3-2615非空有限非空有限点、弧交替点、弧交替序列，序列， W=v0, a1,v1, , a

10、k,vk 使得使得i=1,2,k , 弧弧ai的头的头vi , 尾为尾为vi-1 。 路径长度：路径长度：路径上边或弧的数目路径上边或弧的数目2022-3-2616：除首尾两点外，其他各点都不除首尾两点外，其他各点都不相同的路径称为简单路径。相同的路径称为简单路径。简单路径简单路径2022-3-2617回路回路:无重复边的闭路径。无重复边的闭路径。环：环：闭的简单路径，称为环。闭的简单路径，称为环。但不是但不是环环环环2022-3-2618任何两点都有路径的图。任何两点都有路径的图。若图中任意两个顶点若图中任意两个顶点vi,vj都是连通都是连通 的，则称该图是的，则称该图是连通图连通图(viv

11、j)若图中任意两个顶点若图中任意两个顶点vi,vj，都存在，都存在 从从vi到到vj 和从和从 vj到到vi的路径，则称的路径，则称 该有向图为该有向图为强连通图强连通图 (vivj)2022-3-2619无向图中极大连通子图，称为无向图中极大连通子图，称为 连通分量连通分量有向图中极大强连通子图，称为有向图中极大强连通子图，称为 强连通分量强连通分量2022-3-2620生成树生成树一个连通图的生成树是一个极小连通子图一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵，它含有图中全部顶点，但只有足以构成一棵树的树的n-1n-1条边。条边。 如果一个有向图恰有一个顶点

12、入度为如果一个有向图恰有一个顶点入度为0 0，其余顶点的入度均为其余顶点的入度均为1 1，则是一棵有向树。，则是一棵有向树。2022-3-2621 非连通图非连通图的生成树则组成一个的生成树则组成一个生成森林生成森林。若图中有。若图中有n n个个顶点，顶点，m m个连通分量，则生成森林中有个连通分量，则生成森林中有n-mn-m条边。条边。 一个有向图的一个有向图的生成森林生成森林由若干棵有向树组成，含有图由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧中全部顶点，但只有足以构成若干棵不相交的有向树的弧。2022-3-26222022-3-2623 邻接矩阵邻接矩阵(

13、Adjacency Matrix)是表示顶点之间相邻关系的是表示顶点之间相邻关系的矩阵。设矩阵。设G(V，E)是具有是具有n个顶点的图，则个顶点的图，则G的邻接矩阵的邻接矩阵是具有如下性质的是具有如下性质的n阶方阵。阶方阵。Aij=1 对无向图若存在边(vi,vj),对有向图若存在弧0 反之无向图无向图的邻接矩阵是以的邻接矩阵是以主对角线对称主对角线对称的，的，有向图有向图的邻接矩的邻接矩阵阵可能可能是是不对称不对称的。的。 在有向图中：在有向图中： 第第 i 行行 1 的个数就是顶点的个数就是顶点 i 的出度，的出度， 第第 j 列列 1 的个数就是顶点的个数就是顶点 j 的入度。的入度。

14、在无向图中在无向图中, 第第 i 行行 (列列) 1 的个数就是顶点的个数就是顶点i 的度。的度。2022-3-2624例如：例如：G1的邻接矩阵的邻接矩阵例如：例如：G2的邻接矩阵的邻接矩阵无向图的邻接矩阵为对称矩阵无向图的邻接矩阵为对称矩阵G212345G1123400011000000001101G00110001011101010101010102G2022-3-2625 对于对于无向图无向图，（，（vi，vj）和（和（vj，vi）表示同一条边，因表示同一条边，因此，在邻接矩阵中此，在邻接矩阵中Aij=Aji。 无向图的邻接矩阵是（关于主对角线）无向图的邻接矩阵是（关于主对角线）对称矩

15、阵对称矩阵，可用，可用主对角线以上（或以下）的部分表示。主对角线以上（或以下）的部分表示。 对对有向图有向图，弧，弧和和表示方向不同的两条弧，表示方向不同的两条弧，Aij和和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。称性。 邻接矩阵表示法邻接矩阵表示法适合于适合于以顶点为主的运算以顶点为主的运算。 2022-3-2626对于对于有向图有向图，顶点，顶点vi的的出度出度OD (vi)等于邻接矩阵第等于邻接矩阵第i行行元素之和；顶点元素之和；顶点vi的的入度入度ID (vi)等于邻接矩阵第等于邻接矩阵第i列元素之列元素之和，即和，即 ：

16、 对于对于无向图无向图，顶点，顶点v vi i的度的度等于邻接矩阵第等于邻接矩阵第i i行的元素之和，行的元素之和，即：即： njjiA1,njjiA1,njijA1,TDTD（v vi i）= =2022-3-2627V2V1V3V435214 Wij 若若 或或 E(G)A i，j = 0或 若其它若其它150000000423AV1 V2 V3 V4V1 V2 V3 V42022-3-2628 使用邻接矩阵存储结构，可用使用邻接矩阵存储结构，可用一维数组一维数组表示图的表示图的顶点集合顶点集合，用用二维数组二维数组表示图的顶点之间关系（表示图的顶点之间关系（边或弧）的集合边或弧）的集合，

17、数据类型，数据类型定义如下：定义如下： #define MAX_VERTEX_NUM 20 /最大顶点数最大顶点数typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /邻接矩阵类型邻接矩阵类型typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点表顶点表AdjMatrix arcs; /邻接矩阵邻接矩阵int vexnum， arcnum; /图的顶点数和弧数图的顶点数和弧数 MGraph; 由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩

18、阵，因此会造成一定存储空间的浪费。稀疏矩阵，因此会造成一定存储空间的浪费。 2022-3-2629 图的图的链式存储结构链式存储结构 1) 1) 为每个顶点建立一个单链表，为每个顶点建立一个单链表， 2) 2) 第第i i个单链表中包含顶点个单链表中包含顶点ViVi的所有邻接顶点。的所有邻接顶点。邻接表邻接表是图的一种链式存储结构。是图的一种链式存储结构。类似于树的孩子链表类似于树的孩子链表表示法。表示法。在邻接表中为图中每个顶点建立一个单链表，用在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶

19、点为弧尾的一条弧），称为以该顶点为弧尾的一条弧），称为边（或弧）结点边（或弧）结点。2022-3-26302022-3-26312022-3-263225341543533412212123451. 1. 无向图无向图邻接表邻接表二、邻接表二、邻接表G212345adjvex nextarcvexdata firstarc2022-3-26331. 1. 无向图邻接表无向图邻接表对图中对图中每个顶点每个顶点Vi建立一个单链表，链建立一个单链表，链表中的结点表示依附于顶点表中的结点表示依附于顶点Vi的边，每的边，每个链表结点为两个域个链表结点为两个域.其中：其中：邻接点域（邻接点域（adjvex

20、）记载与顶点记载与顶点Vi邻接的顶点信息；邻接的顶点信息； 链域（链域（nextarc）指向下一个与顶点指向下一个与顶点Vi邻接邻接的链表的链表p结点结点每个链表设一个每个链表设一个头结点头结点，头结点头结点结构结构为：为：其中：其中：vexdata存放顶点信息（姓名、编号等）；存放顶点信息（姓名、编号等）； firstarc指向链表的第一个结点。指向链表的第一个结点。二、邻接表二、邻接表adjvex nextarcvexdata firstarc2022-3-26342534154353341221212345G2123452022-3-2635BACDFE例例 20 A 1 41 B 0

21、4 52 C 3 53 D 2 54 E 0 15 F 1 2 32022-3-26362341431212341. n个顶点，个顶点，e条弧的有向图，需条弧的有向图，需n个表头结点，个表头结点，e 个表结点个表结点 2. 第第 i 条链表上的结点数，为条链表上的结点数，为 Vi 的出度的出度如图如图G1的邻接表为：的邻接表为：G112342022-3-26371 4230 120 1 2 3 4 A B C D E2.有向图有向图的邻接表的邻接表ABECF可见，在有向图的可见，在有向图的邻接表中邻接表中不易不易找到找到指向该顶点的弧。指向该顶点的弧。2022-3-26383 31234114

22、31234如图如图G1G1的的逆邻接逆邻接表为：表为：G12022-3-2639ABECD有向图的有向图的逆邻接表逆邻接表A B C D E 303420 01234在有向图的在有向图的邻接表邻接表中，对每中，对每个顶点，个顶点，链接的是指向该顶链接的是指向该顶点的弧。点的弧。2022-3-2640链表中每个结点为链表中每个结点为三个域三个域. 邻接点邻接点 权权2022-3-2641ABECD4.A B C D E 012341 10 3 7 0 4 4 22 3 2 8 1022548371 25 2022-3-2642hlinkhlink指向弧头相同的下一条弧，指向弧头相同的下一条弧，t

23、linktlink指向弧尾相同的指向弧尾相同的下一条弧；下一条弧；datadata顶点信息，顶点信息，firstinfirstin以该顶点为头的第一个弧结点，以该顶点为头的第一个弧结点，firstoutfirstout以该结点为尾的第一个弧结点。以该结点为尾的第一个弧结点。 起点起点vi 终点终点vj hlink tlink弧弧结构结构顶点结构顶点结构 data firstin firstout2022-3-2643432132312012030103212022-3-26442022-3-2645markivex ilinkjvexjlinkdatafirstedge2022-3-26462

24、301154323441201304321图图7-9为图为图7-5 (a)无向图的无向图的邻接多重表邻接多重表。2022-3-26472022-3-2648 图的遍历远比树的遍历复杂。因为从树根到达树的某个图的遍历远比树的遍历复杂。因为从树根到达树的某个结点只有一条路径，而图的两个顶点之间可能有多条路径结点只有一条路径，而图的两个顶点之间可能有多条路径。 因此，在图的遍历过程中，可能会出现下面的现象，即在因此，在图的遍历过程中，可能会出现下面的现象，即在顺着一条路径访问了某个顶点后，可能会沿着另一条路径又回顺着一条路径访问了某个顶点后，可能会沿着另一条路径又回到该顶点。到该顶点。 为避免一个顶

25、点被多次访问为避免一个顶点被多次访问，我们设置一个标志数组，我们设置一个标志数组int visitedMAX_VERTEX_NUM;它的元素初值为它的元素初值为0 0。一旦。一旦v vi i被访问了，便置相应数组元素为被访问了，便置相应数组元素为1.1. 图的图的遍历方法遍历方法有：有：这两种方法对无向图和有向图都适用。这两种方法对无向图和有向图都适用。 深度优先搜索遍历（简称深度优先搜索遍历（简称DFS）广度优先搜索遍历（简称广度优先搜索遍历（简称BFS）2022-3-26491 深度优先搜索深度优先搜索2022-3-26502022-3-265117823456(a)2022-3-2652

26、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个顶点出发个顶点出发DFS2022-3-2653整个图的整个图的DFS遍历遍历void DFSTraverse(ALGraph G) for (int v=0;vG.vexnum;+v) visited

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

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

29、，v5，v4，v8。 2022-3-2655广度优先搜索在搜索访问一层时，需要记住已被访问的广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索中访问其邻接点。所以在广度优先搜索中需要设置需要设置一个一个队列队列Queue，使已被访问的顶点顺序由队尾进入队列使已被访问的顶点顺序由队尾进入队列。在搜索访。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点从该顶点出发搜索访

30、问它的各个邻接点 2022-3-2656队列初始化，空队列；队列初始化，空队列；f-队首指针，队首指针，r-队尾指针队尾指针2022-3-2657 void BFSseach(Graph G, int Visited ,int n) for (v=0; vn; +v) visitedv = 0; /初始化访问标志初始化访问标志 InitQueue(Q); / 置空的辅助队列置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未访问尚未访问 visitedv = 1; Visit(v); / 访问访问u EnQueue(Q, v);

31、/ v入队列入队列 while (!QueueEmpty(Q) u=DeQueue(Q, u); / 队头元素出队并置为队头元素出队并置为u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=1; Visit(w); EnQueue(Q, w); / 访问的顶点访问的顶点w入队列入队列 / if / while / BFSTraverse2022-3-2658课堂练习课堂练习练习练习1、写出右图的邻接矩阵表示。、写出右图的邻接矩阵表示。vexs A 0B1C 2D 3E4F5ABCDEFar

32、cs011000100111000001000000000100000010ACBDEF2022-3-2659课堂练习课堂练习练习练习2、写出右图的邻接表表示。、写出右图的邻接表表示。ACBDEF543210FEDCBA 1 2 0 4 5 3 5 3 42022-3-2660课堂练习课堂练习练习练习3、根据右图的如下存储表示，写出以顶点、根据右图的如下存储表示，写出以顶点A为出发点为出发点进行进行DFS的顶点访问序列。的顶点访问序列。ACBDEF543210FEDCBA 1 2 0 4 5 3 5 3 4A，B，D，E，F，C2022-3-2661课堂练习课堂练习ACBDEF543210FE

33、DCBA 1 2 0 4 5 3 5 3 4A，B，C，D，E，F练习练习4、根据右图的如下存储表示，写出以顶点、根据右图的如下存储表示，写出以顶点A为出发点为出发点进行进行BFS的顶点访问序列。的顶点访问序列。2022-3-26622022-3-26632022-3-2664252510504613228102514242216185046132504613210原图 (a) (b)504613210(c) (d) (e) (f)504613210221250461210251422161232522122022-3-2665504613228102514242216181202810280

34、161416012120221822025241025014182402022-3-26660 28 10 - -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 6028102801614160121202218220252410250141824050461322810251424221618122022-3-26672022-3-26680 28 10 - -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 6选选 v=5选边选边 (0,5)02810280161416012120221822025241025014182402

35、022-3-2669顶点顶点v=5加入生成树顶点集合：加入生成树顶点集合：0 28 25 10 - -1 0 0 0 5 - -1 0 lowcostnearvex0 1 2 3 4 5 6选选 v=4选边选边 (5,4)50461322810251424221618原图 边 (0,5,10) 加入生成树12046132102552022-3-26700 1 2 3 4 5 6顶点顶点v=4加入生成树顶点集合：加入生成树顶点集合：0 28 22 25 10 24 - -1 0 0 4 - -1 - -1 4 lowcostnearvex选选 v=3选边选边 (4,3)5046132281025

36、1424221618原图 边 (5,4,25) 加入生成树1250461321025222022-3-2671顶点顶点v=3加入生成树顶点集合：加入生成树顶点集合：0 28 12 22 25 10 18 - -1 0 3 - -1 - -1 - -1 3 lowcostnearvex0 1 2 3 4 5 6选选 v=2选边选边 (3,2)50461322810251424221618原图 边 (4,3,22) 加入生成树125046132102522122022-3-2672lowcostnearvex0 1 2 3 4 5 6顶点顶点v=2加入生成树顶点集合：加入生成树顶点集合：0 16

37、12 22 25 10 18 - -1 2 - -1 - -1 - -1 - -1 3 选选 v=1选边选边 (2,1)50461322810251424221618原图 边 (3,2,12) 加入生成树1250413210252216122022-3-2673顶点顶点v=1加入生成树顶点集合：加入生成树顶点集合：0 16 12 22 25 10 14 - -1 - -1 - -1 - -1 - -1 - -1 1 lowcostnearvex0 1 2 3 4 5 6选选 v=6选边选边 (1,6)50461322810251424221618原图 边 (2,1,16) 加入生成树12504

38、61321025142216122022-3-2674lowcostnearvex0 1 2 3 4 5 6顶点顶点v=6加入生成树顶点集合：加入生成树顶点集合：0 16 12 22 25 10 14 - -1 - -1 - -1 - -1 - -1 - -1 - -1 50461322810251424221618 原图 边 (1,6,14) 加入生成树125046132102514221612(0, 5, 10), (5, 4, 25), (4, 3, 22),(3, 2, 12), (2, 1, 16), (1, 6, 14)2022-3-26752022-3-2676typedef i

39、nt 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-3-2677closedgek.lowcost=0; for (i=1;iG.vexnum;+i) k=minimum(clo

40、sedge); 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; closedgej.lowcost=

41、G.arcskj; 2022-3-2678普里姆算法中的第二个普里姆算法中的第二个forfor循环语句频度为循环语句频度为n-1n-1，其中包含的两个内循环频度也都为其中包含的两个内循环频度也都为n-1n-1，因此普里因此普里姆算法的姆算法的时间复杂度时间复杂度为为O(nO(n2 2) )。普里姆算法的时间普里姆算法的时间复杂度与边数复杂度与边数e e无关，该算法无关，该算法更适合于更适合于求边数较多求边数较多的的带权无向连通图的最小生成树。带权无向连通图的最小生成树。 2022-3-26792022-3-26801050461322810251424221618125046132504613

42、2原图 (a) (b)2022-3-26811012504613228102514242216181250461325046132101412原图 (c) (d)504613210141612(e) (f) (g)5046132101422161250461210251422161232022-3-2682为实现克鲁斯卡尔算法需要设置一维辅助数组为实现克鲁斯卡尔算法需要设置一维辅助数组E E，按权值从按权值从小到大的顺序存放图的边，数组的下标取值从小到大的顺序存放图的边，数组的下标取值从0 0到到e-1e-1（e e为为图图G G边的数目）。边的数目）。 了解了解-假设数组假设数组E E存放图

43、存放图G G中的所有边，且边已按权值从小中的所有边，且边已按权值从小到大的顺序排列。到大的顺序排列。n n为图为图G G的顶点个数，的顶点个数，e e为图为图G G的边数。克鲁的边数。克鲁斯卡尔算法如下：斯卡尔算法如下：#define MAXE #define MAXV typedef struct int vex1; /边的起始顶点边的起始顶点int vex2; /边的终止顶点边的终止顶点int weight; /边的权值边的权值Edge; 2022-3-2683 Void kruskal(Edge E,int n,int e) int i,j,m1,m2,sn1,sn2,k; int vs

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

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

46、复杂度为为O(eO(e) )。克鲁斯卡尔算法的时间复杂度与边克鲁斯卡尔算法的时间复杂度与边数数e e有关，该算法有关，该算法适合于适合于求求边数较少的带权无向连通图边数较少的带权无向连通图的最小的最小生成树。生成树。 2022-3-26852022-3-26862022-3-26872022-3-26882022-3-26892022-3-26902022-3-26912022-3-26922022-3-26932022-3-26942022-3-26952022-3-26962022-3-2697 在实现拓扑排序的算法中，采用在实现拓扑排序的算法中，采用邻接表邻接表作为有向图的存储作为有向图

47、的存储结构，每个顶点设置一个结构，每个顶点设置一个单链表单链表，每个单链表有一个表头结，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域点，在表头结点中增加一个存放顶点入度的域countcount，这些表这些表头结点构成一个数组，头结点构成一个数组，表头结点定义表头结点定义如下：如下：typedef struct /表头结点表头结点 Vertex data; /顶点信息顶点信息 int count; /存放顶点入度存放顶点入度 ArcNode *firstarc; /指向第一条弧指向第一条弧Vnode;2022-3-2698 void topsort(VNode adj,int

48、n) int i,j; int stackMAXV,top=0; /栈栈stack的指针为的指针为top ArcNode *p; for(i=0;i0) /栈不为空栈不为空 i=stacktop; top-; /顶点顶点vi出栈出栈 printf(“d”,i); /输出输出vi p=adji.firstarc; /指向以指向以vi为弧尾的第一条弧为弧尾的第一条弧 while(p!=NULL) j=p-adjvex; /以以vi为弧尾的弧的另一顶点为弧尾的弧的另一顶点vj 2022-3-2699 while(p!=NULL) j=p-adjvex; /以以vi为弧尾的弧的另一顶点为弧尾的弧的另一

49、顶点vj adjj.count-; /顶点顶点vj的入度减的入度减1 if(adjj.count=0) /入度为入度为0的相邻顶点入栈的相邻顶点入栈 top+; stacktop=j; p=p-nextarc; /指向以指向以vi为弧尾的下一条弧为弧尾的下一条弧 2022-3-26100网中只有：唯一一个入度为网中只有：唯一一个入度为0 0的点的点 源点源点 唯一一个出度为唯一一个出度为0 0的点的点 汇点汇点7.5.2 关键路径关键路径2022-3-261012022-3-26102为头的弧的集合是所有以其中jTnjTjijidutiVeMaxjVei2 ,),()()(为尾的弧的集合是所有

50、以其中iSniSjijidutjVlMiniVlj11 ,),()()(Ve(j) = 从源点到顶点从源点到顶点j的最长路径长度；的最长路径长度；Vl(k) = 从顶点从顶点k到汇点的最短路径长度。到汇点的最短路径长度。2022-3-261032022-3-261042022-3-261052022-3-26106void CriticalPath (ALGraph G) int i, j, k, e, l;int *Ve,*Vl;ArcNode *p; Ve = new intG.vexnum; Vl = new intG.vexnum; for ( i = 0; i G.vexnum; i

51、+ ) Vei = 0; for ( i = 0; i adjvex; if (Vei + p-info Vek) Vek = Vei + p-info; p = p-nextarc; 2022-3-26107 for ( i = 0; i adjvex; if ( Vlk - p-info info; p = p-nextarc; 2022-3-26108【例例7-4】图】图7-29是一个具有是一个具有8个活动和个活动和6个事件的个事件的AOE网，网，试求其关键路径试求其关键路径。 【解解】由】由ve (i)和和vl (i)的递推公式，依次求出所有事件的最的递推公式，依次求出所有事件的最早发

52、生时间早发生时间ve (i)和最迟发生时间和最迟发生时间vl (i)，如下：如下：图图7-29 AOEAOE网网 64253a1=3a8=1a6=3a2=2a3=2a4=3a5=41a7=2顶点最早发生时间ve(i)最迟发生时间vl(i)v1v6v5v4v3v20866238762402022-3-26109 求出所有活动的最早开始时间求出所有活动的最早开始时间e (i)e (i)、最迟开始时间最迟开始时间l (i)l (i)以及以及d (i)=l (i)-e (i)d (i)=l (i)-e (i)，如下：如下：活动最早开始时间e(i)最迟开始时间l(i)a1a6a5a4a3a2022330

53、524401d(i)=l(i)-e(i)a8a77666103011012022-3-26110 从以上计算得出，图从以上计算得出，图7-297-29中中AOEAOE网的关键活动为网的关键活动为a a2 2，a a5 5，a a7 7，这些活动构成了这些活动构成了关键路径关键路径，如图，如图7-307-30所示：所示： 图图7-30 7-30 AOEAOE网的关键路径网的关键路径643a2=2a5=41a7=22022-3-261117.67.6 最短路径最短路径1.1.两地之间是否有通路两地之间是否有通路? ?2.2.若存在多条通路，哪条路最短？若存在多条通路，哪条路最短？2022-3-26

54、1127.6 7.6 两点之间的最短路径问题两点之间的最短路径问题 求从某个源点到其余各点的最短路径求从某个源点到其余各点的最短路径 每一对顶点之间的最短路径每一对顶点之间的最短路径2022-3-261137.6.1 从一个点到其余各顶点的最短路径算法从一个点到其余各顶点的最短路径算法 将图中所有顶点分成两组，一组是包括已将图中所有顶点分成两组，一组是包括已确定最短路径的顶点的集合确定最短路径的顶点的集合S S，另一组是，另一组是尚未确定的最短路径的顶点。尚未确定的最短路径的顶点。1. 取取V0加入加入S中中2. 求出从求出从S中中V0到到S外各顶点的最短路的外各顶点的最短路的顶点顶点W。3.

55、 把把W加入加入S中中2022-3-26114迪杰斯特拉算法的求解过程：迪杰斯特拉算法的求解过程： 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 2022-3-26115 3 8 12 4 3 8 12 4 (e) 第三次求得的结果 (f) 第四次求得的结果 1 2 3 5 4 1 2 3 5 4 图图7-17 迪杰斯特拉算法求最短路径过程及结果迪杰斯特拉

56、算法求最短路径过程及结果2022-3-26116例例135V0V1V4V3V2V5V2V3V1V41. 取取V0加入加入S中中2. 求出从求出从S中中V0到到S外各顶点的最短路外各顶点的最短路的顶点的顶点W。3. 把把W加入加入S中中2022-3-26117例例135V1V2V5V4V3V6V3V4V2V5v1到其它各点的最短路到其它各点的最短路k=1k=2k=3k=4k=5v250v310v4 v545v6 选点选点330352015201050154510501 2 3 4 5 61 2 3 4 5 6502545 4545 45 2022-3-26118例例233241028648745

57、169912V5V1V4V2V3V0v0到其它各点的最短路k=1 k=2 k=3 k=4 k=5v1v2v3v4v5选点8728641645241210339901 2 3 4 50 1 2 3 4 52022-3-2611933241028648745169912V5V1V4V2V3V0v0到其它各点的最短路k=1 k=2 k=3 k=4 k=5v1v2v3v4v5选点8728641645241210339901 2 3 4 50 1 2 3 4 5993310v3552674v23850v150v52022-3-261202022-3-261212022-3-261222022-3-261

58、23 在狄克斯特拉算法中，求一条最短路径所花费的时间：从在狄克斯特拉算法中，求一条最短路径所花费的时间：从V-S中中选取具有最小距离的顶点选取具有最小距离的顶点v k花费时间花费时间O(n)；修改修改V-S中顶点的距离花中顶点的距离花费时间费时间O(n)；输出最短路径花费时间输出最短路径花费时间O(n)。因此求出因此求出n-1条最短路径条最短路径的的时间复杂度为时间复杂度为O(n2)。 2022-3-261247.6.2 求每一对顶点之间的最短路径求每一对顶点之间的最短路径 顶点对之间的最短路径顶点对之间的最短路径是指：对于给定的有向网是指：对于给定的有向网G=(V,E),G=(V,E),要要

59、对对G G中任意一对顶点有序对中任意一对顶点有序对V V、W(VW),W(VW),找出找出V V到到W W的最短距离和的最短距离和W W到到V V的最短距离。的最短距离。 解决此问题的一个解决此问题的一个有效方法有效方法是是: :轮流以每一个顶点为源点轮流以每一个顶点为源点, ,重重复执行迪杰斯特拉算法复执行迪杰斯特拉算法n n次次, ,即可求得每一对顶点之间的最短路即可求得每一对顶点之间的最短路径径, ,总的时间复杂度为总的时间复杂度为O(n3)O(n3)。 弗洛伊德提出了另外一个求图中任意两顶点之间最短路径的弗洛伊德提出了另外一个求图中任意两顶点之间最短路径的算法，虽然其时间复杂度也是算法

60、，虽然其时间复杂度也是 O(n3)O(n3)，但其算法的形式更简单，但其算法的形式更简单，易于理解和编程。易于理解和编程。弗洛伊德弗洛伊德FloydFloyd算法的算法的基本思想基本思想是：是：2022-3-26125 将图中一个顶点将图中一个顶点Vk 加入到加入到S中中，修改，修改Aij的值的值，修改方修改方法法是是：Aij=MinAij , (Aik+Akj) 设顶点集设顶点集S(初值为空初值为空)，用数组，用数组A的每个元素的每个元素Aij保存从保存从Vi只经只经过过S中的顶点中的顶点到达到达Vj的最短路径长度，其思想是：的最短路径长度，其思想是： 初始时令初始时令S= ， Aij的的赋赋初值方