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

淡淡的烟草味﹌ 2023-02-19 10:29 83阅读 0赞

## 克鲁斯卡尔Kruskal算法 : ##

1，该算法用到了排序算法，要求辅助数组按权值大小排序，代码中使用直接插入排序算法。

2，另外还需设置一个连通分量辅助数组，用来标识两个顶点是否在同一连通分量，因为我们要选择的是最小权值的边且边连接的两个顶点在不同连通分量的边。该算法也称“加边法”，所以克鲁斯卡尔算法更适合于求**稀疏网**的最小生成树。

还用上篇文章所用的图为例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

## 代码如下： ##

#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 Head;	//边的始点
    	VerTexType Tail;	//变的终点
    	ArcType lowcost;	//边上的权值
    }Edge[MVNum];
    Edge E;			//创建一个全局边辅助数组
    int Vexset[MVNum];		//标识各个顶点所属的连通分量，只选择不再同一连通分量的边
    
    //函数声明
    void printGraph(AMGraph G);
    int LocateVex(AMGraph G, char v);
    void InitEArray(int i, VerTexType Head, VerTexType Tail, ArcType lowcost);
    
    
    //创建无向网
    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;
    	InitEArray(1, 'v1', 'v2' , 6);	//初始化克鲁斯卡尔辅助数组E
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v3');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    	InitEArray(2, 'v1', 'v3', 1);	//初始化克鲁斯卡尔辅助数组E
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v4');
    	G.arcs[i][j] = G.arcs[j][i] = 5;
    	InitEArray(3, 'v1', 'v4',5);	//初始化克鲁斯卡尔辅助数组E
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v3');
    	G.arcs[i][j] = G.arcs[j][i] = 5;
    	InitEArray(4, 'v2', 'v3',5);	//初始化克鲁斯卡尔辅助数组E
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v5');
    	G.arcs[i][j] = G.arcs[j][i] = 3;
    	InitEArray(5, 'v2', 'v5', 3);	//初始化克鲁斯卡尔辅助数组E
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v5');
    	G.arcs[i][j] = G.arcs[j][i] = 6;
    	InitEArray(6, 'v3', 'v5',6);	//初始化克鲁斯卡尔辅助数组E
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v6');
    	G.arcs[i][j] = G.arcs[j][i] = 4;
    	InitEArray(7, 'v3', 'v6',4);	//初始化克鲁斯卡尔辅助数组E
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v4');
    	G.arcs[i][j] = G.arcs[j][i] = 5;
    	InitEArray(8, 'v3', 'v4', 5);	//初始化克鲁斯卡尔辅助数组E
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v6');
    	G.arcs[i][j] = G.arcs[j][i] = 2;
    	InitEArray(9, 'v4', 'v6', 2);	//初始化克鲁斯卡尔辅助数组E
    	i = LocateVex(G, 'v5');
    	j = LocateVex(G, 'v6');
    	G.arcs[i][j] = G.arcs[j][i] = 6;
    	InitEArray(10, 'v5', 'v6',6);	//初始化克鲁斯卡尔辅助数组E
    
    
    	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 InsertSort(Edge E) {
        
    	int i, j;
    	for (i = 2; i <= 11; ++i)		//辅助数组E的0号不用，故总长度为11
    	{
        
    		E[0] = E[i];				//哨兵
    		j = i - 1;
    		while (E[0].lowcost<E[j].lowcost)
    		{
        
    			E[j+1] = E[j];
    			j--;
    		}
    		E[j + 1] = E[0];
    	}
    }
    
    
    //最小生成树克鲁斯卡尔算法
    void MiniSpanTree_Kruskal(AMGraph G)
    {
        
    	InsertSort(E);			//排序
    	for (int i = 0; i < G.vexnum; ++i)
    	{
        
    		Vexset[i] = i;				//初始化连通分量辅助数组，各顶点自成一个连通分量
    	}
    
    	printf("\n======================\n");
    	printf("最小生成树构造顺序：");
    	for (int i = 0; i < G.arcnum; ++i)
    	{
        
    		int v1 = LocateVex(G, E[i].Head);		//v1为边的始点下标
    		int v2 = LocateVex(G, E[i].Tail);		//v2为边的终点下标
    		int vs1 = Vexset[v1];			//vs1为v1的连通分量
    		int vs2 = Vexset[v2];			//vs2为v2的连通分量
    		if (vs1 != vs2)		//选择不再同一连通分量的顶点
    		{
        
    			printf("\nv%c -> v%c", G.vexs[v1], G.vexs[v2]);	//输出选择
    
    			//改变输出顶点的连通分量为同一个	
    			for (int j = 0; j < G.arcnum;++j)	
    			{
        
    				if (Vexset[j] == vs2)
    				{
        
    					Vexset[j] = vs1;			//把连通分量为vs2的全部改成vs1
    				}
    			}
    		}
    	}
    }
    
    //初始化辅助数组
    void InitEArray(int i,VerTexType Head, VerTexType Tail, ArcType lowcost)
    {
        
    	E[i].Head = Head;
    	E[i].Tail = Tail;
    	E[i].lowcost = lowcost;
    }
    
    int main()
    {
        
    	AMGraph G;
    	CreateUDN(G);
    
    	int v = 0;
    	printf("\n======================\n");
    	printf("邻接矩阵深度优先遍历：");
    	DFS_AM(G, v);
    	
    	MiniSpanTree_Kruskal(G);
    }

## 运行结果： ##

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200620111224566.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/20200620111407785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70