数据结构与算法-第六章 图的最小生成树

概念回顾:生成树

设图G=(V, E)是一个连通图,当从图中任一顶点出发遍历图G时,将边集E(G)分成两个集合T(G)和B(G).其中T(G)是遍历图时所经过的边的集合,B(G)是遍历图时未经过的边的集合.显然G1(V, T)是图G的极小连通子图.即子图G1是连通图G的生成树.
1

所有顶点均由边链接在一起,但不存在回路的图称为生成树;
一个图可以有许多棵不同的生成树;

所有生成树具有以下共同特点:
------生成树的顶点个数与图的顶点个数相同;
------生成树是图的极小连通子图,去掉一条边则非连通;
------一个有n个顶点的连通图的生成树有n-1条边;
------在生成树中再加一条边必然形成回路;
------生成树中任意两点连的路径是惟一的;

含有n个顶点n-1条边的图不一定是生成树

最小生成树

给定一个无向网络,在该网的所有生成树中,使得各边权值之和最小的那棵生成树称为最小生成树,也叫最小代价生成树

构造最小生成树

构造最小生成树的算法有很多,其中多数都利用了MST的性质

MST性质:

设N=(V, E)是一个连通网,U是顶点集V的一个非空子集.若边(u, v)是一条具有最小权值的边,其中u∈U,v∈V-U
,则必存在一棵包含边(u, v)的最小生成树
通俗的来说就是在连通图中的最小权值的边必在一棵最小生成树中包含着

在生成树的构造过程中,图中n个顶点分属两个集合:
	已落在生成树上的顶点集合:U
	尚未落在生成树上的顶点集合:V-U
接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边
1
2
3
4
5
6
7
8

普利姆(Prim)算法

设N=(V, E)是连通图,TE是N上最小生成树中边的集合;
初始令U=(u1),(u1∈V),TE={};
在所有u∈U,v∈V-U的边(u, v)∈E中,找一条代价最小的边(u1,v1);
将(u1,v1)并入集合TE中,同时v1并入U;
重复上述操作,直至U=V为止,则T=(V, TE)为N的最小生成树;
1
2
3
4
5

克鲁斯卡尔(Kruskal)算法

设连通网N=(V, E),令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V, {}).每个顶点自成一个连通分量;
在E中选取代价最小的边,若该边依附的顶点落在T中不同的连通分量上(即不能形成环),则将此边加入到T中;否则,舍去此边,选取下一条代价最小的边;
依次类推,直至T中所有顶点都在同一连通分量中为止
1
2
3

两种算法比较

算法名		普利姆算法		克鲁斯卡尔算法

算法思想		选择点			选择边

时间复杂度	O(n^2)			O(eloge)
			n为顶点数		e为边数
适应范围		稠密图			稀疏图
1
2
3
4
5
6
7