数据结构-图的应用-最小生成树(类C语言版)

文章目录

  • 概念
    • 生成树
    • 无向图的生成树
    • 最小生成树
      • 最小生成树的典型用途
  • 最小生成树的构造
    • MST性质
      • MST性质解释
    • 普里姆(Prim)算法
    • 克鲁斯卡尔(Kruskal)算法
    • 两种算法比较

概念

生成树

所有顶点均由边连接在一起,但不存在回路的图。
数据结构-图的应用-最小生成树(类C语言版)_第1张图片

  • 一个图可以有许多棵不同的生成树;
  • 所有生成树具有以下共同特点;
    • 生成树的顶点个数与图的顶点个数相同;
    • 生成树是图的极小连通子图,去掉一条边则非连通。
    • 一个有n个顶点的连通图的生成树有n-1条边;
    • 在生成树中再加一条边必然形成回路。
    • 生成树中任意两个顶点间的路径是唯一的;
  • 含n个顶点n-1条边的图不一定是生成树。

无向图的生成树

数据结构-图的应用-最小生成树(类C语言版)_第2张图片
设图G = (V, E)是个连通图,当从图任一顶点出发遍历图G时,将边集E(G)分成两个集合T(G)和B(G)。其中T(G)是遍历图时所经过的边的集合,B(G)是遍历图时未经过的边的集合。显然,G1(V, T)是图G的极小连通子图。即子图G1是连通图G的生成树。

最小生成树

给定一个无向网络,在该网的所有生成树中,使得各边权值之和最小的那棵生成树称为该网的最小生成树,也叫最小代价生成树。
数据结构-图的应用-最小生成树(类C语言版)_第3张图片

最小生成树的典型用途

  • 欲在n个城市间建立通信网,则n个城市应铺n-1条线路;
  • 但因为每条线路都会有对应的经济成本,而n个城市最多有n(n-1)/2条线路,那么,如何选择n-1条线路,使总费用最少?

数学模型(显然此连通网是一个生成树!):
顶点——表示城市,有n个;
边——表示线路,有n-1条;
边的权值——表示线路的经济代价;
连通网——表示n个城市间通信网。

最小生成树的构造

构造最小生成树的算法很多,其中多数算法都利用了MST的性质。
最小生成树可能不唯一。

MST性质

设N = (V, E)是一个连通网,U是顶点集V的一个非空子集。若边(u, v)是一条具有最小权值的边,其中u∈U,v∈V-U,则必存在一棵包含边(u, v)的最小生成树。
数据结构-图的应用-最小生成树(类C语言版)_第4张图片

MST性质解释

在生成树的构造过程中,图中n个顶点分属两个集合:
① 已落在生成树上的顶点集:U
② 尚未落在生成树上的顶点集:V-U

接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
数据结构-图的应用-最小生成树(类C语言版)_第5张图片

普里姆(Prim)算法

算法思想:

  • 设N = (V, E) 是连通网,TE是N上最小生成树中边的集合。
  • 初始令U = {u0},(u0∈V),TE={}。
  • 在所有u∈U,v∈V-U的边{u, v}∈ E中,找一条代价最小的边(u0, v0)。
  • 将(u0, v0)并入集合TE,同时v0并入U。
  • 重复上述操作直至U=V为止,则T=(V, TE)为N的最小生成树。
    数据结构-图的应用-最小生成树(类C语言版)_第6张图片
// 辅助数组的定义,用来记录从顶点集 u到v-u 的权值最小的边
struct
{
	VerTexType adjvex; 	// 最小边在U中的那个顶点
	ArcType lowcost; 	// 最小边上的权值
} closedge[MVNum]; 

void MiniSpanTree_Prim(AMGraph G,VerTexType u) 
{	// 无向网G以邻接矩阵形式存储, 从顶点u出发构造G的最小生成树T, 输出T的各条边
	k=LocateVex(G,u); 			// k 为顶点 u 的下标
	for(j=O;j<G.vexnum;++j) 	//对v-U 的每一个顶点 V~j~, 初始化 closedge[j]
		if(j!=k) closedge[j]={u,G.arcs[k][j]}; 	//{adjvex, lowcost} 
	closedge[k].lowcost=O; 		//初始, U={u}
	for(i=1;i<G.vexnum;++i) 
	{	// 选择其余 n-1 个顶点,生成 n-1 条边(n=G.vexnum)
		k=Min(closedge); 
		// 求出 T 的下一个结点:第 K 个顶点, closedge[k]中存有当前最小边
		u0=closedge[k].adjvex; 	// u0 为最小边的一个顶点,u0∈U
		v0=G.vexs[k]; 			// v0 为最小边的另一个顶点, v∈V-U
		cout<<u0<<v0; 			// 输出当前的最小边(u0, v0) 
		closedge[k].lowcost=O; 	// 第k个顶点并入u集
		for(j=O;j<G.vexnum;++j) 
			if(G.arcs[k][j]<closedge[j].lowcost) //新顶点并入u 后重新选择最小边
				closedge [j]={G.vexs[k] ,G.arcs[k][j]}; 
	}
}

克鲁斯卡尔(Kruskal)算法

算法思想:

  • 设连通网N = (V, E),令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V, {}),每个顶点自成一个连通分量。
  • 在E中选取代价最小的边,若该边依附的顶点落在T中不同的连通分量上(即:不能形成环),则将此边加入到T中;否则,舍去此边,选取下一条代价最小的边。
  • 以此类推,直至T中所有顶点都在同一连通分量上为止。
    数据结构-图的应用-最小生成树(类C语言版)_第7张图片
    数据结构-图的应用-最小生成树(类C语言版)_第8张图片
// 辅助数组Edges 的定义
struct 
{
	VerTexType Head; 	// 边的始点
	VerTexType Tail; 	// 边的终点
	ArcType lowcost; 	// 边上的权值
} Edge[arcnum] ; 

void MiniSpanTree_ Kruskal(AMGraph G) 
{	//无向网G以邻接矩阵形式存储,构造G的最小生成树T, 输出T的各条边
	Sort (Edge); 						// 将数组 Edge 中的元素按权值从小到大排序
	for(i=O;i<G.vexnum;++i) 			// 辅助数组,表示各顶点自成一个连通分量
		Vexset[i]=i; 
	for(i=O;i<G.arcnum;++i) 			// 依次查看数组 Edge 中的边
	{
		v1=LocateVex(G,Edge[i].Head); 	// v1 为边的始点 Head 的下标
		v2=LocateVex(G,Edge[i].Tail); 	// v2 为边的终点 Tail 的下标
		vs1=Vexset[v1]; 				// 获取边 Edge[i]的始点所在的连通分量 vs1
		vs2=Vexset[v2]; 				// 获取边 Edge[i]的终点所在的连通分量 vs2
		if(vs1!=vs2) 					// 边的两个顶点分属不同的连通分量
		{
			cout<<Edge[i].Head<<Edge[i].Tail;	//输出此边
			for(j=O;j<G.vexnurn;++j) 		//合并 VS1 和 VS2 两个分量, 即两个集合统一编号
			if(Vexset[j] ==vs2) Vexset[j] =vs1; //集合编号为 vs2 的都改为 vs1
		}
	}
}

两种算法比较

算法名 普里姆算法 克鲁斯卡尔算法
算法思想 选择点 选择边
时间复杂度 O(n2)(n为顶点数) O(eloge)(e为边数)
适应范围 稠密图 稀疏图

你可能感兴趣的