克鲁斯卡尔算法(Kruskal算法)求最小生成树

妙趣前端

10344人浏览 · 2020-03-15 18:25:00

妙趣前端 · 2020-03-15 18:25:00 发布

克鲁斯卡尔算法(Kruskal算法)求最小生成树

克鲁斯卡尔算法，从边的角度求网的最小生成树，时间复杂度为O(eloge)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。

对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。

由于最小生成树本身是一棵生成树，所以需要时刻满足以下两点：

1.生成树中任意顶点之间有且仅有一条通路，也就是说，生成树中不能存在回路；
2.对于具有 n 个顶点的连通网，其生成树中只能有 n-1 条边，这 n-1 条边连通着 n 个顶点。
3.连接 n 个顶点在不产生回路的情况下，只需要 n-1 条边。

所以克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法为：(方法一)

在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。

假设遍历到一条由顶点 A 和 B 构成的边，而顶点 A 和顶点 B 标记不同，此时不仅需要将顶点 A 的标记更新为顶点 B 的标记，还需要更改所有和顶点 A 标记相同的顶点的标记，全部改为顶点 B 的标记。
在这里插入图片描述
例如，使用克鲁斯卡尔算法找图 1 的最小生成树的过程为：

首先，在初始状态下，对各顶点赋予不同的标记（用颜色区别），如下图所示：
在这里插入图片描述
对所有边按照权值的大小进行排序，按照从小到大的顺序进行判断，首先是（1，3），由于顶点 1 和顶点 3 标记不同，所以可以构成生成树的一部分，遍历所有顶点，将与顶点 3 标记相同的全部更改为顶点 1 的标记，如（2）所示：
在这里插入图片描述
其次是（4，6）边，两顶点标记不同，所以可以构成生成树的一部分，更新所有顶点的标记为：

其次是（2，5）边，两顶点标记不同，可以构成生成树的一部分，更新所有顶点的标记为：

然后最小的是（3，6）边，两者标记不同，可以连接，遍历所有顶点，将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记：
在这里插入图片描述
继续选择权值最小的边，此时会发现，权值为 5 的边有 3 个，其中（1，4）和（3，4）各自两顶点的标记一样，如果连接会产生回路，所以舍去，而（2，3）标记不一样，可以选择，将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记：
在这里插入图片描述
当选取的边的数量相比与顶点的数量小 1 时，说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为（6）所示。

方法二（并查集）

将图中边按照权值从小到大排列，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路的话，则将该边并入当前生成树。直到所有的边都检测完为止。
在这里插入图片描述

并查集详细资料

实现代码

方法一：


//用于思路二
//辅助数组
typedef struct
{
	int value; // 顶点数据(下标)
	int sign;  //顶点所属集合
}Assist[MAX_VERTEX];

Assist  assists;

//在assist数组中找到顶点point对应的位置的下标
int Locatevex(int vexnum, int point)
{
	for (int i = 1; i <= vexnum; i++)
	{
		if (assists[i].value == point)
		{
			return i;
		}
	}
	return -1;
}

void Kruscal2(Matrix_Graph* G)
{
	int initail, end , i , path = 0;
	Edge_Node Edge[100];
	
	//对边集矩阵进行排序---采用冒泡排序方法
	fastSort(Edge, G);
	for (i = 1; i <= G->edge_number; i++)
	{
		initail = Locatevex(G->vertex_number, Edge[i].begin);
		end = Locatevex(G->vertex_number, Edge[i].end);//通过find找寻“待选”边两个顶点的“源顶点”
		if (assists[end].sign != assists[initail].sign && initail != -1 && end != -1)
		{
			printf("路径 %d : [%c %c] , 权值为 %d\n", path+1, G->vertex[Edge[i].begin], G->vertex[Edge[i].end], Edge[i].weight);
			path++;

			//将新生成的树标记为一样
			for (int k = 1; k <= G->vertex_number; k++)
			{
				if (assists[k].sign == assists[end].sign)
				{
					assists[k].sign = assists[initail].sign;
				}
			}

		}
		if (path == G->vertex_number - 1)
		{
			break;
		}
	}

}

方法二：

