大学《数据结构》第六章：图-第四节-图的生成树和最小生成树

第四节图的生成树和最小生成树

一、图的生成树

1、生成树的概念

对于具有n个顶点的连通图，包含了该图的全部n个顶点，仅包含

它的n-1条边的一个极小连通子图被称为生成树。

一个图的生成树为一个无回路的连通图。也就是说，若在图中任意

添加一条边，就会出现回路；若在图中去掉任何一条边，都会使之成

为非连通图。

一个连通图的生成树不一定是唯一的。

【例】下图中图（b）和（c）是图（a）的生成树。

由深度优先搜索所得的生成树称为深度优先生成树，简称为DFS生

成树；而由广度优先搜索所得的生成树称之为广度优先生成树，简称

为BFS生成树。

【例】下图中图（b）是图（a）从V0开始的深度优先搜索所得的

生成树，图（c）是图（a）从V0开始的广度优先搜索的生成树。

从V。开始的深度优先搜索序列：Vo,V1,V2,V5,V4,V6,V3,

V7,V8o

从Vo开始的广度优先搜索序列：Vo,V1zV3,V4,V2,V6,V8,

二、最小生成树

1、最小生成树的概念

对于连通的带权图（网）G,其生成树也是带权的。把生成树各边的权

值总和称为该树的权，把权值最小的生成树称为图的最小生成树

(MininumSpanningTree,MST)O

【例】图（b）、（c）、（d）是图（a）的三棵生成树。

(b)

2、普里姆（Prim）算法

（1）算法思想

用自然语言描述的Prim算法：设G=(V,GE)为具有n个顶点

的带权连通图，T=(U,TE)为G的一个子图，初始时，有丁£二空，

算法描述为：从中选择一个顶点仅在

U={Vi},ViGVoPrimGV

中，而另一个顶点在U中，并且权值最小的边加入集合TE中，同时

将该边仅在V中的那个顶点加入集合U中。重复上述过程n-1次，直

到U=V,止匕时T为G的最小生成树。

【例】试用Prim算法构造(a)图的最小生成树，要求分步给出

构造过程

【分析】算法一开始取u={l},然后到V-U中找一条代价最小且依

附于顶点1的边，(u。,vo)=(l,3),将vo=3加入集合U中，修改

辅助数组中的值。使minedge[3].lowcost=0,以表示顶点3已并入

U,由于边(3,6)上的权值是一条最小且依附于顶点集U中顶点的

边，因此修改minedge⑹的值，依此类推，直到U=V,其过程如表

所示。

23456Uv-u说明

ver①①①

{1}[2,3,4,5,6)u(l,3)边最短

lowcost605

ver③①③③

0{1，3}{2,4,5,6}u(3,6)边最短

lowcost5560

Ver③⑥③

00{1,3,6}[2,4,5)u(6,4)也最短

lowcost5目6

ver③③

000{1.3,6,4}{215}u(3,2)边最短

lowcost同6

ver②

0000{1,3,6,4,2}{5}U(2.5)边最短

lowcost

ver

00000{1,3,6,4,2,5}力

lowcost

(2)算法描述

附设一个辅助数组minedge[vtxptr],记录从U到V-U具有最小

代价的边。对每个顶点vwV-U,在辅助数组中存在一个分量

minedge[v],它包括两个域，其中lowcost存储该边上的权值，ver

域存储该边的依附在U中的顶点。Minedge[v]=min{cost(u,v),u

GU},(cost(u,v)表示该边的权)。

【算法描述】

typedefintVRType;

typedefstruct

{ertexTypeVer;

VRTypelowcost;

}minedge[MaxVertexNum];〃从顶点集u至!]V-U

的代价最小的边的辅助数组

voidPrim(MGraphG,VertexTypeu,intn)

{〃采用邻接矩阵存储结构表示图

intk,v,j;

k=vtxNum(G,u);/儆顶点u在辅

助数组中的下标

for(v=o;v<n;v++)〃辅助数组初始化

if(v!=k)

{minedge[v].ver=u;

minedge[v].lowcost=G.arcs[k][v];

)

minedge[k].lowcost=0,〃初始,U={u}

forQ=l;j<n;j++)〃选择其余的n-1

个顶点

{k=min(minedge(j])；

//l<j<n-l，找一个满

足条件的最小边(u,k),ueu,keV-u

printf(minedge[k].ver,G.vexs[k]);

〃输出生成树的边

minedge[k].lowcost=0;〃第k个顶点并

入u

for(v=0;v<n;v++)

if(G.arcs[k][v]<minedge[v].lowcost)

〃重新选择最小边

{minedge[v].ver=G.vexs[k];

mindege[v].lowcost=G.arcs[k][v];

)

)

)

普里姆算法的时间复杂度是0(n2)

【例】试用Prim算法构造下图的最小生成树，画出所有可能的情

况。

图附1-15

隐藏答案

【解析】根据Prim算法构造，本题的最小生成树有的图有两种。

【答案】最小生成树有的图有两种，如图所示

3、克鲁斯卡尔(Krtskal)算法

(1)算法思想

假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是

G的最小生成树，U的初值等于V,即包含有G中的全部顶点。T的

初始状态是只含有n个顶点而无边的森林T=(V,(p)o

该算法的基本思想是：将图G中的边按权值从小到大的顺序依次选

取E中的边(u,v),若选取的边使生成树T不形成回路，则把它并入

TE中，保留作为T的一条边;若选取的边使生成树T形成回路，则将

其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T即为

最小生成树。

【例】试用克鲁斯卡尔(Krtskal)算法构造(a)图的最小生成

当前讲授

(2)算法描述

Kruskal(G)

(〃求连通网G的一棵MST

T=(v,ip);〃初始化T为只含有n个顶

点而无边的森林

按权值升序对边集E中的边进行排序，结果存入E[O...e-l]中

for(i=0;i<e;i++)//e为图G