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

àì夳堔傛蜴生んèń 2023-03-01 05:40 26阅读 0赞

改进点：使用快速排序算法代替第六章中的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;
    }

运行结果：

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

[20200722120400983.png]: /images/20230209/ad4b23b414114c51b909eb7d9a52a4c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/d780289d32664871a6a575a972155af8.png