/***find函数***/
//功能：找寻每一个输入顶点的“源顶点”，并返回此源顶点
//用于思路一：
int find(int* parent, int f)//parent[i]数组记录顶点i的father为parent[i],层层追寻father，就可以找到顶点i的“源顶点”
{
	while (parent[f] > 0)
		f = parent[f];
	return f;
}

//克鲁斯卡尔主功能代码思路一：
void Kruscal(Matrix_Graph* G)
{
	int i, m, n, path;
	Edge_Node Edge[100];
	int parent[100];

    path = 0;
	
	//对边集矩阵进行排序---采用冒泡排序方法
	fastSort(Edge, G);

	//打印边集矩阵
	PrintEdge_Node(G, Edge);
	printf("\nKruscal\n");
	//parent[]数组初始化：将所有顶点的父亲顶点置0
	for (i = 1; i <= G->vertex_number; i++)
	{
		parent[i] = 0;
	}
		
	for (i = 1; i <= G->edge_number; i++)
	{
		n = find(parent, Edge[i].begin);
		m = find(parent, Edge[i].end);//通过find找寻“待选”边两个顶点的“源顶点”
		if (n != m)
		{
			parent[m] = n;//更新m顶点的“源顶点”是n
			printf("路径 %d : [%c %c] , 权值为 %d\n", path+1, G->vertex[Edge[i].begin], G->vertex[Edge[i].end], Edge[i].weight);
			path++;

		}
		if (path == G->vertex_number - 1)
		{
			break;
		}
	}
	
}

方法三

------思想类似于方法一

邻接矩阵生成

#define MAX_VERTEX 100
#define inf 65535  //用65535代表无穷大

#define VertexType char
/*************************建立无向图邻接矩阵**************************/
typedef struct Matrix_Graph
{
	VertexType vertex[MAX_VERTEX];//存储顶点信息
	int edge[MAX_VERTEX][MAX_VERTEX];//存储边信息
	int vertex_number, edge_number;//存储图中的顶点数和边数
}Matrix_Graph;


//索引判断
int index(char vex, Matrix_Graph* mg)
{
	int i;
	for (i = 1;i <= mg->vertex_number;i++)
	{
		if (mg->vertex[i] == vex)
			return i;
	}
	return 0;

}
void create_non_direction_matrix_Graph(Matrix_Graph* G)
{
	int i, j, w, k;
	VertexType h, t;
	char ch;
	printf("请输入顶点数和边数：\n");
	scanf_s("%d %d", &G->vertex_number, &G->edge_number);
	ch = getchar();
	printf("请输入无向图顶点信息(如ABCD...)：\n");
	
	for (i = 1; i <= G->vertex_number; i++)
	{
		scanf_s("%c", &G->vertex[i], 1);

		//为每一个顶点做标记不同的标记，说明属于不同的集合
		assists[i].value = i;
		assists[i].sign = i;  //用于方法2 ，思路一可不需要
	}
		
	ch = getchar();
	//初始化边信息
	for (i = 1; i <= G->vertex_number; i++)
		for (j = 1; j <= G->vertex_number; j++)
		{
			if (i == j)
				G->edge[i][j] = 0;
			else
				G->edge[i][j] = inf;
		}

	for (k = 1; k <= G->edge_number; k++)
	{
		printf("第%d条边的两个顶点(Vi,Vj)和权值" , k);
		scanf_s("%c %c %d", &h,1 ,&t,1, &w);
		ch = getchar();
		i = index(h, G);
		j = index(t, G);
		G->edge[i][j] = w;
		G->edge[j][i] = G->edge[i][j];//由于是无向图，故是对称阵
	}
	//打印邻接矩阵
	printf("*************************构造的邻接矩阵如下**************************\n");
	for (i = 1; i <= G->vertex_number; i++)
	{
		for (j = 1; j <= G->vertex_number; j++)
			if (G->edge[i][j] == inf)
			{
				printf("∞\t");
			}
			else
			{
				printf("%d\t", G->edge[i][j]);
			}
			
		printf("\n");
	}
}

将邻接矩阵转化成边集矩阵

