第6章专题3-最小生成树1

1、数据结构（数据结构（C版）版）清华大学出版社清华大学出版社专题专题3：最小生成树：最小生成树123最小生成树的定义最小生成树的定义 Prim算法算法 Kruskal算法算法 4MST性质性质数据结构（数据结构（C版）版）清华大学出版社清华大学出版社p 生生成树的代价：成树的代价：设设G = (V, E)是一个无向连通网，生是一个无向连通网，生成树上各边的权值之和称为该成树上各边的权值之和称为该生生成树的代价成树的代价。 p 最小生成树：最小生成树：在图在图G所有生成树中，代价最小的生所有生成树中，代价最小的生成树称为成树称为最小生成树最小生成树。 6.3 最小生成树最小生成树最小生成树的定义最

2、小生成树的定义最小生成树的概念可以应用到许多实际问题中。最小生成树的概念可以应用到许多实际问题中。例：在例：在n个城市之间建造通信网络，至少要架设个城市之间建造通信网络，至少要架设n-1条条通信线路，而每两个城市之间架设通信线路的造价是通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？不一样的，那么如何设计才能使得总造价最小？ 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社MST性质性质假设假设G=(V, E)是一个无向连通网，是一个无向连通网，U是顶点集是顶点集V的一的一个非空子集。若个非空子集。若(u, v)是一条具有最小权值的边，其是一条

3、具有最小权值的边，其中中uU，vVU，则必存在一棵包含边，则必存在一棵包含边(u, v)的最的最小生成树。小生成树。顶顶点点集集UVUuvvu顶顶点点集集T1T26.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社MST性质性质顶顶点点集集UVUuvvu顶顶点点集集T1T26.3 最小生成树最小生成树设设T是图是图G的一棵最小生成树，将的一棵最小生成树，将T中的顶点集分成两部分：中的顶点集分成两部分：顶点集顶点集U：U和相关的边构成一棵最小生成子树和相关的边构成一棵最小生成子树T1；顶点集顶点集V-U：V-U和相关的边构成一棵最小生成子树和相关的边构成一棵最小

4、生成子树T2。 则则T1和和T2之间只能有一条边，不妨设为之间只能有一条边，不妨设为(u，v)，且，且u和和u之间、之间、v和和v之间均是连通的之间均是连通的数据结构（数据结构（C版）版）清华大学出版社清华大学出版社MST性质性质顶顶点点集集UVUuvvu顶顶点点集集T1T26.3 最小生成树最小生成树 当将边当将边(u，v)加入加入T中时，由生成树的定义，中时，由生成树的定义，T中必存在一中必存在一条包含边条包含边(u，v)的回路，删去边的回路，删去边(u，v)便可消除上述回路，便可消除上述回路，同时得到另一棵生成树同时得到另一棵生成树T 。因为边。因为边(u，v)的权值小于等于边的权值小于

5、等于边(u，v)的权值，则的权值，则T 的代价亦小于等于的代价亦小于等于T的代价，则的代价，则T 是一是一棵最小生成树，且包含边棵最小生成树，且包含边(u，v)。这与假设矛盾，由此性质得。这与假设矛盾，由此性质得证证数据结构（数据结构（C版）版）清华大学出版社清华大学出版社基本思想基本思想：设：设G=(V, E)是一个连通网，是一个连通网，T=(U, TE)是是G的最小的最小生成树，生成树，T的的初始状态初始状态为为U=u0（u0V），），TE= ，重复执，重复执行下述操作：在所有行下述操作：在所有uU，vV-U的边中找一条代价最小的的边中找一条代价最小的边边(u, v)并入集合并入集合TE，

6、同时，同时v并入并入U，直至，直至U=V。普里姆（普里姆（Prim）算法算法 6.3 最小生成树最小生成树Prim算法的基本思想用伪代码描述如下：算法的基本思想用伪代码描述如下：1. 初始化：初始化：U = v0； TE= ； 2. 重复下述操作直到重复下述操作直到U = V： 2.1 在在E中寻找最短边中寻找最短边(u，v)，且满足，且满足uU，vV-U； 2.2 U = U + v； 2.3 TE = TE + (u，v)；关键关键:是如何找到连接是如何找到连接U和和V-U的最短边的最短边。 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社U=A V-U=B, C, D, E,

