【最小生成树问题（Minimum Spanning Tree）——图】

r囧r小猫 2022-12-20 05:42 78阅读 0赞

### 最小生成树问题（Minimum Spanning Tree）——图 ###

*   *  1、最小生成树（Minimum Spanning Tree）
     *  2、最小生成树的典型用途
     *  3、最小生成树的求解
     *   *  ·普里姆算法（Prim)
         *  ·克鲁斯卡尔算法（Kruskal)

## 1、最小生成树（Minimum Spanning Tree） ##

**目标：在网的多个生成树中，寻找一个各边权值之和最小的生成树，即最小生成树。**  
**构造最小生成树的准则：  
1、必须只使用该网中的边来构造最小生成树  
2、必须使用且仅使用n-1条边来联结网络中的n个顶点  
3、不能使用产生回路的边**

## 2、最小生成树的典型用途 ##

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

**数学模型：  
顶点：表示城市，有n个  
边：表示线路，有n-1条  
边和权值：表示线路的经济代价**  
![在这里插入图片描述][20201110211655691.png_pic_center]

## 3、最小生成树的求解 ##

### ·普里姆算法（Prim) ###

**1、普里姆算法的基本思想：加点法**

**设N = （V,\{E\})使连通网，TE是N上最小生成树中边的集合。**

Prim算法思想的构造过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]

**2、设计数据结构**  
**（1）图采用邻接矩阵来存储  
（2）一维数组closedeg,记录从U到V-U具有最小代价的边。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]

/*图的邻接矩阵存储表示法*/
    //用两个数组分别存储顶点表和邻接矩阵
    #define MaxInt 32767  //表示极大值，即无穷
    #define MVNum 100  //最大顶点数
    typedef char VerTexType;  //假设顶点的数据类型为字符型
    typedef int ArcType;	//假设边的权值类型为整型
    typedef struct
    {
        
    	VerTexType vexs[MVNum];	//顶点表
    	ArcType arcs[MVNum][MVNum];	//邻接矩阵
    	int vexnum, arcnum;	//图的当前顶点数和边数
    }AMGraph;

**对每个顶点v，V-U在辅助数组存在一个相应的分量closedge\[i-1\],它包括两个域：**

typedef struct
    {
        
    	VerTexType adjvex;//最小边的顶点
    	ArcType lowcost;//最小边的权值
    }closedge[MAX_VERTEX_NUM];
    //adjvex:依附于这条最小代价边的另一个顶点
    //lowcost = 0 :表示顶点已经在顶点集U中
    //lowcost > 0 :表示顶点i还在V-U中

**所以，每次循环须在lowcost >0（在集合V-U中）的那些顶点中选择lowcost最小的顶点加入到集合中，同时将相关顶点的closedge作相应的调整。**

**3、Prim算法描述**

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

### ·克鲁斯卡尔算法（Kruskal) ###

**1、克鲁斯卡尔Kruskal算法的基本思想：加边法**  
**有n个结点，都看成独个连通分量，在所有边中选取权值最小的边，将两个顶点连成一个连通分量，舍弃两个顶点间的其他连线，重复此步骤，直到所有顶点都在一个连通分量上面为止。**

**2、设计数据结构**  
**算法实现要引入以下数据结构：**  
**（1）结构体数组Edge:存储边的信息，包括边的两个顶点信息和权值。**

//辅助数组Edges的定义
    typedef struct
    {
        
    	VerTexType Head;//边的始点
    	VerTexType Tail;//边的终点
    	ArcType lowcost;//边上的权值
    }Edge[arcnum];

**（2）、Vexset\[i\]：标识各个顶点所属的连通分量。对每个顶点vi属于V，在辅助数组中存在一个相应元素Vexset\[i\]表示该顶点所在的连通分量。初始化时 Vexset\[i\] = i,表示各顶点自成一个连通分量。**

//辅助数组Vexset的定义
    int Vexset[MVNum];

**3、Kruskal算法描述**

void MiniSpanTree_Kruskal(AMGraph G)
    {
         //无向网G以邻接矩阵形式存储，构造G的最小生成树T，输出T的各条边
    	Sort(Edge);//将数组Edge中的元素按权值从小到大排序
    	for (i = 0;i < G.vexnum;++i)//辅助数组，表示各顶点自成一个连通分量
    		Vexset[i] = i;
    	for (i = 1;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].End;//输出此边
    			for (i = 0;i < G.vexnum;++i)//合并vs1和vs2两个分量，即两个集合统一编号
    				if (Vexset[i] == vs2)
    					Vexset[i] = vs1;//集合编号为vs2的都改为vs1
    		}
    	}
    }

![在这里插入图片描述][20201113203720387.png_pic_center]  
**练习：利用Prim算法、Kruskal算法构造最小生成树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]

**答案：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]

[20201110211655691.png_pic_center]: /images/20221120/cdd52d905a1646e1baf66d9e00018829.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/e5a64980ddfa4a26aebcf2889ab1c3da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201113181034267.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[20201113203720387.png_pic_center]: https://img-blog.csdnimg.cn/20201113203720387.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201113203822350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201113210933735.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201113210942621.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/2020111320390561.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center