typedef struct Edge_Node
{
	int begin;
	int end;
	int weight;
}Edge_Node;

//-----将邻接矩阵转换成记录权值从小到大排序的边集矩阵
void fastSort(Edge_Node* array, Matrix_Graph* G)
{
	int i = 1, j = 0, k;
	Edge_Node temp;
	for (j = 1; j <G->vertex_number; j++)
	{
		array[j ].begin = 0;
		array[j].end = 0;
		array[j].weight =0;
	}
	//匹配相应的权值点
	
	for (j = 1; j <= G->vertex_number; j++)
	{
		for (k = j; k <= G->vertex_number; k++)
		{
			if (G->edge[j][k] != 0 && G->edge[j][k] != inf)
			{
				array[i].begin = j;
				array[i].end = k;
				array[i].weight = G->edge[j][k];
				i++;
			}
		}
	}
	printf("\n");
	//对权值进行排序  -----冒泡排序
	for (i = 1; i <= G->edge_number; i++)
	{
		for (j = 1; j <= G->edge_number - 1; j++)
		{
			if (array[j].weight > array[i].weight)
			{
				temp = array[i];
				array[i] = array[j];
				array[j] = temp;

			}
		}
	}
	

}

//----打印边集矩阵----
void PrintEdge_Node(Matrix_Graph* G, Edge_Node* array)
{
	//打印“新矩阵”
	printf("***************构造的边集矩阵如下****************\n");
	printf("Edge[ ] \tbegin\tend\tweight\n");
	for (int i = 1; i <= G->edge_number; i++)
		printf("Edge[%d]:\t %c \t %c \t %d \t\n", i, G->vertex[array[i].begin], G->vertex[array[i].end], array[i].weight);

}

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX 100
#define inf 65535  //用65535代表无穷大

#define VertexType char
/*************************建立无向图邻接矩阵**************************/
typedef struct Matrix_Graph
{
	VertexType vertex[MAX_VERTEX];//存储顶点信息
	int edge[MAX_VERTEX][MAX_VERTEX];//存储边信息
	int vertex_number, edge_number;//存储图中的顶点数和边数
}Matrix_Graph;



//用于思路二
//辅助数组
typedef struct
{
	int value; // 顶点数据(下标)
	int sign;  //顶点所属集合
}Assist[MAX_VERTEX];

Assist  assists;



//索引判断
int index(char vex, Matrix_Graph* mg)
{
	int i;
	for (i = 1;i <= mg->vertex_number;i++)
	{
		if (mg->vertex[i] == vex)
			return i;
	}
	return 0;

}
void create_non_direction_matrix_Graph(Matrix_Graph* G)
{
	int i, j, w, k;
	VertexType h, t;
	char ch;
	printf("请输入顶点数和边数：\n");
	scanf_s("%d %d", &G->vertex_number, &G->edge_number);
	ch = getchar();
	printf("请输入无向图顶点信息(如ABCD...)：\n");
	
	for (i = 1; i <= G->vertex_number; i++)
	{
		scanf_s("%c", &G->vertex[i], 1);

		//为每一个顶点做标记不同的标记，说明属于不同的集合
		assists[i].value = i;
		assists[i].sign = i;  //用于方法2 ，思路一可不需要
	}
		
	ch = getchar();
	//初始化边信息
	for (i = 1; i <= G->vertex_number; i++)
		for (j = 1; j <= G->vertex_number; j++)
		{
			if (i == j)
				G->edge[i][j] = 0;
			else
				G->edge[i][j] = inf;
		}

	for (k = 1; k <= G->edge_number; k++)
	{
		printf("第%d条边的两个顶点(Vi,Vj)和权值" , k);
		scanf_s("%c %c %d", &h,1 ,&t,1, &w);
		ch = getchar();
		i = index(h, G);
		j = index(t, G);
		G->edge[i][j] = w;
		G->edge[j][i] = G->edge[i][j];//由于是无向图，故是对称阵
	}
	//打印邻接矩阵
	printf("*************************构造的邻接矩阵如下**************************\n");
	for (i = 1; i <= G->vertex_number; i++)
	{
		for (j = 1; j <= G->vertex_number; j++)
			if (G->edge[i][j] == inf)
			{
				printf("∞\t");
			}
			else
			{
				printf("%d\t", G->edge[i][j]);
			}
			
		printf("\n");
	}
}

