改进的Kruskal算法 (C语言实现)

改进点：使用快速排序算法代替第六章中的Kruskal算法的冒泡排序。Kruskal算法的时间复杂度取决于排序算法的时间复杂度。冒泡排序时Kruskal算法的时间复杂度为O(M^2)，改用快速排序后，时间复杂度降为O(M * logM)。其中M为图中边的数量。注意，用三路快速排序、双基准三路快速排序等改进的快速排序算法，不要用原始的快速排序。

#include <stdio.h> 
#include <stdlib.h> 

//定义一个边的结构体。一条边需要起点、终点和长度 
struct Edge{
	int startIndex, endIndex, distance;
};

int n = 6; //6个点 
int m = 10; //一共10条边 
struct Edge arrEdge[10]; //存放10条边的一个数组 
int arr[6 + 1]; //并查集用的一维数组，不使用下标为0的元素，所以要 + 1 

void initEdge() //初始化所有边 
{
	arrEdge[0].startIndex = 0; arrEdge[0].endIndex = 1; arrEdge[0].distance = 10;
	arrEdge[1].startIndex = 0; arrEdge[1].endIndex = 2; arrEdge[1].distance = 16;
	arrEdge[2].startIndex = 0; arrEdge[2].endIndex = 3; arrEdge[2].distance = 14;
	arrEdge[3].startIndex = 1; arrEdge[3].endIndex = 3; arrEdge[3].distance = 15;
	arrEdge[4].startIndex = 1; arrEdge[4].endIndex = 4; arrEdge[4].distance = 24;
	arrEdge[5].startIndex = 2; arrEdge[5].endIndex = 3; arrEdge[5].distance = 14;
	arrEdge[6].startIndex = 2; arrEdge[6].endIndex = 5; arrEdge[6].distance = 16;
	arrEdge[7].startIndex = 3; arrEdge[7].endIndex = 4; arrEdge[7].distance = 23;
	arrEdge[8].startIndex = 3; arrEdge[8].endIndex = 5; arrEdge[8].distance = 8;
	arrEdge[9].startIndex = 4; arrEdge[9].endIndex = 5; arrEdge[9].distance = 22;
}

void initArr() //初始化并查集要用到的数组，这里是从1开始计数的 
{
	for(int i = 1; i < n; i++)
	{
		arr[i] = i;
	}
}

void swap(int a, int b) //交换数组arrEdge中编号为a和b的两个元素 
{
	struct Edge temp = arrEdge[a];
	arrEdge[a] = arrEdge[b];
	arrEdge[b] = temp;
}

void quickSort(int low, int high) //三路快速排序 
{
	if(low > high) //递归的出口 
	{
		return;
	}
	
	int i = low; 
	int j = high;
	int cur = i; //cur用来遍历数组arr 
	struct Edge standard; //基准，用来记录arrEdge的首元素 
	
	//rand()%m;//把随机数控制在0~m-1之间
	//所以下面这个语句的意思是把随机数控制在low ~ high之间 
	int randomIndex = rand()%(high - low + 1) + low;
	
	swap(low, randomIndex); //交换首元素和随机位置的数据 
	standard = arrEdge[low]; //记录首元素 
	
	//当前cur下标还没有与j相遇时继续循环
	//也就是与基数相等的数据刚好跟大于基数的数据接触时停止循环 
	while(cur <= j)  
	{
		if(arrEdge[cur].distance == standard.distance) //把与基数相等的数据放在中间 
		{
			cur++;//相等时，只需要移动cur，不需要移动i和j
		}
		
		//把小于基数的数据都放在左边
		//左边已经放了与基数相等的数，所以需要交换一下，让与基数相等的数到中间来
		else if(arrEdge[cur].distance < standard.distance) 
		{
			swap(cur, i); //把下标为cur的值与i交换 
			cur++; //小于基准时，移动cur
			i++; //比基准小的数+1，所以i也加1
		}
		
		//大于基数的数据都放在最右边，从右往左放置
		else
		{
			swap(cur, j); //把下标为cur的值与j交换 
			j--;//从右往左放置，所以j--
		}
	}
	
	//一轮循环之后，数组arr分为三段：小于基准的数，等于基准的数、大于基准的数。
	//中间一段数组 (下标：i ~ j) 已经有序了。只需要对左右两段数组继续排序即可。 
	quickSort(low, i - 1); //左边一段数组继续排序，左边一段数组的终点是i - 1 
	quickSort(j + 1, high); //右边一段数组继续排序。右边一段数组的起点是j + 1 
}

void sort()//调用快速排序
{
	//图中一共有m条边，arrEdge数组的最大元素编号为m - 1 
	quickSort(0, m - 1); //调用快速排序
} 

int getBoss(int n) //找老板 
{
	if(arr[n] == n)
	{
		return n;
	}
	
	//递归找老板，顺便压缩路径，时间复杂度为O(1)
	arr[n] = getBoss(arr[n]); 
	return arr[n];
}

int merge(int x, int y) 
{
	int bossX = getBoss(x); //找x的老板
	int bossY = getBoss(y); //找y的老板
	
	if(bossX != bossY) //老板不一样的时候，要合并。并返回1 
	{
		arr[bossY] = bossX; //修改老板的信息
		return 1;
	}
	return 0; //老板一样的时候，不合并，返回0
 } 

int main()
{
	int sum = 0;
	int count = 0;
	
	initEdge(); //初始化边
	initArr(); //初始化并查集的数组
	
	sort(); //按照边的长度从小到大排序 
	
	//按照边的长度从小到大遍历 
	for(int i = 0; i < m; i++)
	{
		//如果一条边上的两个点还没有被放在同一棵树中，则放在同一棵树中 
		struct Edge e = arrEdge[i];
		if(merge(e.startIndex, e.endIndex)) //合并 
		{
			sum += e.distance; //总的距离要累加 
			count ++; //增加了一条边 
			printf("选用的边：%d --> %d: %d\r\n", e.startIndex, e.endIndex, e.distance);
		}
		
		//n个点需要n - 1条边。
		//增加这个判断有可能提前结束循环，提高代码的效率
		//没有这个判断不影响最后的计算结果 
		if(count == n - 1) 
		{
			break;
		}
	}
	printf("sum = %d", sum);
	return 0;
}

运行结果：

下面对三种最小生成树算法进行对比：
注：
1、N表示点的个数，M表示边的个数。
2、Prim算法的时间复杂度是O(N^2)。M的大小与Prim算法的时间复杂度无关。所以Prim算法在计算稠密图 (M很大) 时更有优势。当然，Prim算法也可用于稀疏图 (M很小)，但是相对而言，优化后的Prim算法和Kruskal算法用来计算稀疏图 (M很小) 更快。所以优化后Prim算法和Kruskal算法适用于稀疏图。
直接用C语言实现优化的Prim算法的代码很长，且比较复杂。C++中提供了优先级队列的模块，直接调用模块就比较简单。