图的最小生成树--克鲁斯卡尔算法 C语言

逃离我推掉我的手 2022-11-21 14:02 141阅读 0赞

克鲁斯卡尔算法构造最小生成树。  
还是根据书上的例子进行构造：  
![在这里插入图片描述][20201101221202566.jpg_pic_center]  
步骤为（代码用邻接矩阵表示上图）：  
![在这里插入图片描述][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;
    
    struct//辅助数组Edge的定义 
    { 
    	char Head;//边的始点 
    	char Tail;//边的终点 
    	int lowcoat;//边的权值 
    }Edge[MVNum];
    
    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 i;//记录次数 
    	char a;//顶点变量 
    	printf("请输入顶点数和边数:");
    	scanf("%d %d",&G.vexnum,&G.arcnum);
    	Interrupt();//该函数用于检测并吸收换行符 
    	printf("请输入顶点名称（连续输入）：");
    	for(i=0;i<G.vexnum;i++)
    	{ 
    		scanf("%c",&a);
    		G.vexs[i] = a;//第i个顶点的命名 
    	}
    	Interrupt();//该函数用于检测并吸收换行符
    	char b,c;//顶点变量 
    	int w,j,k;//w为权值变量，j和k是用来记录次数的 
    	for(i=0;i<G.arcnum;i++)
    	{ 
    		printf("请输入边的两个顶点和权值w:");
    		scanf("%c %c %d",&b,&c,&w);//输入 
    		Interrupt();//该函数用于检测并吸收换行符
    		Edge[i].Head = b;
    		Edge[i].Tail = c;
    		Edge[i].lowcoat = w;//辅助数组Edge[]的初始化 
    		for(j=0;j<G.vexnum;j++)
    		{ 
    			if(G.vexs[j] == b)//找到输入的顶点b的位置 
    			break;
    		}
    		for(k=0;k<G.vexnum;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");
    	}
    }
    
    int Vexset[MVNum];//再申请一个辅助数组Vexset 
    void Sort(AMGraph G)//书上的Sort函数，将数组Edege中的元素按权值从小到大排序，这里用 冒泡排序 
    { 
    	int i,j;//记录次数 
    	for(i=G.arcnum-1;i>=0;i--)//相邻两数的比较终点 
    	{ 
    		for(j=0;j<i;j++)//进行相邻两数的比较 
    		{ 
    			if(Edge[j].lowcoat > Edge[j+1].lowcoat)//如果大于，互换位置 
    			{ 
    				Edge[G.arcnum] = Edge[j];
    				Edge[j] = Edge[j+1];
    				Edge[j+1] = Edge[G.arcnum];
    			}
    		}
    	}
    }
    int LocateVex(AMGraph G,char b)//定位函数，用于定位顶点b在顶点集的位置 并返回其位置 
    { 
    	int j;
    	for(j=0;j<G.vexnum;j++)//利用循环找到和b相同的顶点 
    	{ 
    		if(G.vexs[j] == b)//找到输入的顶点b的位置 
    		break;
    	}
    	return j;//返回其位置j 
    }
    void MiniSpanTree_Kruskal(AMGraph G)//无向网G以邻接矩阵形式存储，构造最小生成树，克鲁斯卡尔算法 
    { 
    	int i,j;
    	Sort(G);//根据权值排序 
    	for(i=0;i<G.vexnum;i++)//辅助数组，表示各顶点自成一个连通分量 
    		Vexset[i] = i;
    	int v1,v2,
    		vs1,vs2;
    	for(i=0;i<G.arcnum;i++)//依次查看数组Edge中的边 
    	{ 
    		v1 = LocateVex(G,Edge[i].Head);//v1为边的始点的下标 定位函数 
    		v2 = LocateVex(G,Edge[i].Tail);//v2为边的终点的下标 
    		vs1 = Vexset[v1];//获取边Edge[i]的始点所在的连通分量vs1 
    		vs2 = Vexset[v2];//获取边Edge[i]的终点所在的连通分量vs2
    		if(vs1 != vs2)//边的两个顶点分属不同的连通分量 
    		{ 
    			printf("%c->%c ",Edge[i].Head,Edge[i].Tail);//输出打印次边 
    			for(j=0;j<G.vexnum;j++)//合并vs1和vs2两个分量，即两个集合统一编号 
    				if(Vexset[j] == vs2)//集合编号为vs2的都改为vs1 
    					Vexset[j] = vs1;
    		}
    	}
    }
    
    int main()
    { 
    	AMGraph G;
    	InitGraph(G);//图的初始化 
    	CreateGraph(G);//创建邻接矩阵 
    	InputGraph(G);//输出邻接矩阵
    	MiniSpanTree_Kruskal(G);//克鲁斯卡尔算法 
    	return 0;
    }

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

[20201101221202566.jpg_pic_center]: /images/20221120/1f70ff3b8e754d789c9e25cc0c6cf2bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/bca46b3aafcc4eeb81bd7e476e64631f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/b594126ba92a4c84b5387470f9b97726.png