7、Fcost=(A, B)34, (A, C)46, (A, D),(A, E),(A, F)19 251234192646381725ABEDCFPrim算法算法 6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Prim算法算法 251234192646381725ABEDCFU=A, F V-U=B, C, D, Ecost=(A, B)34,(F, C)25, (F, D)25,(F, E)26 6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Prim算法算法 2512341926381725ABEDCFU=A,

8、F, C V-U=B, D, Ecost=(A, B)34, (C, D)17,(F, E)26 6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Prim算法算法 12341926381725ABEDCFU=A, F, C, D V-U=B, Ecost=(A, B)34, (F, E)26 6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Prim算法算法 123419261725ABEDCFU=A, F, C, D, E V-U=Bcost=(E, B)12 6.3 最小生成树最小生成树数据结构（数据结构（C版）版）

9、清华大学出版社清华大学出版社Prim算法算法 1219261725ABEDCFU=A, F, C, D, E, B V-U= 6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1. 图的存储结构：由于在算法执行过程中，需要不断图的存储结构：由于在算法执行过程中，需要不断读取任意两个顶点之间边的权值，所以，图采用邻接读取任意两个顶点之间边的权值，所以，图采用邻接矩阵存储。矩阵存储。数据结构设计数据结构设计6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCF例如，对于顶点例如，对于

10、顶点C，只需保留，只需保留minarcAC, arcFC 6.3 最小生成树最小生成树2. 候选最短边集：设置数组候选最短边集：设置数组shortEdgen表示候选最表示候选最短边集，数组元素包括短边集，数组元素包括adjvex和和lowcost两个域，分别两个域，分别表示候选最短边的邻接点和权值。表示候选最短边的邻接点和权值。 数据结构设计数据结构设计对于对于V-U中的每个顶点，只保留从中的每个顶点，只保留从该顶点到该顶点到U中某顶点的最短边。中某顶点的最短边。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社p 候选最短边候选最短边(vi, vk)的权值为的权值为w，其中，其中vi

11、V-U，vkU：如何用如何用lowcost和和adjvex表示候选最短边集表示候选最短边集？6.3 最小生成树最小生成树shortEdgei.adjvex = kshortEdgei.lowcost = w数据结构设计数据结构设计shortEdgej.lowcost = min shortEdgej.lowcost , cost(vj，vk)shortEdgej.adjvex = k（如果边（如果边(vj，vk)的权值较小）的权值较小）p 顶点顶点vk从集合从集合V-U进入集合进入集合U后，依据下式更新数组后，依据下式更新数组shortEdge： 数据结构（数据结构（C版）版）清华大学出版社清

12、华大学出版社1. 初始化辅助数组初始化辅助数组shortEdgen；2. 输出顶点输出顶点v，将顶点，将顶点v加入集合加入集合U中；中；3. 重复执行下列操作重复执行下列操作n-1次次 3.1 在在shortEdgen.lowcost中选取最短边及对应的中选取最短边及对应的邻接点编号邻接点编号k； 3.2 输出顶点输出顶点k和对应的权值；和对应的权值； 3.3 将顶点将顶点k加入集合加入集合U中；中； 3.4 调整数组调整数组shortEdgen；Prim算法算法伪代码伪代码 6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Prim算法算法运行过程运行过程

13、 6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社void Prim(MGraph G) for (i = 1; i G.vertexNum; i+) /初始化辅助数组初始化辅助数组shortEdge shortEdgei.lowcost = G.arc0i; shortEdgei.adjvex = 0; shortEdge0.lowcost = 0; /将顶点将顶点0加入集合加入集合U for (i = 1; i G.vertexNum; i+) k = MinEdge(shortEdge, G.vertexNum) /寻找最短边的邻接点寻找最短边的邻接

14、点k cout(k shortEdgek.adjvex) shortEdgek.lowcost; shortEdgek.lowcost = 0; /将顶点将顶点k加入集合加入集合U中中 for (j = 1; j G.vertexNum; j+) /调整数组调整数组shortEdgen if G.arckj shortEdgej.lowcost shortEdgej.lowcost = G.arckj; shortEdgej.adjvex = k; Prim算法算法C+描述描述 6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社void Prim(MGrap

15、h G) for (i = 1; i G.vertexNum; i+) shortEdgei.lowcost = G.arc0i; shortEdgei.adjvex = 0; shortEdge0.lowcost = 0; for (i = 1; i G.vertexNum; i+) k = MinEdge(shortEdge, G.vertexNum) cout(k shortEdgek.adjvex) shortEdgek.lowcost; shortEdgek.lowcost = 0; for (j = 1; j G.vertexNum; j+) if G.arckj shortEdg

