1、a1本章主要介绍本章主要介绍图图的基本概念、图的存储结构和有关的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该：图的一些常用算法。通过本章学习，读者应该：1)了解图的定义和术语了解图的定义和术语 2)掌握图的各种存储结构掌握图的各种存储结构 3)掌握图的掌握图的深度优先搜索深度优先搜索和和广度优先搜索广度优先搜索遍历算法遍历算法 4)理解理解最小生成树、最短路径、拓扑排序、关键路最小生成树、最短路径、拓扑排序、关键路径径等图的常用算法等图的常用算法 a2 图（Graph）是一种较线性表和树更为复杂的）是一种较线性表和树更为复杂的非线性结构非线性结构。在在线性结构线性结构中
2、，结点之间的关系是中，结点之间的关系是线性关系线性关系，除开始结点和终，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。端结点外，每个结点只有一个直接前趋和直接后继。在在树形结构树形结构中，结点之间的关系实质上是中，结点之间的关系实质上是层次关系层次关系，同层上的，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。只能和上一层的一个结点（即双亲）相关（根结点除外）。然而在然而在图形结构图形结构中，对结点（图中常称为顶点）的前趋和后继中，对结点（图中常称为顶点）的前趋
3、和后继个数都是不加限制的，即个数都是不加限制的，即结点之间的关系是任意的结点之间的关系是任意的。图中任意。图中任意两个结点之间都可能相关。两个结点之间都可能相关。图的图的应用应用极为广泛，特别是近年来的迅速发展，已渗透到诸如极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。学的其它分支中。a3 第七章第七章 图图a4v 图图定义定义 图图G由两个集合由两个集合V和和E组成，记为组成，记为 G=(V,E)其中，其中，V是顶点的有穷非空集合，是顶点的有穷非空集合，E是是V中顶点偶
4、对的有穷集，中顶点偶对的有穷集，这些顶点偶对称为边。通常这些顶点偶对称为边。通常V(G)和和E(G)分别称分别称为图的为图的顶点集合顶点集合和和边集合边集合。注注：E(G)可以为空集。可以为空集。a5v 图的数据结构的图的数据结构的形式化定义形式化定义 （p156）G=(V,E)其中其中 V=x|x dataobject E=VR VR=|p(x,y)(x,y V)VR是两顶点间的关系的集合，即边的是两顶点间的关系的集合，即边的集合。集合。a6G1G1=（V，E）V=v1,v2,v3,v4E=,其中其中表示从表示从x到到y的一条弧（的一条弧（arc），），A为为弧集合，弧集合，x为弧尾（为弧尾
5、（tail），），y为弧头（为弧头（head)x弧尾y弧头a7G2 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之间的一条连线，称为边之间的一条连线，称为边（edge）a8图的图的术语术语设设n为顶点数，为顶点数，e为边或弧的条数为边或弧的条数 对对无向图无向图有：有：0 e n(n-1)/2 有向图有向图有：有：0 e n(n-1)证明：对有向图，每个顶点至多有证明：对有向图，每个顶点至多有n-1条边与其它的条边与其它的n-1个顶点相连，则个顶点相连，则
6、n个顶点至多有个顶点至多有n(n-1)条边条边。但对。但对无向图，每条边连接无向图，每条边连接2个顶点，故最多为个顶点，故最多为n(n-1)/2a9在一个无向图中，若存在一条边在一个无向图中，若存在一条边v,则称则称v vi i，v vj j为该边的两个为该边的两个端点端点，并称它们，并称它们互为互为邻结点邻结点。21453G2a10在一个有向图中，若存在一条边在一个有向图中，若存在一条边,则称该边则称该边是顶点是顶点v vi i的一条的一条出边出边，是，是v vj j的一条的一条入边入边，称，称v vi i是起是起始端点（或始端点（或起点起点），称），称v vj j是终止端点（或是终止端点（
7、或终点终点）,并称它们并称它们互为邻结点互为邻结点.2134G1a11图中每个顶点的度是以该顶点为一端点的边的数目。图中每个顶点的度是以该顶点为一端点的边的数目。记为记为 D(V)。对于有向图，入度为以该顶点为终点的对于有向图，入度为以该顶点为终点的边的数目，出度为以该顶点为起点的边的数目。边的数目，出度为以该顶点为起点的边的数目。例例 D(v1)=3 无向图的度数为依附于顶点无向图的度数为依附于顶点v的边数；有向图的度数等于以的边数；有向图的度数等于以顶点顶点v 为弧头的弧数与以顶点为弧头的弧数与以顶点v为弧尾的弧数之和为弧尾的弧数之和21453G22134G1例例 D(v1)=2 a12设
8、有两个图设有两个图G=（V，E）G=（V，E）中，若中，若V是是V的子集，的子集，E是是E的子集，则称的子集，则称G是是G子图。子图。G2 a13对不含多重边和自环的图。对不含多重边和自环的图。2145321453a14图的图的术语术语 边达到最大的图边达到最大的图 无向完全图：无向完全图：具有具有条边的简单图条边的简单图称为无向完全图称为无向完全图 有向完全图：有向完全图：具有具有条边的有向图。条边的有向图。稀疏图：稀疏图：边或弧很少的图。边或弧很少的图。稠密图：稠密图：边或弧很多的图。边或弧很多的图。权：权：与图的边或弧相关的数。与图的边或弧相关的数。网：网：边或弧上带有权值的图。边或弧上
9、带有权值的图。a15非空有限非空有限点、弧交替点、弧交替序列，序列，W=v0,a1,v1,ak,vk 使得使得i=1,2,k,弧弧ai的头的头vi,尾为尾为vi-1 。路径长度：路径长度：路径上边或弧的数目路径上边或弧的数目a16：除首尾两点外，其他各点都不除首尾两点外，其他各点都不相同的路径称为简单路径。相同的路径称为简单路径。简单路径简单路径a17回路回路:无重复边的闭路径。无重复边的闭路径。环：环：闭的简单路径，称为环。闭的简单路径，称为环。但不是但不是环环环环a18任何两点都有路径的图。任何两点都有路径的图。若图中任意两个顶点若图中任意两个顶点vi,vj都是连通都是连通 的，则称该图是
10、的，则称该图是连通图连通图(vivj)若图中任意两个顶点若图中任意两个顶点vi,vj，都存在，都存在 从从vi到到vj 和从和从 vj到到vi的路径，则称的路径，则称 该有向图为该有向图为强连通图强连通图 (vivj)a19无向图中极大连通子图，称为无向图中极大连通子图，称为 连通分量连通分量有向图中极大强连通子图，称为有向图中极大强连通子图，称为 强连通分量强连通分量a20生成树生成树一个连通图的生成树是一个极小连通子图一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵，它含有图中全部顶点，但只有足以构成一棵树的树的n-1n-1条边。条边。如果一个有向图恰有一个顶点
11、入度为如果一个有向图恰有一个顶点入度为0 0，其余顶点的入度均为其余顶点的入度均为1 1，则是一棵有向树。，则是一棵有向树。a21生成树、生成森林生成树、生成森林生成树生成树 一个连通图的生成树是它的一个连通图的生成树是它的极小连通子图极小连通子图，在在n n个顶个顶点的情形下，有点的情形下，有n n-1-1条边。条边。生成树是对连通图而言的生成树是对连通图而言的 是连通图的极小连通子图是连通图的极小连通子图 包含图中的所有顶点包含图中的所有顶点 有且仅有有且仅有n-1n-1条边条边 非连通图非连通图的生成树则组成一个的生成树则组成一个生成森林生成森林。若图中有。若图中有n n个顶点个顶点，m
12、 m个连通分量，则生成森林中有个连通分量，则生成森林中有n-mn-m条边。条边。一个有向图的一个有向图的生成森林生成森林由若干棵有向树组成，含有图由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。中全部顶点，但只有足以构成若干棵不相交的有向树的弧。a22a23 邻接矩阵邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的是表示顶点之间相邻关系的矩阵。设矩阵。设G(V，E)是具有是具有n个顶点的图，则个顶点的图，则G的邻接矩阵的邻接矩阵是具有如下性质的是具有如下性质的n阶方阵。阶方阵。Aij=1 对无向图若存在边(vi,vj),对有向图若存在弧0 反之
13、无向图无向图的邻接矩阵是以的邻接矩阵是以主对角线对称主对角线对称的，的，有向图有向图的邻接的邻接矩阵矩阵可能可能是是不对称不对称的。的。在有向图中：在有向图中：第第 i 行行 1 的个数就是顶点的个数就是顶点 i 的出度，的出度，第第 j 列列 1 的个数就是顶点的个数就是顶点 j 的入度。的入度。在无向图中在无向图中,第第 i 行行(列列)1 的个数就是顶点的个数就是顶点i 的度。的度。a24例如：例如：G1的邻接矩阵的邻接矩阵例如：例如：G2的邻接矩阵的邻接矩阵无向图的邻接矩阵为对称矩阵无向图的邻接矩阵为对称矩阵G212345G1123400011000000001101G00110001
14、011101010101010102Ga25 对于对于无向图无向图，（，（vi，vj）和（和（vj，vi）表示同一条边，因表示同一条边，因此，在邻接矩阵中此，在邻接矩阵中Aij=Aji。无向图的邻接矩阵是（关于主对角线）无向图的邻接矩阵是（关于主对角线）对称矩阵对称矩阵，可用，可用主对角线以上（或以下）的部分表示。主对角线以上（或以下）的部分表示。对对有向图有向图，弧，弧和和表示方向不同的两条弧，表示方向不同的两条弧，Aij和和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。称性。邻接矩阵表示法邻接矩阵表示法适合于适合于以顶点为主的运算以
15、顶点为主的运算。a26对于对于有向图有向图，顶点，顶点vi的的出度出度OD(vi)等于邻接矩阵第等于邻接矩阵第i行行元素之和；顶点元素之和；顶点vi的的入度入度ID(vi)等于邻接矩阵第等于邻接矩阵第i列元素之列元素之和，即和，即：对于对于无向图无向图，顶点，顶点v vi i的度的度等于邻接矩阵第等于邻接矩阵第i i行的元素之和，行的元素之和，即：即：njjiA1,njjiA1,njijA1,TDTD（v vi i）=a27V2V1V3V435214 Wij 若若 或或 E(G)A i，j =0或 若其它若其它150000000423AV1 V2 V3 V4V1 V2 V3 V4a28 使用邻
16、接矩阵存储结构，可用使用邻接矩阵存储结构，可用一维数组一维数组表示图的表示图的顶点集合顶点集合，用用二维数组二维数组表示图的顶点之间关系（表示图的顶点之间关系（边或弧）的集合边或弧）的集合，数据类型，数据类型定义如下：定义如下：#define MAX_VERTEX_NUM 20 /最大顶点数最大顶点数typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵类型邻接矩阵类型typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点表顶点表AdjMatrix arcs;/邻接矩阵邻接矩阵int vexnum
17、，arcnum;/图的顶点数和弧数图的顶点数和弧数 MGraph;由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。稀疏矩阵，因此会造成一定存储空间的浪费。a29 图的图的链式存储结构链式存储结构 1)1)为每个顶点建立一个单链表，为每个顶点建立一个单链表，2)2)第第i i个单链表中包含顶点个单链表中包含顶点ViVi的所有邻接顶点。的所有邻接顶点。邻接表邻接表是图的一种链式存储结构。是图的一种链式存储结构。类似于树的孩子链表类似于树的孩子链表表示法。表示法。在邻接表中为图中每个顶点建立一个单链表，用
18、在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为以该顶点为弧尾的一条弧），称为边（或弧）结点边（或弧）结点。a3025341543533412212123451.1.无向图无向图邻接表邻接表G212345adjvex nextarcvexdata firstarca31234143121234如图如图G1的邻接表为：的邻接表为：G11234a32a33a3425341543533412212123451.1.无向图无向图邻接表邻接表二、邻接表二、邻接表G212345adj
19、vex nextarcvexdata firstarca351.1.无向图邻接表无向图邻接表对图中对图中每个顶点每个顶点Vi建立一个单链表，链建立一个单链表，链表中的结点表示依附于顶点表中的结点表示依附于顶点Vi的边，每的边，每个链表结点为两个域个链表结点为两个域.其中：其中：邻接点域（邻接点域（adjvex）记载与顶点记载与顶点Vi邻接的顶点信息；邻接的顶点信息；链域（链域（nextarc）指向下一个与顶点指向下一个与顶点Vi邻接的链表邻接的链表p结点结点每个链表设一个每个链表设一个头结点头结点，头结点头结点结构结构为：为：其中：其中：vexdata存放顶点信息（姓名、编号等）存放顶点信息（
20、姓名、编号等）；firstarc指向链表的第一个结点。指向链表的第一个结点。二、邻接表二、邻接表adjvex nextarcvexdata firstarca362534154353341221212345G212345a37BACDFE例例 20 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3a382341431212341.n个顶点，个顶点，e条弧的有向图，需条弧的有向图，需n个表头结点，个表头结点，e 个表结点个表结点 2.第第 i 条链表上的结点数，为条链表上的结点数，为 Vi 的出度的出度如图如图G1的邻接表为：的邻接表为：G11234a39
21、1 4230 120 1 2 3 4 A B C D E2.有向图有向图的邻接表的邻接表ABECF可见，在有向图的可见，在有向图的邻接表中邻接表中不易不易找到找到指向该顶点的弧。指向该顶点的弧。a403 3123411431234如图如图G1G1的的逆邻接逆邻接表为：表为：G1a41ABECD有向图的有向图的逆邻接表逆邻接表A B C D E 303420 01234在有向图的在有向图的邻接表邻接表中，对每中，对每个顶点，个顶点，链接的是指向该顶链接的是指向该顶点的弧。点的弧。a42链表中每个结点为链表中每个结点为三个域三个域.邻接点邻接点 权权a43ABECD4.A B C D E 0123
22、41 10 3 7 0 4 4 22 3 2 8 1022548371 25 a44hlinkhlink指向弧头相同的下一条弧，指向弧头相同的下一条弧，tlinktlink指向弧尾相同的指向弧尾相同的下一条弧；下一条弧；datadata顶点信息，顶点信息，firstinfirstin以该顶点为头的第一个弧结点，以该顶点为头的第一个弧结点，firstoutfirstout以该结点为尾的第一个弧结点。以该结点为尾的第一个弧结点。起点起点vi 终点终点vj hlink tlink弧弧结构结构顶点结构顶点结构 data firstin firstouta4543213231201203010321a4
23、6a47markivex ilinkjvexjlinkdatafirstedgea482301154323441201304321图图7-9为图为图7-5(a)无向图的无向图的邻接多重表邻接多重表。a49a50 图的遍历远比树的遍历复杂。因为从树根到达树的某个图的遍历远比树的遍历复杂。因为从树根到达树的某个结点只有一条路径，而图的两个顶点之间可能有多条路径结点只有一条路径，而图的两个顶点之间可能有多条路径。因此，在图的遍历过程中，可能会出现下面的现象，即在因此，在图的遍历过程中，可能会出现下面的现象，即在顺着一条路径访问了某个顶点后，可能会沿着另一条路径又回顺着一条路径访问了某个顶点后，可能会
24、沿着另一条路径又回到该顶点。到该顶点。为避免一个顶点被多次访问为避免一个顶点被多次访问，我们设置一个标志数组，我们设置一个标志数组int visitedMAX_VERTEX_NUM;它的元素初值为它的元素初值为0 0。一旦。一旦v vi i被访问了，便置相应数组元素为被访问了，便置相应数组元素为1.1.图的图的遍历方法遍历方法有：有：这两种方法对无向图和有向图都适用。这两种方法对无向图和有向图都适用。深度优先搜索遍历（简称深度优先搜索遍历（简称DFS）广度优先搜索遍历（简称广度优先搜索遍历（简称BFS）a511 深度优先搜索深度优先搜索a52a5317823456(a)a54int visit
25、edMAX_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个顶点出发个顶点出发DFSa55整个图的整个图的DFS遍历遍历void DFSTraverse(ALGraph G)for(int v=0;vG.vexnum;+v)visitedv=0;for(v=0;vG.vexnum;+v)if(!visit
26、edv)DFS(G,v);对于连通图，从一个顶点出发，调用对于连通图，从一个顶点出发，调用DFS函数即可将所有函数即可将所有顶点都遍历到。顶点都遍历到。a561 广度优先搜索广度优先搜索思想思想 广度优先搜索遍历类似于树的按层次遍历。广度优先搜索遍历类似于树的按层次遍历。对于无向连通图，广度优先搜索是对于无向连通图，广度优先搜索是从从图的某个顶点图的某个顶点v0出发，出发，在访问在访问v0之后，之后，依次搜索依次搜索访问访问v0的各个未被访问过的邻接点的各个未被访问过的邻接点w1，w2，。然后顺序然后顺序搜索访问搜索访问w1的各未被访问过的邻接点，的各未被访问过的邻接点，w2的各未被访问过的邻
27、接点，的各未被访问过的邻接点，。即从。即从v0开始，由近至远，按层开始，由近至远，按层次依次访问与次依次访问与v0有路径相通且路径长度分别为有路径相通且路径长度分别为1，2，的顶点，的顶点，直至直至连通图中所有顶点都被访问一次。连通图中所有顶点都被访问一次。广度优先搜索的顺序不是唯一的，例如图广度优先搜索的顺序不是唯一的，例如图7-10(a)连通图连通图的广度优先搜索遍历的广度优先搜索遍历顺序顺序可为可为v1，v2，v3，v4，v5，v6，v7，v8 也可为也可为v1，v3，v2，v7，v6，v5，v4，v8。a57广度优先搜索在搜索访问一层时，需要记住已被访问的广度优先搜索在搜索访问一层时，
28、需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索中访问其邻接点。所以在广度优先搜索中需要设置需要设置一个一个队列队列Queue，使已被访问的顶点顺序由队尾进入队列使已被访问的顶点顺序由队尾进入队列。在搜索访。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点从该顶点出发搜索访问它的各个邻接点 a58队列初始化，空队列；队列初始化，空队列；f-队首指针，队首指针，r-队尾指针队尾指针a59 voi
29、d 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);/v入队列入队列 while(!QueueEmpty(Q)u=DeQueue(Q,u);/队头元素出队并置为队头元素出队并置为u for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(
30、G,u,w)if(!visitedw)visitedw=1;Visit(w);EnQueue(Q,w);/访问的顶点访问的顶点w入队列入队列 /if /while /BFSTraversea60课堂练习课堂练习练习练习1、写出右图的邻接矩阵表示。、写出右图的邻接矩阵表示。ACBDEFa61课堂练习课堂练习练习练习2、写出右图的邻接表表示。、写出右图的邻接表表示。ACBDEF543210FEDCBA 1 2 0 4 5 3 5 3 4a62课堂练习课堂练习练习练习3、根据右图的如下存储表示，写出以顶点、根据右图的如下存储表示，写出以顶点A为出发点为出发点进行进行DFS的顶点访问序列。的顶点访问序
31、列。ACBDEF543210FEDCBA 1 2 0 4 5 3 5 3 4A，B，D，E，F，Ca63课堂练习课堂练习ACBDEF543210FEDCBA 1 2 0 4 5 3 5 3 4A，B，C，D，E，F练习练习4、根据右图的如下存储表示，写出以顶点、根据右图的如下存储表示，写出以顶点A为出发点为出发点进行进行BFS的顶点访问序列。的顶点访问序列。a64a65a66252510504613228102514242216185046132504613210原图 (a)(b)504613210(c)(d)(e)(f)504613210221250461210251422161232522
32、12a6750461322810251424221618120281028016141601212022182202524102501418240a680 28 10 -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 602810280161416012120221822025241025014182405046132281025142422161812a69a700 28 10 -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 6选选 v=5选边选边(0,5)02810280161416012120221822025241025
33、01418240a71顶点顶点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)加入生成树1204613210255a720 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)50461322810251424221618原图 边(5,4,25)
34、加入生成树125046132102522a73顶点顶点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)加入生成树12504613210252212a74lowcostnearvex0 1 2 3 4 5 6顶点顶点v=2加入生成树顶点集合：加入生成树顶点集合：0 16 12 22 25 10 18-1 2 -1 -1 -1 -1 3 选选 v=1选边选边(2,1)5046
35、1322810251424221618原图 边(3,2,12)加入生成树125041321025221612a75顶点顶点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)加入生成树125046132102514221612a76lowcostnearvex0 1 2 3 4 5 6顶点顶点v=6加入生成树顶点集合：加入生成树顶点集合：0 16 12 22 25 10 1
36、4-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)a77a78typedef int VRType;structVertexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;void MiniSpanTree_PRIM(MGraph G,VertexType u)int k,j,i,minCost;k=LocateVex(G,
37、u);for(j=0;jG.vexnum;+j)if(j!=k)closedgej.adjvex=u;closedgej.lowcost=G.arcskj;a79closedgek.lowcost=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)
38、;closedgek.lowcost=0;for(j=0;jG.vexnum;+j)if(G.arcskjclosedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj;a80普里姆算法中的第二个普里姆算法中的第二个forfor循环语句频度为循环语句频度为n-1n-1，其中包含的两个内循环频度也都为其中包含的两个内循环频度也都为n-1n-1，因此普里因此普里姆算法的姆算法的时间复杂度时间复杂度为为O(nO(n2 2)。普里姆算法的时间普里姆算法的时间复杂度与边数复杂度与边数e e无关，该算法无关，该算法更适合于更适合于
39、求边数较多求边数较多的的带权无向连通图的最小生成树。带权无向连通图的最小生成树。a81a8210504613228102514242216181250461325046132原图 (a)(b)a831012504613228102514242216181250461325046132101412原图 (c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123a84为实现克鲁斯卡尔算法需要设置一维辅助数组为实现克鲁斯卡尔算法需要设置一维辅助数组E E，按权值从按权值从小到大的顺序存放图的边，数组的下标取值从小到大的顺序存放
40、图的边，数组的下标取值从0 0到到e-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;a85 Void kruskal
41、(Edge E,int n,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(ke)/生成的边数小于生成的边数小于e时继续循环时继续循环 ml=Ej.vex1;m2=Ej.vex2;/取一条边的两个邻接点取一条边的两个邻接点 sn1=vsetm1;sn2=vsetm2;/分别得到两个顶点所属的集合编号分别得到两个顶点所属的集合编号
42、 if(sn1!=sn2)/两顶点分属于不同的集合，该边是最小生成树的一条边两顶点分属于不同的集合，该边是最小生成树的一条边a86 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中，则用克鲁斯卡尔算法构造最小生成树中，
43、则用克鲁斯卡尔算法构造最小生成树的的时间复杂度时间复杂度为为O(e)O(e)。克鲁斯卡尔算法的时间复杂度与边数克鲁斯卡尔算法的时间复杂度与边数e e有关，该算法有关，该算法适合于适合于求求边数较少的带权无向连通图边数较少的带权无向连通图的最小生成的最小生成树。树。a87a88a89a90a91a92a93a94a95a96a97a98a99 在实现拓扑排序的算法中，采用在实现拓扑排序的算法中，采用邻接表邻接表作为有向图的存储作为有向图的存储结构，每个顶点设置一个结构，每个顶点设置一个单链表单链表，每个单链表有一个表头结，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域点，在表头结
44、点中增加一个存放顶点入度的域countcount，这些表这些表头结点构成一个数组，头结点构成一个数组，表头结点定义表头结点定义如下：如下：typedef struct /表头结点表头结点 Vertex data;/顶点信息顶点信息 int count;/存放顶点入度存放顶点入度 ArcNode*firstarc;/指向第一条弧指向第一条弧Vnode;a100 void topsort(VNode adj,int n)int i,j;int stackMAXV,top=0;/栈栈stack的指针为的指针为top ArcNode*p;for(i=0;i0)/栈不为空栈不为空 i=stacktop;
45、top-;/顶点顶点vi出栈出栈 printf(“d”,i);/输出输出vi p=adji.firstarc;/指向以指向以vi为弧尾的第一条弧为弧尾的第一条弧 while(p!=NULL)j=p-adjvex;/以以vi为弧尾的弧的另一顶点为弧尾的弧的另一顶点vj a101 while(p!=NULL)j=p-adjvex;/以以vi为弧尾的弧的另一顶点为弧尾的弧的另一顶点vj adjj.count-;/顶点顶点vj的入度减的入度减1 if(adjj.count=0)/入度为入度为0的相邻顶点入栈的相邻顶点入栈 top+;stacktop=j;p=p-nextarc;/指向以指向以vi为弧尾
46、的下一条弧为弧尾的下一条弧 a102网中只有：唯一一个入度为网中只有：唯一一个入度为0 0的点的点 源点源点 唯一一个出度为唯一一个出度为0 0的点的点 汇点汇点7.5.2 关键路径关键路径a103a104为头的弧的集合是所有以其中jTnjTjijidutiVeMaxjVei2,),()()(为尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11,),()()(Ve(j)=从源点到顶点从源点到顶点j的最长路径长度；的最长路径长度；Vl(k)=从顶点从顶点k到汇点的最短路径长度。到汇点的最短路径长度。a105a106a107a108void CriticalPath(ALGr
47、aph 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+)Vei=0;for(i=0;i adjvex;if(Vei+p-info Vek)Vek=Vei+p-info;p=p-nextarc;a109 for(i=0;i adjvex;if(Vlk-p-info info;p=p-nextarc;a110【例例7-4】图】图7-29是一个具有是一个具有8个活动和个活动和6个事件的个事件的AOE网，网，试求其关键路径试求其关键路径。【解解】由】由ve(
48、i)和和vl(i)的递推公式，依次求出所有事件的最的递推公式，依次求出所有事件的最早发生时间早发生时间ve(i)和最迟发生时间和最迟发生时间vl(i)，如下：如下：图图7-29 AOEAOE网网 64253a1=3a8=1a6=3a2=2a3=2a4=3a5=41a7=2顶点最早发生时间ve(i)最迟发生时间vl(i)v1v6v5v4v3v2086623876240a111 求出所有活动的最早开始时间求出所有活动的最早开始时间e(i)e(i)、最迟开始时间最迟开始时间l(i)l(i)以及以及d(i)=l(i)-e(i)d(i)=l(i)-e(i)，如下：如下：活动最早开始时间e(i)最迟开始时
49、间l(i)a1a6a5a4a3a2022330524401d(i)=l(i)-e(i)a8a7766610301101a112 从以上计算得出，图从以上计算得出，图7-297-29中中AOEAOE网的关键活动为网的关键活动为a a2 2，a a5 5，a a7 7，这些活动构成了这些活动构成了关键路径关键路径，如图，如图7-307-30所示：所示：图图7-30 7-30 AOEAOE网的关键路径网的关键路径643a2=2a5=41a7=2a1137.67.6 最短路径最短路径 两地之间是否有通路两地之间是否有通路?若存在多条通路，哪条路最短？若存在多条通路，哪条路最短？a1147.6 7.6
50、两点之间的最短路径问题两点之间的最短路径问题v 求从某个源点到其余各点的最短路径求从某个源点到其余各点的最短路径v 每一对顶点之间的最短路径每一对顶点之间的最短路径a1157.6.1 从一个点到其余各顶点的最短路径算法从一个点到其余各顶点的最短路径算法 将图中所有顶点分成两组，一组是包括已将图中所有顶点分成两组，一组是包括已确定最短路径的顶点的集合确定最短路径的顶点的集合S S，另一组是，另一组是尚未确定的最短路径的顶点。尚未确定的最短路径的顶点。取取V0加入加入S中中 求出从求出从S中中V0到到S外各顶点的最短路的外各顶点的最短路的顶点顶点W。把把W加入加入S中中a116迪杰斯特拉算法的求解