/*************************克鲁斯卡尔算法**************************/
//构造记录权值、边的起点、边的终点的边集矩阵结点
typedef struct Edge_Node
{
	int begin;
	int end;
	int weight;
}Edge_Node;





//-----将邻接矩阵转换成记录权值从小到大排序的边集矩阵
void fastSort(Edge_Node* array, Matrix_Graph* G)
{
	int i = 1, j = 0, k;
	Edge_Node temp;
	for (j = 1; j <G->vertex_number; j++)
	{
		array[j ].begin = 0;
		array[j].end = 0;
		array[j].weight =0;
	}
	//匹配相应的权值点
	
	for (j = 1; j <= G->vertex_number; j++)
	{
		for (k = j; k <= G->vertex_number; k++)
		{
			if (G->edge[j][k] != 0 && G->edge[j][k] != inf)
			{
				array[i].begin = j;
				array[i].end = k;
				array[i].weight = G->edge[j][k];
				i++;
			}
		}
	}
	printf("\n");
	//对权值进行排序  -----冒泡排序
	for (i = 1; i <= G->edge_number; i++)
	{
		for (j = 1; j <= G->edge_number - 1; j++)
		{
			if (array[j].weight > array[i].weight)
			{
				temp = array[i];
				array[i] = array[j];
				array[j] = temp;

			}
		}
	}
	

}

//----打印边集矩阵----
void PrintEdge_Node(Matrix_Graph* G, Edge_Node* array)
{
	//打印“新矩阵”
	printf("***************构造的边集矩阵如下****************\n");
	printf("Edge[ ] \tbegin\tend\tweight\n");
	for (int i = 1; i <= G->edge_number; i++)
		printf("Edge[%d]:\t %c \t %c \t %d \t\n", i, G->vertex[array[i].begin], G->vertex[array[i].end], array[i].weight);

}
/***find函数***/
//功能：找寻每一个输入顶点的“源顶点”，并返回此源顶点
//用于思路一：
int find(int* parent, int f)//parent[i]数组记录顶点i的father为parent[i],层层追寻father，就可以找到顶点i的“源顶点”
{
	while (parent[f] > 0)
		f = parent[f];
	return f;
}

//克鲁斯卡尔主功能代码思路一：
void Kruscal(Matrix_Graph* G)
{
	int i, m, n, path;
	Edge_Node Edge[100];
	int parent[100];

    path = 0;
	
	//对边集矩阵进行排序---采用冒泡排序方法
	fastSort(Edge, G);

	//打印边集矩阵
	PrintEdge_Node(G, Edge);
	printf("\nKruscal\n");
	//parent[]数组初始化：将所有顶点的父亲顶点置0
	for (i = 1; i <= G->vertex_number; i++)
	{
		parent[i] = 0;
	}
		
	for (i = 1; i <= G->edge_number; i++)
	{
		n = find(parent, Edge[i].begin);
		m = find(parent, Edge[i].end);//通过find找寻“待选”边两个顶点的“源顶点”
		if (n != m)
		{
			parent[m] = n;//更新m顶点的“源顶点”是n
			printf("路径 %d : [%c %c] , 权值为 %d\n", path+1, G->vertex[Edge[i].begin], G->vertex[Edge[i].end], Edge[i].weight);
			path++;

		}
		if (path == G->vertex_number - 1)
		{
			break;
		}
	}
	
}



//思路二  用数组标记顶点，用一个集合标记，在同一个集合中有相同的标记

//在assist数组中找到顶点point对应的位置的下标
int Locatevex(int vexnum, int point)
{
	for (int i = 1; i <= vexnum; i++)
	{
		if (assists[i].value == point)
		{
			return i;
		}
	}
	return -1;
}

