图的最小生成树 -普里姆算法 c语言

Dear 丶 2022-11-21 11:47 166阅读 0赞

这里运用邻接矩阵来进行对普里姆算法的实现。  
还是按照课本上的例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MaxInt 32767
    #define MVNum 100 //图的最大容量 ，也可以称为图的最大顶点数 
    
    void Interrupt(void)//创建一个中断函数 
    { 
    	while(1)//用于检测换行符，使函数脱离scanf的连续输出 
    		if(getchar()=='\n')
    			break;
    } 
    
    typedef struct//图的结构体 
    { 
    	char vexs[MVNum];//顶点表 
    	int arcs[MVNum][MVNum];//邻接矩阵 
    	int vexnum,arcnum;//图的当前点数和边数 
    }AMGraph;
    
    void InitGraph(AMGraph &G)//图的初始化 
    { 
    	int i,j;
    	for(i = 0;i<MVNum;i++)
    		for(j = 0;j<MVNum;j++)
    			G.arcs[i][j] = MaxInt;//使邻接矩阵中的数据都初始化为0 
    }
    
    void CreateGraph(AMGraph &G)//图的创建 
    { 
    	int m,//顶点个数变量 
    		n,//边个数变量 
    		i;//记录次数 
    	char a;//顶点变量 
    	printf("请输入顶点数和边数:");
    	scanf("%d %d",&m,&n);
    	Interrupt();//该函数用于检测并吸收换行符 
    	G.vexnum = m;//顶点 
    	G.arcnum = n;//边 
    	printf("请输入顶点名称（连续输入）：");
    	for(i=0;i<m;i++)
    	{ 
    		scanf("%c",&a);
    		G.vexs[i] = a;//第i个顶点的命名 
    	}
    	Interrupt();//该函数用于检测并吸收换行符
    	char b,c;//顶点变量 
    	int w,j,k;//w为权值变量，j和k是用来记录次数的 
    	for(i=0;i<n;i++)
    	{ 
    		printf("请输入边的两个顶点和权值w:");
    		scanf("%c %c %d",&b,&c,&w);//输入 
    		Interrupt();//该函数用于检测并吸收换行符
    		for(j=0;j<n;j++)
    		{ 
    			if(G.vexs[j] == b)//找到输入的顶点b的位置 
    			break;
    		}
    		for(k=0;k<n;k++)
    		{ 
    			if(G.vexs[k] == c)//找到输入的顶点c的位置 
    			break;
    		}
    		G.arcs[j][k] = G.arcs[k][j] = w;//权值赋值 
    	}
    }
    
    void InputGraph(AMGraph G)//邻接矩阵的输出 
    { 
    	int i,j;//记录次数 
    	printf("邻接矩阵为：\n ");
    	for(i=0;i<G.vexnum;i++)//打印顶点名称 
    		printf("%c ",G.vexs[i]);
    	printf("\n");
    	for(i=0;i<G.vexnum;i++)
    	{ 
    		printf("%c ",G.vexs[i]);//打印顶点名称 
    		for(j=0;j<G.vexnum;j++)//遍历邻接矩阵 
    			printf("%d ",G.arcs[i][j]);
    		printf("\n");
    	}
    }
    
    struct//辅助数组的定义，用来记录从顶点集U到V-U的权值最小的边 
    { 
    	char adjvex;//最小的边在U中的那个顶点 
    	int lowcost;//最小的边上的权值 
    }closedge[MVNum];
    
    int Min(AMGraph G)//普里姆算法中的Min 
    { 
    	int i,//次数 
    		a,//用于记录最小值的位置 
    		min = MaxInt;//先使min设为最大值 
    	for(i=0;i<G.vexnum;i++)
    	{ 
    		if(closedge[i].lowcost == 0) 
    			continue;
    		if(min>closedge[i].lowcost)
    		{ 
    			min = closedge[i].lowcost;
    			a = i;
    		}	
    	}
    	return a;//返回最小值的位置 
    }
    
    void MiniSpanTree_Prim(AMGraph G,char u)
    { 
    	int i,j,//记录次数变量 
    		k;//顶点位置变量 
    	for(j=0;j<G.vexnum;j++)//书上的函数LocateVex，为了简单直接写上了 
    		{ 
    			if(G.vexs[j] == u)//找到输入的顶点b的位置 
    			break;
    		}
    	k = j;//k为顶点u的下标 
    	for(j=0;j<G.vexnum;j++)//对V-U的每一个顶点vj,初始化closedge[j] 
    	{ 
    		if(j != k)
    		{ 
    			closedge[j].adjvex = u;
    			closedge[j].lowcost = G.arcs[k][j];
    		}
    	}
    	closedge[k].lowcost = 0;//初始，U={u},至此初始化结束 
    	char u0,v0;
    	for(i=0;i<G.vexnum;i++)//选择其余n-1个顶点，生成n-1条边 
    	{ 
    		k = Min(G);//求出closedge[]中除去已选边以外的最小边 
    		u0 = closedge[k].adjvex;//u0为最小边的一个顶点，u0属于U 
    		v0 = G.vexs[k];//v0为最小边的另一个顶点，v0属于V-U 
    		printf("%c->%c ",u0,v0);//输出，当前的最小边（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];
    			}
    		}	
    	}
    }
    
    int main()
    { 
    	AMGraph G;
    	InitGraph(G);//图的初始化 
    	CreateGraph(G);//创建邻接矩阵 
    	InputGraph(G);//输出邻接矩阵 
    	MiniSpanTree_Prim(G,0);//普里姆算法函数 
    	return 0;
    }

结果演示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/ff40afb4bc424d7b8b3b6e500bee4769.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201101165805916.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0,size_16,color_FFFFFF,t_70#pic_center