图的最小生成树之Prim算法C/C++代码实现

比眉伴天荒 2023-02-19 09:24 9阅读 0赞

## 最小生成树： ##

在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称 为该连通网的最小代价生成树 (Minimum Cost Spanning Tree), 简称为**最小生成树**。

一棵有n个顶点的生成树有且仅有n-1条边。

## 普里姆Prim算法 : ##

该算法也称“加点法”，即在辅助数组中选择权值最小的顶点加入点集合U，并用刚选择的顶点更新辅助数组中到各顶点的权值。

注：该算法与网中的边数无关， 因此适用于求**稠密网**的最小生成树。

以该图为例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
辅助数组如下表（k为顶点在数组中的下标）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]

## 代码如下： ##

（下面代码中被选择的顶点权值置为0代替加入点集合U）

#include<stdio.h>
    
    #define MaxInt 9			//定义无穷大，这里设置一个比所有边的权值都大的数9
    #define MVNum 100
    typedef char VerTexType;    //顶点类型
    typedef int ArcType;		//边权值类型
    
    //邻接矩阵的存储结构
    typedef struct
    {
        
    	VerTexType vexs[MVNum];				//顶点表
    	ArcType arcs[MVNum][MVNum];			//邻接矩阵
    	int vexnum, arcnum;					//图的当前点数和边数
    }AMGraph;
    
    //最小生成树普里姆算法定义
    //辅助数组
    typedef struct
    {
        
    	VerTexType adjvex;
    	ArcType lowcost;
    }closedge[MVNum];
    
    //函数声明
    void printGraph(AMGraph G);
    int LocateVex(AMGraph G, char v);
    int Min(closedge C, AMGraph G);
    
    
    //创建无向网
    void CreateUDN(AMGraph &G)
    {
        
    	G.vexnum = 6;						//输入总顶点数和边数
    	G.arcnum = 10;
    	G.vexs[0] = 'v1';					//输入顶点信息
    	G.vexs[1] = 'v2';
    	G.vexs[2] = 'v3';
    	G.vexs[3] = 'v4';
    	G.vexs[4] = 'v5';
    	G.vexs[5] = 'v6';
    
    	//初始化邻接矩阵为极大值
    	for (int i = 0; i < G.vexnum; i++)			
    	{
        
    		for (int j = 0; j < G.vexnum; j++)
    		{
        
    			G.arcs[i][j] = MaxInt;
    		}
    	}
    
    	//建立边
    	int i, j;
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v2');
    	G.arcs[i][j] = G.arcs[j][i] = 6;
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v3');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v4');
    	G.arcs[i][j] = G.arcs[j][i] = 5;
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v3');
    	G.arcs[i][j] = G.arcs[j][i] = 5;
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v5');
    	G.arcs[i][j] = G.arcs[j][i] = 3;
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v5');
    	G.arcs[i][j] = G.arcs[j][i] = 6;
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v6');
    	G.arcs[i][j] = G.arcs[j][i] = 4;
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v4');
    	G.arcs[i][j] = G.arcs[j][i] = 5;
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v6');
    	G.arcs[i][j] = G.arcs[j][i] = 2;
    	i = LocateVex(G, 'v5');
    	j = LocateVex(G, 'v6');
    	G.arcs[i][j] = G.arcs[j][i] = 6;
    
    
    	printGraph(G);
    }
    
    
    //查找指定顶点的数组下标，并返回
    int LocateVex(AMGraph G, char v)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		if (G.vexs[i] == v)
    		{
        
    			return i;
    		}
    	}
    }
    
    //打印输出图
    void printGraph(AMGraph G)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		printf("v%d :", i + 1);
    
    		for (int j = 0; j < G.vexnum; j++)
    		{
        
    			printf("%d ", G.arcs[i][j]);
    		}
    		printf("\n");
    	}
    }
    
    
    //邻接矩阵深度优先遍历
    bool visited[MVNum];
    void DFS_AM(AMGraph G, int v)
    {
        
    	printf("v%c->", G.vexs[v]);
    	visited[v] = true;
    	for (int w = 0; w < G.vexnum; w++)
    	{
        
    		if ((G.arcs[v][w]) != 0 && (!visited[w]))
    		{
        
    			DFS_AM(G, w);
    		}
    	}
    }
    
    //最小生成树普里姆算法
    void MiniSpanTree_Prim(AMGraph G, VerTexType u, closedge C)
    {
        
    	int k = LocateVex(G, u);			//获取起始顶点的数组下标
    	for (int j = 0; j < G.vexnum; ++j)	//初始化普里姆算法的辅助数组
    	{
        
    		if (j != k)
    		{
        
    			C[j].adjvex = u;					//顶点
    			C[j].lowcost = G.arcs[k][j];		//该顶点到各顶点的权值
    		}
    	}
    	C[k].lowcost = 0;							//把已加入点集合的权值置为0
    	printf("\n======================\n");
    	printf("最小生成树构造顺序：");
    
    	for (int i = 1; i < G.vexnum; ++i)
    	{
        
    		k = Min(C, G);			//选择最小的权值的顶点，并返回下标存入k中
    
    		char u0 = C[k].adjvex;	//之前加入的顶点
    		char v0 = G.vexs[k];	//要加入的顶点
    		printf("\nv%c -> v%c", u0, v0);	//输出选择
    		C[k].lowcost = 0;
    
    		//如果新加入的顶点到某个顶点的权值有比之前更小的，则更新辅助数组
    		for (int j = 0; j < G.vexnum; ++j)
    		{
        
    			if (G.arcs[k][j]<C[j].lowcost)
    			{
        
    				C[j] = {
         G.vexs[k] ,G.arcs[k][j] };
    			}
    		}
    	}
    }
    
    //选择辅助数组中除0外最小权值的顶点的下标，并返回
    int Min(closedge C, AMGraph G)
    {
        
    	int min = MaxInt;
    	int index = 0;
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		if (C[i].lowcost<min && C[i].lowcost != 0)			//权值为0的表示已经加入点集合，所以不再遍历
    		{
        
    			min = C[i].lowcost;
    			index = i;
    		}
    	}
    	return index;
    }
    
    
    int main()
    {
        
    	closedge C;
    	AMGraph G;
    	CreateUDN(G);
    
    	int v = 0;
    	printf("\n======================\n");
    	printf("邻接矩阵深度优先遍历：");
    	DFS_AM(G, v);
    
    	char u = 'v1';			//设v1为起始顶点
    	MiniSpanTree_Prim(G, u, C);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200619190843419.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200619191209628.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200619191415812.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70