void Kruscal2(Matrix_Graph* G)
{
	int initail, end , i , path = 0;
	Edge_Node Edge[100];
	
	//对边集矩阵进行排序---采用冒泡排序方法
	fastSort(Edge, G);
	for (i = 1; i <= G->edge_number; i++)
	{
		initail = Locatevex(G->vertex_number, Edge[i].begin);
		end = Locatevex(G->vertex_number, Edge[i].end);//通过find找寻“待选”边两个顶点的“源顶点”
		if (assists[end].sign != assists[initail].sign && initail != -1 && end != -1)
		{
			printf("路径 %d : [%c %c] , 权值为 %d\n", path+1, G->vertex[Edge[i].begin], G->vertex[Edge[i].end], Edge[i].weight);
			path++;

			//将新生成的树标记为一样
			for (int k = 1; k <= G->vertex_number; k++)
			{
				if (assists[k].sign == assists[end].sign)
				{
					assists[k].sign = assists[initail].sign;
				}
			}

		}
		if (path == G->vertex_number - 1)
		{
			break;
		}
	}

}




//用于思路三： //查找源顶点的集合     //如果属于同一棵树上拥有同一个节点   思路二三比思路一时间复杂度较大
int find_pre(int* parent, int f)//parent[i]数组记录顶点i的father为parent[i],层层追寻father，就可以找到顶点i的“源顶点”
{
	if (parent[f] == f)
		return parent[f];
	return find_pre( parent, parent[f]);
}

//克鲁斯卡尔主功能代码思路三：
void Kruscal3(Matrix_Graph* G)
{
	int i, m, n, path;
	Edge_Node Edge[100];
	int parent[100];

	path = 0;

	//对边集矩阵进行排序---采用冒泡排序方法
	fastSort(Edge, G);

	printf("\nKruscal\n");
	//parent[]数组初始化：将所有顶点的父亲顶点置0
	for (i = 1; i <= G->vertex_number; i++)
	{
		parent[i] = i;
	}

	for (i = 1; i <= G->edge_number; i++)
	{
		n = find_pre(parent, Edge[i].begin);
		m = find_pre(parent, Edge[i].end);//通过find找寻“待选”边两个顶点的“源顶点”
		if (n != m)
		{
			printf("路径 %d : [%c %c] , 权值为 %d\n", path + 1, G->vertex[Edge[i].begin], G->vertex[Edge[i].end], Edge[i].weight);
			path++;
			//将新生成的树标记为一样
			for (int k = 1; k <= G->vertex_number; k++)
			{
				if (parent[k] == parent[n])
				{
					parent[k] = parent[m];
				}
			}

		}
		if (path == G->vertex_number - 1)
		{
			break;
		}
	}

}




int main()
{
	Matrix_Graph* G;
	G = (Matrix_Graph*)malloc(sizeof(Matrix_Graph));
	create_non_direction_matrix_Graph(G);
	Kruscal(G);
	printf("\nKruscal2");
	Kruscal2(G);
	printf("\nKruscal3");
	Kruscal3(G);

	return 0;
}

在这里插入图片描述

GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

[转载]在Windows环境下安装GNU Radio

转自：在Windows环境下安装GNURadio_恐弱智_新浪博客GNU Radio是用Python开发的，大部分开源的工程能够在Linux环境下运行良好，而Windows下却运行的很勉强，而且安装配置都很复杂。GNU Radio算是个例外了，不光提供了Windows的二进制安装，还有比较详细的说明。我是Python小白，所以折腾了好久才弄好，特意记录下来，免得以后再装还折腾。GNU Radio的

GitCode 开源社区

centOS 8 使用dnf安装Docker

DNF是什么？CentOS 8使用YUM软件包管理器版本v4.0.4。现在，该版本使用DNF(已删除YUM)。DNF是软件包管理器。它会在Linux发行版上安装，执行更新并删除软件包。使用DNF安装Docker跳过具有损坏依赖性的程序包一个有效的解决方案是使您的CentOS 8系统使用以下--nobest命令安装最符合条件的版本：sudo dnf install docker...

GitCode 开源社区

定时同步数据库表(mysql+linux+crontab)

sync.sh里面的参数需要改变，ip/username/password/database/tablesync.sh#!/bin/sh# Please change the IP and password of the data source db.# Then change the table name.filename=/home/nington/db/$(date +%Y-%m