16、ej.lowcost shortEdgej.lowcost = G.arckj; shortEdgej.adjvex = k; Prim算法算法C+描述描述 6.3 最小生成树最小生成树时间复杂度？时间复杂度？O(n)O(n)O(n)因此，算法的时间复杂度为因此，算法的时间复杂度为O(n2)数据结构（数据结构（C版）版）清华大学出版社清华大学出版社克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法 基本思想基本思想：设无向连通网为：设无向连通网为G(V, E)，令，令G的最小生成树为的最小生成树为T(U, TE)，其，其初态为初态为UV，TE ，然后，按照，然后，按照边的权值边的权值由小到大的

17、顺序由小到大的顺序，考察，考察G的边集的边集E中的各条边。若被考察的边中的各条边。若被考察的边的两个顶点属于的两个顶点属于T的两个不同的的两个不同的连通分量连通分量，则将此边作为最小，则将此边作为最小生成树的边加入到生成树的边加入到T中，同时把两个连通分量连接为一个连通中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当此边，以免造成回路，如此下去，当T中的连通分量个数为中的连通分量个数为1时，此连通分量便为时，此连通分量便为G的一棵最小生成树。的一棵最小生成树。 6.3 最

18、小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法 1. 初始化：初始化：U=V；TE= ； 2. 重复下述操作直到重复下述操作直到T中的连通分量个数为中的连通分量个数为1： 2.1 在在E中寻找最短边中寻找最短边(u，v); 2.2 如果顶点如果顶点u、v位于位于T的两个不同连通分量，则的两个不同连通分量，则 2.2.1 将边将边(u，v)并入并入TE； 2.2.2 将这两个连通分量合为一个；将这两个连通分量合为一个； 2.3 标记边标记边(u，v)，使得，使得(u，v)不参加后续最短边的选取；不参加后续最短边的选取

19、；6.3 最小生成树最小生成树Kruskal算法的基本思想用伪代码描述如下：算法的基本思想用伪代码描述如下： 关键：如何判别被考察边的两个顶点是否位于两个连通分量关键：如何判别被考察边的两个顶点是否位于两个连通分量 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCFABEDCF连通分量连通分量A, B, C, D, E, F6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCFABEDCF连通分量连通分量A, B, C, D, E, F12连通分量连通分量A,

20、 B, E, C, D, F6.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCFABEDCF12176.3 最小生成树最小生成树连通分量连通分量A, B, E, C, D,F连通分量连通分量A, B, E, C, D, F数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCFABEDCF12196.3 最小生成树最小生成树17连通分量连通分量A, B, E, C, D, F连通分量连通分量A, F, B, E, C, D数据结构（数据结构（C版）版）清华大学出版

21、社清华大学出版社251234192646381725ABEDCFABEDCF连通分量连通分量A, F, B, E, C, D12连通分量连通分量A, F, C, D, B, E1917256.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社251234192646381725ABEDCFABEDCF连通分量连通分量A, F, C, D, B, E12连通分量连通分量A, F, C, D, B, E191725266.3 最小生成树最小生成树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.3 最小生成树最小生成树1. 图的存储结构：因为图的存储结构

22、：因为Kruskal算法是依次对图中的算法是依次对图中的边进行操作，因此考虑用边集数组存储图中的边，为边进行操作，因此考虑用边集数组存储图中的边，为了提高查找速度，将边集数组按边上的权排序。了提高查找速度，将边集数组按边上的权排序。 数据结构设计数据结构设计数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.3 最小生成树最小生成树2. 连通分量。连通分量。Kruskal算法实质上是使生成树以一种随意的方算法实质上是使生成树以一种随意的方式生长，初始时每个顶点构成一棵生成树，然后每生长一次就式生长，初始时每个顶点构成一棵生成树，然后每生长一次就将两棵树合并，到最后合并成一棵树。将两棵

23、树合并，到最后合并成一棵树。 设数组设数组parentn，元素，元素parenti表示顶点表示顶点i的双亲结点，初的双亲结点，初始时，始时，parenti= -1，表示顶点，表示顶点i没有双亲，即该结点是所在生没有双亲，即该结点是所在生成树的根结点；对于边成树的根结点；对于边(u, v)，设，设vex1和和vex2分别表示两个顶分别表示两个顶点点u和和v所在生成树的根结点，如果所在生成树的根结点，如果vex1vex2，则顶点，则顶点u和和v必必位于不同的连通分量，令位于不同的连通分量，令parentvex2 = vex1，实现将两棵生，实现将两棵生成树合并。成树合并。 求某顶点求某顶点v所在生

24、成树的根结点只需沿数组所在生成树的根结点只需沿数组v = parentv不不断查找断查找v的双亲，直到的双亲，直到parentv等于等于-1。 数据结构设计数据结构设计数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.3 最小生成树最小生成树1. 初始化辅助数组初始化辅助数组parentn；num = 0；2. 依次考查每一条边依次考查每一条边for (i = 0; i arcNum; i+) 2.1 vex1 = edgei.from所在生成树的根结点；所在生成树的根结点； 2.2 vex2 = edgei.to所在生成树的根结点；所在生成树的根结点； 2.3 如果如果vex1

25、!= vex2，执行下述操作：，执行下述操作： 2.3.1 parentvex2 = vex1; 2.3.2 num+; 2.3.3 if (num = n-1) 算法结束；算法结束；Kruskal算法用伪代码进一步描述为：算法用伪代码进一步描述为： Kruskal算法算法伪代码伪代码数据结构（数据结构（C版）版）清华大学出版社清华大学出版社v1初始化：初始化：parent0=-1parent1=-1parent2=-1parent3=-1parent4=-1parent5=-16.3 最小生成树最小生成树v5v0v4v3v2Kruskal算法算法运行过程运行过程数据结构（数据结构（C版）版）

26、清华大学出版社清华大学出版社v1考察最短边考察最短边(v1, v4):parent0=-1parent1=-1parent2=-1parent3=-1parent4=-1parent5=-16.3 最小生成树最小生成树v5v0v4v3v212Kruskal算法算法运行过程运行过程1v1数据结构（数据结构（C版）版）清华大学出版社清华大学出版社考察最短边考察最短边(v2, v3):parent0=-1parent1=-1parent2=-1parent3=-1parent4=1parent5=-16.3 最小生成树最小生成树v5v0v4v31712Kruskal算法算法运行过程运行过程2v1v1

27、v2数据结构（数据结构（C版）版）清华大学出版社清华大学出版社考察最短边考察最短边(v0, v5):parent0=-1parent1=-1parent2=-1parent3=2parent4=1parent5=-16.3 最小生成树最小生成树v5v4v3171219v1v1v2Kruskal算法算法运行过程运行过程0v0数据结构（数据结构（C版）版）清华大学出版社清华大学出版社考察最短边考察最短边(v2, v5):parent0=-1parent1=-1parent2=-1parent3=2parent4=1parent5=06.3 最小生成树最小生成树Kruskal算法算法运行过程运行过程

28、v5v4v3171219v1v1v2v0225数据结构（数据结构（C版）版）清华大学出版社清华大学出版社考察最短边考察最短边(v3, v5):parent0=2parent1=-1parent2=-1parent3=2parent4=1parent5=06.3 最小生成树最小生成树考查边考查边(v3, v5)，由于，由于parent3=2，parent2=-1，则则v3所在生成树的根结点是所在生成树的根结点是v2 ，而而parent5=0，parent0=2，则，则v5所在生成树的所在生成树的根结点也是根结点也是v2 ，故舍去此边。，故舍去此边。Kruskal算法算法运行过程运行过程v5v4v

29、3171219v1v1v2v02525数据结构（数据结构（C版）版）清华大学出版社清华大学出版社考察最短边考察最短边(v4, v5):parent0=2parent1=-1parent2=-1parent3=2parent4=1parent5=06.3 最小生成树最小生成树Kruskal算法算法运行过程运行过程v5v4v3171219v1v1v2v012526数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.3 最小生成树最小生成树Kruskal算法算法C+描述描述void Kruskal(EdgeGraph G) for (i = 0; i G.vertexNum; i+) parenti = -1; for (num = 0, i = 0; i G.edgeNum; i+) vex1 = FindRoot(parent, G.edgei.from); vex2 = FindRoot(parent, G.edgei.to); if (vex1 != v